PKUWC 2025 游记

· · 生活·游记

省流：100+100+20+95+73+44=432。

Day 1

这个 T1 是啥，做了 1h 不会做，只得了 10 分，先去看 T2。

这很像区间颜色数，一眼离线维护 pre，随便画画图就知道只变 O(n\log n) 次，dsu on tree 随便维护，然后 cdq，感觉不好写，而且常数可能起飞，然后就开始想一些最坏打算，比如说这个题被卡常了喜提暴力分或者调不出来最后不达三位数，但是鉴于不会其它任何分就开始莽，调了一下，过了样例，测了很久，发现过了。

这时感觉状态好了很多，去做 T1，后来发现 a>b+1 很有启发性啊，考虑分组去做它，那就能 dp[i][j] 表示 i 个 0 j 个 1 的最小代价，枚举分成多少组暴力转移，发现能过 60.

打表发现必然分 i-1 组，那我不是做完了，过掉 T1。

用剩下的时间给 T3 整了 20 分暴力。

好像打了不及大众分的分数。

Day 2

T1 交互，一眼 5 个分组求直径，可以先分组问，然后相邻合并直径，会了 4n，但是 n<5 的边界很唐需要判判，大概捣鼓了 1 小时得了 83 分？

相邻 2 个问很浪费哦。因为 10 个信息我就用了 6 个。我可以递归：T(n)=T(\dfrac{2}{5}n)+2n=\dfrac{10}{3}n，在边界情况需要优化一下询问，否则询问次数为 3\times 10^5+eps。整到了 95。

T2 先胡乱写了 11，发现记搜转移听着很对啊，于是改改就有 73 了。

T3 的暴力还是比较简单的，但是 5e6 就过不了了，得迪利克雷前缀和，l=r,B\le 4 记搜一下就好了，成功骗了 44 分。

妄图对小数预处理然后做记搜，无法通过 1e8，没能骗取更高分数了。

赛后听说方程可以去掉若干因为有的元已经被解出过，胡乱分析就 3n 了，可能这就是最后一档只有 5 分的缘故把。