CSP-S 2025 游记

无法理解去年 NOIP 后居然没有退役。

14:30-18:30.

开场读了一遍题。全部想假，T1 以为全部丢进去贪心，T2 以为是以前做过的类似题要超级源点，T3 简单搓了一个不知道怎么处理的充要条件，T4 排列计数 dp 一眼做不出来。

先做 T1，发现过不了样例，发现贪心假了。后面不知道什么时候想到反悔贪心，此时已经 1h+ 了，已经有点红了。

T2 写完一版发现过不了样例 4，才发现读错题了，他不是要求第 $j$ 个加入的乡镇而是选择第 $j$ 个乡镇加入。于是总感觉脱不开 $2^k$，以为这玩意不对，数据分治写了 $O(2^k m\log m)$ 和 A 性质。

哦不过赛后发现的确这么搞不行，好像每次加入必须归并......

T3 搓出的充要条件什么子串 $y$ 的位置不同是不可能的，然后如果用 $i$ 替换则必须满足其中间不等的部分和询问不等的部分完全相同，其次 $i$ 必须是询问的子串。然后瞎写了个 $O(nq)$ 的哈希，结果大样例都跑得动，好像是因为判掉了很多串长不相等的情况。且通过了样例 4，但是样例 3 WA 了其中的一组询问......调试无果。

T4 写了状压。

$100+[64,72]+[0,50]+20=[184,242]$。

感觉又出现了去年 NOIP 场上做 T2 时越来越乱的情况，又是 T2 造成的。

这个分数区间稍微折中一下可能与去年完全一致，幽默。

准备最后一舞了，NOIP 2025 rp++！

upd：$100+56+45+24=225$。T2 莫名卡到了 $56$。