2023 联合省选游记 & 退役记

退役记请翻到页面底端的 后记 篇。

Day -1

不知道为什么这次提前两天就可以颓了，于是：

(Loopy 20*20 Hard)

和同学一起解了有差不多两小时。

晚上看了场电影，打了会块。

Day 0

不知道为什么这次不能颓了。

早上和下午都在对着 QOJ 的模板题单刷板子。多项式系列模板卡常差评

感觉这次是模板写得最顺的一次，甚至写了文艺平衡树。

晚上实在没什么事干，开了个 50*50 的 Pearl，结果推了两小时都没整完：

(Pearl 50*50 Tricky [Allow unsoluble])

临考倒感觉很轻松，比去年好多了。

Day 1

白板上密码写得有点潦草，输错了两次

T1 没想到有那么简单，第一眼没发现答案一定是段区间。第一想法是将所有区间按右端点排序，然后判每个右端点能否到达。

写了一会儿发现假了，改成按左端点排序并记录每个区间能到达的最左点，用线段树优化，写完后差不多已经过了 45min。

然而写完线段树后测大样例发现 RE 了，查了半个小时错才发现是叶子 pushdown。全部搞定后差不多 1.5h。

开看 T2，首先想到选出的点集一定是个联通块。想到分成边双，这样如果一个边双内选了两个点那么整个边双都必须选。枚举联通块大小 \(d\)，大力分讨 dp，容易发现转移时大小 \(<d\) 或 \(>d\) 的子树的选择唯一确定，\(=d\) 的子树最多只能选一个。

这个已经与正解很接近了（赛后发现改成点双圆方树就是对的，不知道边双对不对），然而感觉写起来很恶心，就先去干 T3 暴力。此时已经过了 2.5h。

T3 很快想到 \(O(n^2m)\) 的暴力（树形依赖背包）与链的 \(O(nm \log n)\) 暴力，有 28 分。其实再想想很容易得到 \(O(nm \log n)\) 暴力甚至 A 性质的部分分（这样有 62 分），但是场上太紧张了脑袋空空，什么都没想到。

T3 的暴力写了 0.5h，然后写了 1h T2，发现怎么都调不出来，紧急开写 T2 的 25 分暴力（还差点没写完），最后在结束前五分钟写完了。

由于策略问题暴力分完全没拿满，垫底了。

感谢教练的关心与劝慰，没有影响到第二天的发挥。

比赛归比赛，Puzzle 还是要接着推。

由于 Pearl 太大难以生成具有唯一解的题，因此开的时候选了 Allow unsoluble（可能有多解）。结果推到一大半时剩下的提示太少，几乎推不动了。

然后我直接钦定规划剩下插头之间的连接方式，再照着这个方式构造，竟然成功了（可见多解有多么离谱）。

(草图)

(Pearl 50*50 Tricky [Allow unsoluble])

推完后看了看 CMD 的一篇决策单调性优化的博客，就回去睡觉了。

Day 2

这次没输错密码

粗略扫一眼题面，T1 T2 似乎都是博弈，T3 是神秘数数题。

T1 的数据范围超小，看起来是大模拟题，就先什么都没想写了个记搜，很快发现环的情况不管怎么判都是假的。

之前好像见过类似的题，但是不太记得了而且这题需要算步数。先写了个拓扑排序，显然不对；再试试 Dijkstra，还是不对；最后试着多做几遍拓扑排序，每次用环上必胜的点作为起点，发现能过样例（虽然这也是假的）。

优化一下变成 \(O(T(nm)^3)\)，样例有点卡常。此时已经过了 2h，想着 CCF 往年数据强度就先不管了。

时间不太够了，开始争取 T2,T3 暴力。T2 很快发现是图论题，在 Bob 的两个数间连边，就是要求给每条边定向且每个点的入度 \(\leq 1\)。

显然若有解，每个联通块内边数不超过点数，于是只可能是树或者基环树。这样可做性质 A。

基环树的树部分定向是唯一的，环定向只有两种。统计环上 Alice 两个端点都能选的边数，枚举其中选择左边点的边数量即可。这样可做性质 B。

树的定向有 \(siz\) 种，分别是以每个点为根的外向树。看似要换根 DP，仔细想想不用。对于 Alice 的一种选择方案，考虑计算 Bob 选择每个根的共享。对于一条边，若其指向子树，则会给根定在子树外的情况 \(+1\)；否则会给根定在子树内的情况 \(+1\)。这样可做性质 C，同时可以树形依赖背包（\(dp_{u,i}\) 表示给子树外 \(+i\) 的情况下子树内最小值的最大值）获得 \(O(n^2)\) 暴力。

性质 D 不太会，先开始写。光是基环树的部分就写了 30min，测一下性质 B 过了。然后写树的 \(O(n^2)\) 暴力，结果后面的点怎么都过不了。

这时离比赛结束还有差不多 70min，没什么好办法，赶紧开始写对拍。造树的数据怎么都拍不出来，最后发现是环长为 \(1\) 或 \(2\) 时要特判。

调出 64 分后还有 40min，开 T3，发现什么都不会，直接输出 1 0。

感觉 T3 没什么办法拿分了，再回去写 T2 性质 C 的 8 分。写完离比赛结束还有 15min。

实在没什么事可做了，突然想起 T1 的时间还很卡。马上想了一个办法：只提取所有有用状态，可能会快很多。迅速把假掉的记搜改成搜索所有有用状态，测一下样例没挂，就不管了。

后记

任何故事都有结局，无论是喜剧还是悲剧。

Day1 倒是一分没挂，D2T2 也一分没挂，但是 D2T1 挂成了 20pts。

奇怪的是，民间数据上 D2T1 都是 70-90 分左右，并且按这个分是能进队的。

数据出后很快就找到了原因：没有判两个红棋走到同一个位置不合法，85->20。

首先我承认我有疏漏在先。但客观地来讲，在一道以模拟为主，细节繁多的题目中有一点样例检测不出来（而且还没法对拍）的疏漏不是一件小概率事件，并且我的代码只有在两个红棋相邻且被密封的情况才会出错，在一场能决定大多数人去处的重要比赛中，不应该在大部分测试点都放入同一个 Corner Case。

不过这可能也不能全怨出题人，OI 赛制本身就决定了它是一个随机性较强，波动性较大的比赛。从某种意义上来说，这和 2022NOID1T1 那次事故的性质差不多。

然而我就是这么“好运”，两次事故全在最重要的决赛碰上了。

不管怎么说，事情已经过去了，长达四年半（真正有效的可能只有三年）的 OI 生涯终于结束了。

感谢一路陪我走来的学长和学弟们，感谢为了信息竞赛呕心沥血的各位教练。

幸而这四年还是做了许多有意义的事情：

学习了许多算法，做了许多题。当年正是算法的精妙引我走入算法竞赛的大门；各种题目使算法千变万化，让它们结晶成精密的艺术品。

拿到了一些成绩，证明了自己的实力。尽管结果不尽人意，过程才是最重要的。我最骄傲的成绩有 2021NOIP 场切了 T3，2022NOIP Rank1（虽然是因为 T3 的水数据），2023WC Rank1。现在想想，成绩只是个荣誉，都是次要的。

参加了许多场比赛与交流，认识了许多优秀的人。思维的碰撞让算法竞赛永葆活力。从我个人的角度来说，有幸在校内结识了许多大佬，大家一起探讨了无数有用或者感兴趣的东西，交流互鉴让我们一同成长；外出学习交流比赛的经历也很宝贵，虽然很遗憾去年没有结识多少 OIer，今年也再没有机会了。

学习了许多感兴趣的知识。我尤其喜欢组合数学，也写了几篇相关内容的学习笔记，生成函数那一篇几乎包含了两三年来我知道的所有相关知识点与技巧。还记得坐在屏幕前推式子的每分每秒，做自己喜欢的事总是幸福的。

出了几道自认为挺有意思的私题，虽然大部分都是计数题。希望它们日后能具有应有的价值。

回忆就到这里为止吧。

从今天开始，我就正式退役了。不过退出 OI 不等于退出算法竞赛，Atcoder 和 Codeforces 的比赛有条件我还是会打一打的，文化课整无聊了也还来做一做题，闲下来的时候会修补一下以前写的文章，可能还会写几篇总结性的文章。感兴趣的东西还会继续研究，有时间的话可能会看看集训队论文。

QQ，洛谷和博客园也会定期上的，不要当我消失了啊。

说到洛谷，在这里打个卡，毕竟攒了两年半啊。

那么各位，再见了，希望我们能在两三年后的 ACM 赛场上重逢。

致本校的省队选手以及未来将成为省队选手的各位学弟们：我很遗憾没有达到应有的高度，未来就在你们手中了，祝你们的竞赛道路一帆风顺。

最后，致所有人（也包括我自己）：

一名受命运安排而退役的 OIer

2023 年 4 月 15 日