526互联

Educational Codeforces Round 127 (Rated for Div. 2)

发布时间 2023-04-24 16:42:53作者: 努力的德华

题目链接

D

核心思路

首先挖掘下操作的性质吧：

x>1&&x+3<10:
1 x x+1 x+2 x+3 10
我们可以发现这样子好像对于我们的结果是没有影响的，答案还是9.
所以这个性质就挖掘出来了啊，只要我们把一段连续的插入到对应的区间里面就好了。也就是只要这个区间的左端点小于插入连续的数的最小值，右端点大于插入的连续的数的最大值。那么肯定是最优的。因为不会对我们的答案产生贡献啊。

我们可以知道的是我们插入的这一段数的最小值是1，最大值是x。

所以我们就看原序列里面的mn和mx和他们的情况。其实如果\(mn>1||mx<x\).那么其实对于答案的贡献就是插入1和插入x。

我们线性扫描看哪个位置插入1or x 对于我们的答案的影响最小就好了。

E

核心思路

这个题目确实挺不错的，其实可以理解为就是一个树形dp。从底往上跟新下答案就好了。

但是这里有个蛋疼的地方就是有可能我们的左右子树是同构，什么是同构呢，因为\(f[u]表示的以u做为子树包含的前序串的个数\)。

正常来说：\(f[u]=f[ls(u)]*f[rs(u)]*2\).但是如果是同构那么交换就没有意义，所以也就是不需要乘2.

那么怎么判断同构呢，其实很简单。我们只需要求出来以u作为子树的最小字典序就好了。

所以整个题目也就做出来了，其实也还好。不是特别的困难。