2024ICPC南京站游记

省流：选了个好赛站混了个正式队前10，然而被dls等一众打星队吊锤。

大概是最后一场以选手身份参加的xcpc了（如果能去成ecf的话另说），水篇游记玩玩。

背景

本来不想来南京的，因为高三在南京曾经干出过3题的超级黑历史（虽然当时主要是不想学whk跑出去玩的），这个心理阴影和debuff实在太重了，但是hyw说要带我们去看剧，以及一套诸如rp守恒之类的说辞最后还是去了南京。

本来也没打算打出个多好的成绩，整个大学阶段除了打出过一场ccpc的rk3和一场香港站的rk3（两场都是线上）以外其他都挺一言难尽的，5年换了4次队友，现在这支队去年还在合肥现了个大眼，算了下我们还从来没有在线下的比赛里拿到过大于6题的成绩。icpc最多允许打5年，今年是最后一年了，不算ecf的话也是最后一场了，这种比赛早就参加到麻了，就当是去旅游了，顺便还能蹭个剧看也还是挺乐的。

（喂我还有一堆ddl没赶完啊啊啊啊啊下个周又要天天熬夜了）

赛前看选手名单，正式队认识的外校人数 \le 3，看来自己是真老了，结果看到非正式队差点叫出声来，已经能想象到非正式选手屠榜的画面了。

day0

2号早晨8点的火车，6点就要起床，对于当代大学生来说还是太超前了点/fn

7点到了火车站遇到看起来比我更困的ckw，得知他凌晨飞机落地北京然后立刻赶到火车站/jy

上了火车，补觉，启动！

11点多下火车，南航离火车站近的一批，去酒店办理入住，和hyw会合去赛场报到，去了传说中“非常好吃”的南航食堂/se

下午开幕式，cjb居然是裁判长/jy，中文题面好评！

试机赛，怎么全是袋鼠题啊，哦B是个交互，还没读完题hyw就秒出了做法，迅速过掉。然后hyw过了C，ckw过了D，hyw过了E。

这时候大概还剩一个小时，难道能ak试机赛？（之前xcpc还从来没ak过试机赛）但是这个A怎么做啊，想了一堆乱搞策略但是全都既不会证明也不会证否。

先随便写一个交一发吧，每次随机选一个人沿着树跑一个欧拉序返回起点，直到只剩一个人……啊？怎么AC了？

（所以正解做法是什么啊，以及我这个做法理论上到底对不对啊qwq）

这下提前离场了，茶颜悦色，启动！

晚上hyw带我们看剧，我和ckw都是剧场经验仅限于马兰花开（注：你T学生必看）的剧场萌新，ckw看起来至少搞懂了剧情和人物关系，然而我到最后连一共GG了几个人都没搞清/qd，大概是因为剧情的时间线是跳跃交织的，到最后直接放弃理解剧情改成纯看场景看着爽了。

晚上焦虑到睡不着（喝奶茶喝的？），干脆看了会比赛，从2比1看到2比3，这下更睡不着了/ll

day1

跳过细节直接进入比赛。

开场正着开题，怎么又是袋鼠，看了看不会，队友倒开，怎么是计算几何，跳过，跟榜，一看有人过了E，遂开题，过掉。这时候hyw说D是简单nim（伏笔），我说还没人过你要不再想想，答曰抢个一血岂不是很爽，遂写之。过了一会说怎么越写越觉得不对，怎么先后手地位不一样，我拿来一看这不妥妥得上超现实数，关键我们没人会维护那种带有 \{0|0\} 的东西（原版超现实数定义要求左集合严格小于右集合，体现在博弈论上要求每走一步都会使自己面对的局面严格更劣），遂放弃。这时候已经过去了半个多小时，然而只有1题，其他题也没编出个做法，急急急。（赛后想想这题每走一步其实几乎是会使局面严格更劣的，只有一种特例是一个格子两人都可以无伤地走，这样对应 \{0|0\}=+，而两个 + 会抵消，因此可能也可以维护，然而具体细节到现在还没编出来。）

这段时间我和ckw一直在各种题上反复横跳，最后去开B题，先pass掉若干贪心做法之后感觉要在每一步记录可能的剩余前缀长成什么样子。后来发现因为一定形如 0101... 或 1010...，假设把前者用正的串长表示，后者用负的串长表示，那么每个位置所有可能剩余的状态一定是一个区间内的全部奇数或偶数，而每加一个字符区间要么左移1要么右移1，要么是通配符的话会左端点 -1 右端点 +1，于是就做完了。事后得知不少队被卡在这个B上，还喜提诈骗题之名，感觉赛时能迅速想出做法多少还是沾点幸运。

接着去开交互，看了一会说点分就完事了，二叉树这个性质会让每次只往一边递归。这时候感觉已经写累了（这才哪到哪）于是扔给了自告奋勇的ckw，叮嘱了一番细节之后去看C。

这时候旁边hyw说J似乎不难，讨论了下最开始以为要枚举三元环，后来发现一个点是固定的，其实枚举一条边就行了。正好ckw说G的点分还有点难写难调，还WA了一发，于是先让hyw写J，过了之后再去调G，结果过一会传来ckw的大叫“woc交互忘记输出感叹号了！”

接着看C，感觉这题跟今年推研机试的C有点像，那个题是一个从上到下dp的平方算法，想了下这个题似乎也可以从上到下dp，然后注意到从 f(x,i) 转移到 f(y,j) 对于每个 j>i 而言都是一样的，遂前缀和优化之，于是就平方了。写写写，在打错了几次dp转移和组合数的式子之后过了。

然后是K题，hyw说貌似把每一段拆出来从左往右贪心就行了，如果放不下怎么办，再从右往左扫回去调整。感觉貌似挺对的，ckw表示这怎么可能难道不需要dp吗，又给他推了一番之后表示好吧也许你们说得对，于是过了。

这时候还有两个小时，已经6题在手，优势在我！ckw和hyw去推I，推来推去得到一些容斥之后多项式的东西，于是开始打NTT，打完之后信誓旦旦地说再有10分钟就能写完。结果就开始了噩梦般的调试，具体过程由于我没跟着推这个题就不详细展开了，总之看上去很痛苦实际上一点也不轻松。我看剩下的题貌似只有F可做，是个凸壳/李超树维护dij的东西，至于M虽然也有人过但完全没有开的欲望（事后听说M可能反而比F更好写啊啊啊）。但是他们在调I我爱莫能助，眼睁睁看着时间来到封榜，最后没办法先打印出来我和hyw肉眼看下代码ckw你先去写F如何。最后观察各种输出调试终于找到了问题所在，过掉I的时候大概还剩50分钟，F能创造奇迹吗？

不得不说ckw码力和手速还是给力的，还剩20分钟过了编译，然后样例没过开始调。（此处省略1000字心理描写。）我上了个厕所回来还剩5分钟，一边盯着大屏幕上倒计时跳动一边看着ckw调过了样例，删掉注释，提交……WA。好吧，大家都尽力了，比赛结束。

讲题没听，跑出去买茶颜了，回来看颁奖，得知5题就能有AU的时候还有些小激动，因为这意味着这场大家过题数都不太高，我们7题可能有个还算不错的位次。结果这时候突然要先把AU颁完奖再滚榜，hyw上去领个牌牌回来，然后就到了紧张刺激的时刻。

（此处省略1000字心理描写）最后看到队伍定格在rk14，正式队rk8还是挺开心的，毕竟已经是线下打xcpc的最好战绩了。正式队有且仅有前三名是8题，还有些小遗憾毕竟F可能就差一点，不过最后算了下如果过掉F也只有正式队第4也就释然了。当然最后的重头戏还是dls与jly的巅峰对决，最后恭喜dls在同为11题之下以罚时优势胜出！当之无愧中国算法竞赛届最高的山最长的河orz（最后前5名都是打星队而且都是9题以上，太可怕了……）

然后就没了，后面高高兴兴地吃完饭坐高铁回学校（我不要面对ddl啊啊啊啊啊）

总结

其实也没啥好总结的，最大的收获大概是打破了多年以来线下不超过6题的超级debuff，以及重新找回了对南京这座城市的好感/xk

本来想把这篇当成算法竞赛生涯最后的回忆录，但是鉴于这次打得还行或许会厚着脸皮再要一个ecf名额吧，如果有的话那就强行再续两个月的在役时间，回忆录什么的到时候再说吧qwq