Codeforces

Codeforces Round 934 (Div. 2)¶

ABC 都挺水的。

D 题跑一遍 manacher，然后就得到了以每个字符为中心的最长回文串的长度，假设是 \(len\)，那么 \(1\sim len\) 的都要排除，只需要打个 ST 表存一下区间最长回文串的长度，最后用 \(1\sim n\) 的和减去 \(1\sim len\) 的总和即可。
E 题如果树的形状确定了的话，第一想法必然是用根结点一层一层染，如果这个做法正确的话就需要找到以哪个结点为根结点最佳。
- 想要使操作数尽量少，那么我们必然希望这棵树的深度能尽量小，那必然是以树的直径的中点（之一）为根最佳
- 不妨设直径长度为 \(n\)，如果 \(n\) 为奇数，那么显然直接以中点为根一层层染色即可，操作数为 \(\lceil \frac{n}{2}\rceil\)，其实这个时候可以发现，我们只需要考虑给这个直径染色就可以了
- 如果 \(n\) 为偶数，试一下 4 和 6 的例子，会发现 4 的操作数依旧是 \(\frac{n}{2}\)，而 6 则会多出来一个 1
- 换而言之，对于 \(n\equiv 0\pmod{4}\) 的情况，最小操作数仍然是 \(\frac{n}{2}\) ，方法懒得写了
- 对于 \(n\equiv 2\pmod{4}\) 的情况，最小操作数会是 \(\frac{n}{2}+1\)，方法懒得写了

总结是构造思维没练好, 还是应该多做做构造题的.