2024 NOIP游记

· · 生活·游记

省流：AH 高一第一没了

Day -5

AK NOIP提高组真题

Day -2

水整体二分

嗓子有点疼

Day -1

水可持久化Trie、三分

Day 0

试机。

八中的硬件设施一点没变，只有键盘很流畅。

见到了若干初中校友。

预计代码长度上限：1.5K+2K+2.5K+5K=11K，显然是写不完的。

Day 1

8:25 才让进机房，8:35 才下发密码，为什么不加时？

拿到密码先花 10 min 看大致题意，T1 可能把 01 串分成若干段贪心，T2 n\le 10^9 可能有某种通式，T3 是超难的树形dp，T4一看我只会 dfs 序 \mathcal{O}(nq) 每次选 k 个连续数求 lca，1G 的空间大概又要转化一下再用线段树合并什么东西，或者考虑每个点对询问的贡献偏序数点。

8:40 看T1，固定了一些位置把两个串划分成若干段，每段可随意排序，求最大匹配。想了几个贪心，比如将可排序的块先排序、尽量先匹配固定的位置，但都没成功实现，第一个贪心不对的时候有点急，最后那个假掉的贪心已经写到了 1h，于是想着先看 T2，大概是有一些数已经确定，还有一些二元限制要求方案。没错，二元限制不是给定的，而是让我们求方案的，那确定的数就只是为了判无解？

9:58 去上厕所。

10:00 注意到当 x_i \neq a_i 时，第 i 条限制对 x_{i+1} 的值不做任何约束，也就是说，相邻两个有限制的位置间，只有限制首尾相接才有可能不合法，显然要想不合法，只有让第一个 a 是起始位置的值，最后一个 b 不是终止位置的值才行，顺着这个思路 10 min 码完，此时已是 10:12。

再这样下去 T1 都写不完，于是我重构了一个正确的贪心（?）。若遇到不同的位置，同等情况下换一个 a 的字符和 b 匹配与换一个 b 的字符和 a 匹配显然是一样的，因为早匹配晚匹配都能匹配。但现在的问题就是有些情况不是同等情况，具体来说，就是当前 a 的块的长度和 b 的块的长度不一定相等，导致有一些字符本来可以匹配另一个串其他块中的字符但其被固定在了某一块中。这时换那个长的块中的字符过来匹配就行了，因为长块的多余字符可以匹配更多块，短块的多余字符就被限制了，简单实现可以 \mathcal{O}(n^2) ，稍微改一改可以 \mathcal{O}(n)，只要寻找要换过来的字符时想办法跳过不可能和要匹配的字符匹配的位置就可以了。

20 min 不到码完,此时已将近 10:30。

测了一下大样例，怎么跑这么慢？于是测了一下循环次数，3e7 ! Why so much? 不过改了一段代码，就降到 1e5 级别了。

稍稍休息一会，把 T4 dfs序暴力打完，大概 11:00，感觉 T3 正解码量上天于是打点特殊性质。

一开始读错了题目以为边之间形成的是有根树，遂浪费20 min，然后一直在想 k=1 的dp，又浪费25 min，然后突然想到一个点与其父亲的边只会连向一条儿子边，因为不遍历完邻边不能回溯，这相当于将儿子边重排，且各子树独立，于是 k=1 时答案就是 \prod \limits_u \space (deg_u-1)!，也就是度数减一阶乘之积。一条链时只有一种连法，于是思考菊花图，发现（又过10 min）其相当于把所有边重排但只允许关键边第一个，去掉首尾都是关键边的方案数，即 k\times (n-2)! -C_k^2\times (n-3)!，考场把 n-3 写成 n-2 又调了 5 min。写到这里已经 12:20 于是在 T4 链和 T3 k=2 中决定想 k=2 的容斥，然而以我的速度，25 min 过去了还不知道哪些树是重复的。

此时一想，T4 不是整体二分？不过一开始的想法是 1G 怎么可能是整体二分，但恰好给了可以写整体二分（性质A）的部分分。遂没东西写了，本来 T4 还能多拿一点性质 A 的。

于是这下只有 100+100+40+32=272 了。

出来一看，Monomial T3T4 特殊性质拿满了有 300 来分，hjq A了T4十分强，还有人在叫苦 T1 怎么比 T2 难。浪费了好多时间，我还是太菜了。