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作为子树的最小字典序就好了。
所以整个题目也就做出来了,其实也还好。不是特别的困难。
标签:Educational,Rated,题目,Codeforces,同构,127,Div From: https://www.cnblogs.com/xyh-hnust666/p/17350025.html