日记

不是考试就是综合训练。

Game on Tree (Hard)# Link to

首先看的不是这题，但是首先 A 的是这题。

先口胡了一个神秘小 dp，果不其然连样例都过不了。经过一番严密推理发现 dp 状态设的有点漏洞，于是把漏洞补起了，内心浅浅的博弈了一下便开始写了。令人震惊的是居然过了样例。更令人震惊的是竟然就这么水灵灵的过了。上洛谷一搜：$\textcolor{3498DB}蓝$ 的？！我能切蓝题，真的假的？

当然是假的。

Minimizing the Sum# Link to

其实最先看的是这道题。先口胡了一个假做法：把每个 $|a_i - a_{i - 1}|$ 都扔到一个 multiset 里面，每次取最大的用来更改答案。但是很显然这个是一个错的。因为有些时候，两个 $i$ 所对应的 $|a_i - a_{i - 1}|$ 是一样的，但是他们俩并不一样优，要判断的话需要 $O(n)$，显然不可取。

我见过好多这种“两种决策看起来一样但是实际上不一样，要决定哪个更优需要再考虑好多麻烦的东西”这样的题。这种无一例外都是 dp。看到 $k \le 10$，就想到把它塞到状态里。然后就搓了一个 $O(nk^2)$，过了。

说句闲话：本来以为是 $O(n^2 k)$ 的，AC 的时候吓死我了，我还以为 CF 神机一秒能跑 $3 \times 10^{11}$ 呢。

Infinite Sequence (Easy Version)# Link to

首先就想到 $a_m = \bigoplus\limits_{1}^{\lfloor \frac{m}{2} \rfloor} a_i = a_{m - 2} \oplus a_{\lfloor \frac{m}{2} \rfloor}$，但是如果递归求解的话，因为有 $m - 2$，所以是 $O(n)$ 起步的。显然不可取。下午看了题解才知道如何变成 $O(\log n)$。

还是太菜了。

Nene and the Mex Operator# Link to

这道是蓝的，但是没有切出来。赛时只想到了要操作的区间必须出现 $[0,len - 1]$ 的每个数才最优，实际上可以通过神秘小操作给他操作到这个区间内每个数都是 $len - 1$。先用区间 dp 求解答案，再使用神秘小构造求解操作方法。

总结：实力有增长，但不多。去看了一眼 2023 的 S 组，T2 一眼能想到 50%，多看几眼应该就能做出来。