日记 - 伊埃斯的博客站

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

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

Make a Palindrome↗

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

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

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

Make it Zero↗

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

我们考虑 $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\}$ ，那么有

\begin{cases} a = a_1 + a_2 \\ b = b_1 + b_2 \\ c = c_1 + c_2 \\ a_1 + b_1 = c_1 \\ a_2 = b_2 + c_2 \end{cases}

解方程得出 $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)↗

我们有朴素的 $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}$ 就行。

后日谈

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

Thanks for reading!

日记

周一 7月 07 2025

677 字 · 3 分钟

life 日记