省选联考 2023 游记 | noip 发挥不完全，省选完全不发挥

· · 生活·游记

一生中最辉煌的时刻 是没到还是结束了？\ 这场无硝烟的战争 我胜利或早就输了？\ 当青春逐渐逝去 还有谁真正在乎着？\ 无声无息不知不觉地活着 又如何？

现在的我只会呼吸 找不到理由存在\ 一个平凡的人物 就这样消失在人海\ 无论我背后的故事有多么 惊涛骇浪\ 人们还是像往常一样地 忙碌着来往

—— 《战役》

前言：noip lost 100pts。

Day -?

被甲流击中了，回家躺了 10 天。训练完全停摆。

中途听说沙东省选支持 Linux 了，不由得悲从中来。同一个赛场，为什么 noip 不给 Linux？如果 noip 给 Linux 的话我也不至于丢那 100 分啊！！1

很唏嘘，如果因为这丢掉的 100 分而丢掉了省队，也是很合理的罢（悲

Day -1

中午醒来，发现 CCF 公布了省队名额。

河北省队有整整 15 个，而 SD 却只有 13 个省队名额。再看看隔壁 JS，只有 12 个省队名额，更为地狱。这真的合理吗？

然后机房众人即兴讨论了一下省选事宜，去除三个不动点和女队，再去除大家觉得完全没戏的，剩下 20 个人争夺 9 个省队名额，相当残酷。这 20 个人的意思是，随便选 9 个人组成省队都在可接受的范围内。\binom{20}{9}，很符合我对竞赛大省的想象。

顺带一提，我是光荣的吊车尾。

你说得对，但是不如休学去泰国做变性手术，归来即为下一任女队！！！！！

感觉打 OI 就像追番，以在役选手的身份完整地度过了两年高中生涯就是 happy ending；而如果中途因为省选之类的原因寄掉了就烂尾了。如果你有足够的气魄，可以法效二营长，自己将故事硬圆回来。但现实是，大部分人追的番都是烂尾的。失败贯穿人生，未来是不可预知的，省队是虚无的。所以不如来享 D 类铜牌福，一享起福来就发狠了、忘情了、没命了！

Day 0

和大家谈笑风生。

晚上试机+面基，众神归位。一号机房之于省选，就好比火葬场之于医院。

王好强和切队是情侣座/se，峰峰峰：这不结婚很难收场。

明天就是省选，想说但未说的，还有很多。但不管怎样，我都已经做到了自己能力范围内的最好。而人生充满未知与可能，决定性的分叉点有很多，眼前的联合省选可能都不算是一个十字路口……谁知道呢？省选并没有那么可怕，与省选对决，其实就是与命运对峙。所以还是那句话，自信即巅峰！

Day 1

倘若写出了你伸出的 T3

我一定无法回到 这不知孤独的 whk 了吧

你将线段树分治拍我脸上 在那二分下也诞生了阴影

加点给我看吧 关于这段省选的后续

直至抵达我们从未写完的 T3

省流：完全不会 T2，会 T3 3log 但是连只加点的部分分都没写完。如果把 3log 的树剖换成（静态）LCT 就是 2log 的。

以下是正文：

进考场，先打缺省源。打完缺省源就发密码了。于是开题。

T1 第一眼线段树优化建图，我再一看，哦，原来是贪心。然后我一个左边扫，一个右边扫，过了大样例。鉴定为人口普查题。

T2 第一眼转化成了子集卷积，然后就不会做了。看到数据范围有一档 n\le 15，然后才是 n\le 20，愈发让我坚信这两档分是子集卷积。

T3 一眼会了 O(nq\log n) 的可并堆维护贪心，数了一下竟然有 48 分。

飞速写完 T3 48 分，又简单想了想那几个特殊性质，感觉好做但是一时间找不到头绪，于是去写 T2。由于最开始转化成了子集卷积状物，忽视了极其好写的 O(2^nm) 模拟做法。然后写了一坨歪比巴卜。中途发现它那个样例水得要命，我 k=1 没有额外减掉 k=0 的答案都能过前两个样例。由于 T3 的部分分看上去极其刮痧，就又想了很长时间 T2 的树怎么做，捏了几个 dp 复杂度都升天了，感觉寄。

最后一个小时决定转战 T3，在走廊来回踱步了半个小时终于会了只加点（也顺带会了删点，因为只需要套一层线段树分治）。但是时间所剩无几，根本写不完！

下午吃完饭后找 tyy 验证了一下 T3 做法的正确性，发现自己是对的，同时把树剖换成 LCT 就是两个 \log 的，我越想越觉得亏麻了。就算是 O(n\log^3 n) 的也保底有 80 分。这下只能把希望放在 Day 2 了。

Day 2

钟声响起退役的讯号 在他生命里 仿佛带点唏嘘

noip 发挥不完全，省选 D2 完全不发挥。

如果我 noip 看到了那行致命的 warning，如果我果断地去开 D1T3……结局是不是会大有改观呢？但是事实就是我没有注意到 warning 和系统差异，因此 noip 275 -> 175；我 D1 和 D2 没有任何发挥，因此没进省队。遗憾啊，遗憾，我的 OI 生涯，就这样结束了。

还是写一下比赛过程吧。

顺次开题，T1 最开始只看了题意，以为是观察性质题，于是手推了一下，发现它的结构很烂。看到数据范围 n,m\le 10 才意识到是暴力记状态，转化成有环的有向图博弈。这种东西还挺典的，但是我完全没有触碰过这个话题。

T2 读完题“二分图”和“hall 定理”就蹦到了我的脑子里，然后数了数暴力费用流的分数发现最好能有 40，感觉相当牛逼，所以就心满意足地去看 T3 了，并没有往下延伸思考。

T3 最开始感觉有想法，对着那个式子拆了半个小时的贡献，最终拆成了与每个位置前面比它大的元素个数有关的形式，然后发现自己连第一问都不会做哎！puts("1 0"); 遗憾离场。

回到 T1，首先猜了一下记忆化搜索，剪掉重复走的转移。代码写了一坨，边写边吐槽怎么会有红色棋子不能重叠这种奇怪的设定。写的时候很小心翼翼，然后发现过不了样例。这才意识到记搜对环的处理完全错误，但之前一个小时都在搞记搜，所以思维一时间没有走出来，还在想怎么打补丁。

第一反应是粗暴地将步数也记录在状态里，这样就是一个有向无环图上的递推了。这个做法拿 55 分肯定是稳稳的，但是我不太想写。而且我甚至没意识到即使是这样子做，DAG 上的递推也应该反向拓扑排序，由已知的终末状态不断向前更新未知。而是认为这个递推完全可以把之前的记搜 dfs 改成迭代加深来实现（毕竟我之前已经写了一版 dfs 的代码了，所以潜意识肯定更倾向于复用之前的代码，就没有细究）。这对于我的判断的影响是致命的，第一点是错失了拓扑排序这一突破口，从此之后我再也没有往这方面想。第二点则是误判了代码难度，导致时间分配失衡。

接下来又冷静分析了一下（中途甚至还口胡了一会儿分层 dij 和 spfa），发现 dfs 的唯一缺陷是如果出边指向了已经走到过的结点，我们无法分辨这个结点的 dp 值是已经确定无疑的还是在等待审判。进而想到在回溯时处理这些存疑的出边，如果它们全都确定是必败的了就寄了，否则它可以赖到一个环上。但是稍微尝试着写了一下就发现这个想法完全落实不到代码上，因为这会破坏 dfs 的结构。所以我又捏了一个做法，先不重复走点 dfs 一遍，然后按 dfs 序倒着看，以此代替在回溯时处理不确定的结点。但是这并没有解决本质问题，因为 dfs 树对应的 dfs 序并不是一个有力的顺序。这里我又犯了一个错误是认为 确定 与 尚未确定 的结点是相对而言的，换言之我是在 dfs 的过程中才会分清哪些结点是确定的，哪些结点是尚未确定的。但实际上完全可以通过拓扑排序简单地剥掉一些结点，以此简化问题结构。

一时间没别的进展，眼看时间不早，选择把 T2 的暴力费用流写掉。写完 T2 后调了一小会儿，过掉了该过的样例。看了看表，竟然只剩下一个小时了？！我 T1 还一分都没有，相当惊慌失措。这个时候目标转为了先写出 T1 的 55 分。如前文所述，我写的是迭代加深+dfs，完全失败。最后遗憾离场。

Day 3

躺在床上睡不着，于是回想 D2T2，沿着二分图+hall 定理转成了树和基环树，基环树很好做，树的话转成了给边定向，大概会了 O(n^2)，之后就不会了。不过这样至少 B 性质的分已经解决了……有点难受，凌晨两点爬起来，对着电脑沉默了很久。

从上帝视角看，我 D1 应该梭哈 T3，D2 应该梭哈 T2，但是，这两道题的定位又与我考前制订的求稳的策略相违背，只能说，noip 丢的那一整道 T3 和不会 D2T1 就注定了我失败的结局。

老天爷确实给机会了，但是给我机会我不中用啊……