省选模拟 14

老规矩，礼尚往来。我觉得题目的英文名字比中文名字好看一些，中文名字就一个字，好-色-乐。

good

题目要求不一定删完，如果我们知道强制删完每个区间的最大价值，剩下的操作就是一个简单的 \(n^2\) DP。

现在我们只需要求出来删掉每个区间的最大价值。考虑区间DP。

讨论区间端点l,r是不是同时被删去的。如果不是，那么整个区间一定存在一个分界点满足左右互不影响，这一部分枚举分界点转移即可。

如果l和r是同时删去的，那么也就是说存在一个起点为l终点为为r的好串。

观察好串的性质，发现好串一定是一个先递增然后递减的序列。这样我们就容易进行DP了。

我们可以分两边DP个单调递增的序列，然后枚举最高点拼起来即可，注意l和r可能是最高点。

复杂度\(O(n^3)\)，我的实现比这个复杂度要大，看上去像是\(n^4\)，但是实际的运算量只是多了个较大的常数。

color

注意最小距离一定是一条边的权值，这个东西显然。

还有一个很重要的性质，就是最小权值一定在最小生成树上，这个东西好像也是显然的，可以尝试反证法证明。

综合以上性质，最小权值一定是最小生成树的一条边。

我们对于父亲节点维护儿子颜色个数个可重集，然后维护一个全局可重集。

更新时在父亲节点处更新自己的贡献即可，然后对于自己的颜色则直接修改，或许还需要维护一颗线段树。

复杂度\(O(nlogn)\)。

然而我并没有写这个做法，出题人是良心的，数据是随机的，所以.........

music

显然是有border的数量好记，于是我们用总数减去有border的个数就行。

我们考虑如何计数，朴素的想我们需要枚举border长度，一开始我想枚举最长border的长度，但是这个东西的重复部分非常不好去，我尝试了很多种容斥然后都失败了。

于是换一个方向考虑，我们枚举最短的border，这样我们只需要限制这个border没有border即可，你会惊喜地发现这就是DP的子状态，完全可以转移。

于是现在枚举border可以做到\(O(n^2)\)。

发现转移式子是卷积的形式，与是可以用分治NTT来优化，复杂度\(O(nlog^2n)\)，此时无法通过。

考虑最短border的长度不会超过n/2，于是只需要求出前n/2项即可，最后再计算第n项。注意卷积有一些限制，使得分治乘法和模板并不太一样。