联合省选 2023 游记

· · 生活·游记

前言

NOIP2022 的爆炸（176 \to 69），导致了我在 3 月 30 日才知道自己可以去省选。

厦门一中初中去的只有初二的我和初一的 cjld(Register_int)，cyz(STUDENT0)，hr(houran)。zzp(狂风之息)NOIP 没有报上，痛失省选机会；初三的巨佬们虽然 NOIP 都考到了 100+，但是因为要认真备战中考，主动放弃了省选资格。

于是，思维还停留在提高（普及？）组算法的我，猝不及防地踏上了省选的征程。

3.31 / Day 0

上午

逃了一天学，一早就来到了厦门火车站。

在去福州的火车上，估计复习了四五遍模板的 lsh 高二巨佬在决战前轻松愉快地打起了东方，而我这个一遍都没有复习的被杀了个措手不及的蒟蒻竟然在看 lsh 打……

最终在 TSFH 的激励下我还是打了几个模板（tarjan、割点、点双）。

中午

酒店和 FJOI2022 是一样的，并且没啥新变化。放了一下东西就来到一家按重量计价的快餐店，比一中食堂好吃多了。吃完回酒店打了个边双和匈牙利的板子。

下午

来到福师大附中试机。鼠标左键单机时有时会判定为双击，差评；空格按不下去差评。随便刷了个蓝题就去打 florr 了（lv1 的新号）。

回到酒店继续刷题。然而一题都没刷就忍不住开摆 yorg&surf 了。

晚上

吃的和中午一样。晚上想好好写一写模板，但只写了一个树剖就累得不行，就没有继续写。玩了会游戏才意识到：不能再摆了，否则明天将会寄得很惨。于是拿出颓废利器小蓝本刷了一题。

22:15 睡了，满脑子都是 yorg.io 的城墙。

Day 1

考前

早餐自助。和 cjld 奶今天的题。“T1 大模拟，T2 计数，T3 poly。”我奶道。

觉得今天考试状态简直完美。坐等开题。

开考！

NOI 2023 好评。day0 好评。

T1 分明是黄题难度！但是为了求稳，我还是谨慎地写了 40min。9:10 过了大样例，感觉很稳。

此后通读了 T2、T3 题面。T2 果然是计数（笑），但是题目给出的条件很复杂，图上的技术对于我这提高选手显然也不好搞。T3 是树上的最优化问题，发现只要能 O(n^2) 解决静态问题就有 22 分，只要能 O(n) 就有 48 分！果断开 T3。

然而感觉策略很难想。其实是我一开始就入了歧途，考虑将优秀员工从小到大加入，后来又考虑从大到小。想了半个小时没啥思路，看 T2。

一眼发现 T2 有显然的 O(m\times 2^n) 做法（枚举 V'），果断开写。写得很顺利，10:00 就过了大样例。

此时还剩 3h 而我已拿到 125 分，感觉优势在我。按照 NOIP T3 的经验，试图思考树的部分分，可惜没有任何结果。于是重新捡起了 T3。

先从更特殊的情况入手：静态的特殊性质 C。容易想到把员工按 dfs 序加入。然后猜想一般情况也类似，结果——我得到了 T3 的 O(n^2) 贪心策略。

又发现复杂度瓶颈是一种支持合并和删除最小值的数据结构。我听说过 \log n 的可并堆，但是不会；又听过 \log^2 n 的启发式合并，但是只写过一题。

以上经过了 1h，现在是 11：00。考虑到时间充裕，我毅然决定重推启发式合并的算法流程。在 1h 内我经历了漫长的推导、Hack 和反 Hack 过程，最终写出了正确的启发式合并。

最后用 30min 给予了 T3 最后一击。大样例本地跑了 6s，希望 CCF 少爷机手下留情。随便检查和卡常了一下就结考了。

估分：100+25+48=173

考后

问了三个初一的和 lsh，他们大都打到了这个分数。hr T3 的策略似乎假了；cjld 和 hr T2 的枚举都是 O(2^m) 的；其他人和我估分情况完全一样。

我的超常发挥，我的极致状态，我的奇思妙想，在别人眼里，竟是如此微不足道，只是换来了“大众分”这个评价；听着 cjld 和 lsh 对 T2、T3 的激烈讨论，听着“圆方树”“线段树分治”“模拟费用流”这些我闻所未闻的算法名，听着 cjld“T3 的贪心策略很一眼”的暴论，我深感我的眼界之小、水平之低、和众巨佬的差距之大。

我的实力，如同刚刚凑齐第 10 张青卡；cjld，如同合粉失败数百次。装备上似乎差距不大，只有等级默默倾诉着差别。

中午在礼堂吃食堂，味道不如一中。吃完回酒店写了一道大码量紫题。

写完后觉得很累，遂放飞自我，到 cjld 房间教 cjld 入坑 yorg。然后被教练逼迫到健身房跑 1200m。

晚上依然吃快餐。写了 KMP 和 dij 模板又想开摆，于是入坑了 gartic.io，玩了一把（竟然榜一了）发现一点意思都没有，不如 digdig 或 yorg。

又刷了道小蓝本就睡觉了。

Day 2

考前

晚上做了个怪梦：省选 day2 cjld 切了 T1 拿了 206，我只切掉（只有蓝题难度的）T2 拿了 150+。事实证明我没有见过世面，天真地以为省选 D2T2 还会出蓝题。

早饭时继续毒奶。“T1 多项式，T2 构造，T3 大 DS。”

开考！

先看 T1。T1 是博弈论，但是考虑到 n 很小，可以考虑暴力设状态，无脑 dp。但是 dp 转移可能成环，于是想到将所有状态建图，再进行类似于拓扑排序的操作。我在草稿纸上详细列出了 dp 的状态转移和建图过程。

时间已是 9:00，我明白 day1 大家都和我差不多拉不开差距，成败在此一举，于是果断开写。然而写到 9:30 就发现情况太多写不下去了，而且复杂度分析 O(Tn^6\times\text{大常数}) 大概率过不了，考虑到“儒略日”的惨痛经历，我果断弃疗，转攻 20pts 部分分。这个决定被证明是正确的。

接着我通读了 T2 题面，纯暴力部分分给了 20 分，真好！特殊性质分也很多。稍微思考了一下性质 A、B，A 只需判定，让我想到了“连续进攻游戏”，但使用匈牙利算法只有 4 分（考场上以为能过 8 分，实际上显然不行），性价比不高，先不写；B 性质非常简单。果断开写 4^n 暴力和性质 B，轻松过了大样例。

然后觉得 T1 只得 20 太窝囊了，开始思考测试点 5~6 和 7~9。发现 5~6 是非常恶心的分类讨论，7~9 似乎可以用我的“正解”写个 dp。于是开写，但是困难重重最后不得不放弃。

此时大约是 11:15，我决定开 T3。什么？暴力分一分不给？我很快就想到了用一个套路的 dp 拿到 2 分（第一档第一问）的方法，但是中间调了很久，到 12:00 才调完。发现将这个 dp 稍微修改一下也可以做第二问，于是大约在 12:30 我拿到了 10 分。

最后半个小时先把 T2 的匈牙利写了，然后从 12:45 就开始认真地检查题目名称有没有拼错、有没有撞关键字。然后就发现，T1 的 Tie 打成了 draw！捡回 20 分。12:50 就无所事事了。

考场估分：20+36+10=66

考后

cjld 一出考场就激动地说：“我 T2 想出正解了！！没打完！！”我们都要他说正解。他用极快的语速说道：“先对原图建立二分图，转化成树和基环树，@#$%^&……”当然我们都没听懂，只是一个劲的膜拜。

问了一下三个初一的情况。cjld 投入所有时间肝 T2 爆炸，只有 10+[0,10]+0。cyz T1 写了迭代加深（orz）55+12+2，hr 忘了。

在去食堂的路上，我像播音机似的持续大喊“Ri 初一会 T2”，引得旁人侧目而视。

今天中午吃的是一中自己点的肯德基，比盒饭好多了。回到酒店收拾行李就匆匆离开了。到福州火车站时离开点还有一个半小时，先在旁边的快餐店等了会，写完了一张地理作业。三位初一的在按 NOIP2021 的规则报数。在车上我写完了截止到 day1 的游记。

虽然我们一直在试图活跃气氛，但相比省选时的其乐融融还是感觉少了点什么。尤其是当火车到达厦门时，当熟悉的背景音乐“12315，56751（音符）”响起时，一种压抑的空虚笼罩着我们。

那空虚，是别离 OI 世界、别离志同道合的 OIers 的感伤，是 whk 那无趣而世俗的世界的召唤，是 OI 的桃花源消失的滋滋声。

（当晚发现 D2T1 使用 y1 和万能头，喜提 -20，即估分 46）

Day 3 / 结束后

前一天晚上补一个周末的作业。

今天是一个平凡的日子，与上周四（那天晚上得知省选）一样平凡的日子。

只是下午的信息训练，当我打开电脑开始继续写游记时，我已经几乎忘记我的省选经历了。毫无疑问，OI 的世界已经远远离我而去，“桃花源”已经荡然无存。

出分阶段

考场估分 100+25+48+20+36+10=239。

云斗学院估分，可以看出 D2T1 的 y1 没有挂分，D2T2 的匈牙利拿了 A 性质的所有 8 分（预估 4 分）。但愿 CCF 也如此良心。

正式出分：100+25+48+20+40+10=243。

拿了初中部四个人中第一（cyz 238），可以说没有什么遗憾了吧。

扩展阅读

FJOI 2022

CSP 2022

NOIP 2022

cjld 的省选游记