A

• 本身就是不回文字符串，答案为 \(0\)。
• 本身是回文字符串。
  • 只由一种字符组成，答案为 \(\left|s\right|\)。
  • 由至少两种字符组成，答案为 \(1\)。

因为回文串中的字符，除了最中间自己对应自己的一段，旁边两两对应的一定要完全相同，只要删除其中任意一个字符使它们不相同就行。

时间复杂度 \(O\left(\left|s\right|\right)\)。

B

贪心，重复的选大的，没重复直接选。

时间复杂度 \(O\left(\left(n+m\right)\log n\right)\)。

C

然后发现当一个子树的根结点拥有一个以上的儿子时，子树内的一些链与子树外的那一条链的公共点只能在子树的根结点。子树内若只有一条链，则不可能传出去；子树内若有大于一条链，则至多传一条出去。

这样的话子树外也最多只有一条链了，也就是说子树外必定是一条链。

所以整棵树最多只有一个结点的度可以大于 \(2\)，也就是菊花图，每条链均从根到叶子即可。

时间复杂度 \(O\left(n\right)\)。

D

套路题，很难直接记录值，按位确定。

判断写个 DP，令 \(f_{i,j}\) 前 \(i\) 本书放了 \(j\) 个书架能否合法。

时间复杂度 \(O\left(n^2k\log a\right)\)。

E

超级好题，看得我一脸懵。

如果选取的操作区间均包含了某个位置，那么这个位置一定是最大值。

于是我们考虑选取若干个操作区间使它们的并集非空（反之去掉一些操作区间不会造成影响），此时它们 \(x\) 的和就可以作为最大值。

将操作区间按右端点从小到大排序，依次处理。用 \(f_i\) 表示当前值为 \(i\)，并集能取到的最右端点（贪心，越靠右越可能被新加入的区间覆盖），类似可行性背包转移即可。

最后若 \(f_i>0\) 说明 \(i\) 值可作为最大值。

时间复杂度 \(O\left(q\left(n+\log q\right)\right)\)。

F

随机化好题。

有一个暴力的想法，暴力枚举一对新郎新娘，然后依次配下去，可以用调整法证明正确性。

然后加一个剪枝，如果当前最大值已经大于等于全局最小值，就跳出。

交一发，\(\texttt{TLE}\)，被卡到了 \(O\left(n^2\right)\)。

我能想到的方法是对着剪枝卡，将每次搞到的最大值从小到大和从小到大分别排一次序（不清楚枚举顺序），这样就很容易在其中一个点爆炸。

尝试随机枚举第一对新郎新娘，还是被卡掉了。

现在就比较玄学了，我们猜想它可能把距离全搞成有序的，也就是说在配的时候我们不能及时跳出（虽然全局最小值能很快缩减）。

在刚刚的基础上随机配，这样它就卡不掉我了。

时间复杂度不是很清楚，先鸽着。

后面的题都鸽了。