日记

前几天实在是太颓废了点，直到今天才恢复。

今天主要的就是 VP 昨天晚上的 CF，还有改题。

Make a Palindrome# Link to

我们设整个数列第 $k$ 小的是 $w$，那么小于 $w$ 的一定会被留下来，而 $w$ 是可以被选择留不留下来的。小于等于 $w$ 的数的数量又一定大于等于 $k$。所以我们只考虑小于等于 $w$ 的数。

我们把所有小于 $w$ 的单独拎出来，那么他们一定要是一个回文串，否则输出 NO，然后如果这些数的数量小于 $k - 1$，那么我们就需要把那些在小于 $w$ 的数之间的缝里的 $w$ 加进去。如果在 $w$ 数量也回文的情况下都凑不出 $k - 1$ 个，就说明无解。

最后把所有的无解都判掉就可以输出 YES 了。

Make it Zero# Link to

先把无解和只用一次特判掉。

我们考虑 $n = 3$ 的情况。设它们是 $\{a,b,c\}$，观察题解得到只要有解就说明次数 $\le 2$，我们又把 $1$ 的情况特判掉了，所以只能是 $2$ 次。

我们发现两次的分界点不可能在同一个地方，所以只能分别在 $a,b$ 的缝里和在 $b,c$ 的缝里。设第一次的 $B_1 = \{a_1,b_1,c_1\}$，第二次的 $B_2 = \{a_2,b_2,c_2\}$，那么有

解方程得出 $b_1 = \frac{c + b - a}{2},b_2 = \frac{a + b - c}{2}$。构造就这么构造：$a_1 = a,a_2 = 0$，$c_1,c_2$ 就能够算出来了。

$n > 3$ 的情况类比一下，设 $i$ 表示 $i$ 前面的数的和小于 $\frac{sum}{2}$，加上 $a_i$ 就大于 $\frac{sum}{2}$ 了，那么 $i$ 所对应的两次操作就是 $b_1,b_2$，左边就是 $a_1,a_2$，右边就是 $c_1,c_2$。

Appending Permutations (Easy Version)# Link to

我们有朴素的 $O(n^3)$ 但是能过 dp：设 $dp_i$ 表示填到 $i$ 结尾的方案数。转移就去枚举最后一段。

但是我们发现样例都过不了。究其原因是这样子的：1 2 3 4 1 2 被计算了两次，一次是 1 2|3 4 1 2，另一次是 1 2 3 4|1 2。我们把它给一般化：$s_2+1,\dots,s_1|1,2,\dots,s_2$。而且这样有要求：$s_1 > s_2$。我们再记录一个 $dp2_{i,j}$ 表示 $i$ 以 $j$ 结尾（且不用考虑是否算重）的方案数。我们在没有偏移量时将 $dp_i$ 减掉一个 $\sum_{j = s + 1}^{\text{上界不管}}dp2_{i - s,j}$ 就行。

后日谈 # Link to 后日谈

我每天真的没有在虚度光阴吗？