2026 联合省选

IvanZhang2009 · 2026-03-08 16:43:11 · 生活·游记

noip 是 321，获得了 JS-007。试机下发了滚木，何意味。

3.7

三十分钟把 T1 过了。这么难的。

T2 想了一会发现可以往前插字符，记一下比几个后缀大就好了，是不是 O(nm^2/w)，全对。？

写了一个小时发现还要记一维 lcp，多一个 n。想了好一会儿发现不太好修正确性，于是改了好久改成不 WA 的了。测了一下大概只能跑 75，而 T3 看上去有一堆部分分，而且只剩两个小时了，遂放弃 T2。

T3 上来先把 B 性质当 3 个不动点写通过了样例，觉得应该过了，然后发现别的都不太写的明白，拼了 m\le 2 和 2^n 就摆烂了。最后十分钟发现 B 性质被改成过不去样例了惊险改完，但是出来发现好像没啥用，还是 0 分。

我是蛆。

玉玉正了半天。

3.8

发现不会做 T1，想了想瞄了眼特殊性质 p_0=0，想了一下然后会正解了。结果发现我写了五分钟快写完了考场里还有 0 个其他人在写代码。？

T1 总共花了大概二十分钟，中途还改了改 checker，然后扔了。

然后奋斗一下 T2。发现好像没什么部分分，想了一下 k=3 会做了，写一下，写了半个小时。

然后一直在想 k=4,5，虽然没这分。主要的考虑是 T3 一看就是最后留点时间研究一下，不适合把巨无霸 T2 直接扔掉。想了半天完全不会做，发现如果按归纳的想法可以让每个连通块度数 \le 2，然后发现环可以变成链。本来以为比较最简形式了，结果手玩一下发现 5 链竟然可以变成 2 链？？？然后观察了一下这个变换的形式大概是 1245，2345，1345。这么深刻的。？

大概就是可以花费 k-2 个废物点，来反转一个三元环，大概要求反转次数是偶数。然后再根据 k 和 \lfloor\frac{k}{2}\rfloor 的奇偶性找点类似度数奇偶性和边数奇偶性的不变量，大概可以编出来第一问。

到了大概快两个小时的时候过了第一问的样例。

然后发现几个问题，两个不重叠的三元环很难找 k-2 个废物点，然后这个操作次数也是很炸的，因为至少要 6 个操作来反转两个三元环，但是我的 k=3 看上去大概是 \frac{n^2}{4} 量级的。

然后玉玉正了好久不知道怎么写构造。后来发现如果写反转四元环大概是简单点（n-(k-2)\ge 4），操作次数只有 4。在图边数为偶数且度数为偶数的情况下，我发现可以用缩四元环的操作来缩偶环，即反转 1,2,3,4 的环，把 p 环变成 p-2 环，操作次数 4。那至少是一个 n^2 量级（两倍限制）的做法了。对于奇环还没想好，感觉三元环有点唐，但是好像至少比较能写了。

然后发现这个找环好像有点变态，大概是可以提取欧拉回路？但是我好像不会啊？回忆了一下好像是什么 dfs 然后结束了加入序列，手玩了一个两个环的情况大概有点道理，然后写了半天，调调调，在三个多小时的时候通过了样例。调试的难点在于各种 n,n/2,k,k/2,m 的奇偶性的讨论很让人头疼，而且我特判了 k\le 3，导致 n 的规模一定很大，很难手算。最后我不得不相信我的欧拉回路和缩环部分没啥问题才有信心调下去，但是好运的是这两个部分还真没问题。

然后想了一会 T3 发现暴力有点杂，o_x=1 看上去完全不可做。如果是 2000 怎么做？是不是可以按长链排序，就能 O(n^2) 了？那为什么不把所有子树提前排序。欸怎么还有一档随机？那可能能过 o_x=0 的随机了，暴力预处理然后换根，对于 o_y=1 肯定是有单调性的！我记得我上了个厕所然后在 12:25 的时候开始写，不是很难写，半个小时写完感觉比较有信心调出来，但是很令人绝望的是我过了所有小样例然后挂大样例，一切的 n\le 10 都过了，但是所有更大的大样例全部都莫名其妙的 wa。中途发现暴力部分的排序老是写错，改了好几遍。

中途为了避免真调不出来我写了个 lca 来做 r=1，然后 lca 写错了，用 lca 输出调试信息还以为是找路径上第二个点写错了，结果浪费了十分钟。快速拼完 r=1 但是暴力还是 wa 的时候我已经准备认命了，结果突然宣布延时十五分钟，仿佛突然活过来了！

三十分左右我突然发现我的排序好像仍然不对！因为字典序的比较看上去是从大到小排序，但是 rk 是反的，实际上应该从小到大！改完一测竟然过样例了！瞬间真活过来了。

然后光速拼了菊花和 o_y=1（当时没发现这档分没结合随机），跑路了！

感觉 T2 挂分的可能性不低的！但是 day2 的标准分注定会让 day1 的蛆一样的发挥更容易弥补！

算了不想这么多了，成绩出来再说。

3.12