ICPC2024 成都赛站 游记

前情提要：CCF CCSP 2024 游记。

Day 0

中午从义乌机场坐飞机来到成都。在成都地铁上坐了两个小时，感觉身体已经不是我的了。到达酒店之后和队友前往附近的一家商场，在众多店面下选择了一个高配萨莉亚。

吃完之后发现商场有机厅，而且有两台舞萌两台中二，还有 19.99/20pc 活动。检查随身物品发现有手套，遂出勤。最后在四川舞萌上 1pc 就十血通过了四川金曲超熊猫。

最后是骑单车回酒店的。酒店有洗衣房提供，被汗浸湿的衣服可以直接送洗，感觉已经比很多协议酒店牛了（暴论）。

Day 1

仔细阅读了赛站群一直在复读的公告。前一天本来以为是在学校内部比赛，结果发现是学校外的一个体育馆。

报到后吃上了盒饭。从菜里面吃到的两三粒花椒就够我喝完一瓶水，广东人还是不太适合吃辣。

一点钟作为第一个过安检的选手进入赛场，一进大门发现左手边就是赤橙黄绿蓝紫和传奇打星队。感觉座位随机的还是太深刻了。

热身赛喜提 A 和 B 的一血，最终喜提 rk2，排在 jls 后面。尽管热身赛上一些强队没能按时参加，但是这个成绩也确实带来了一些自信，起码在明天正式赛上还是可以和强队掰掰手腕的。

队友晚上都被约去吃饭了，遂骑单车去商场打舞萌中二。这一天手感有点差。

Day 2

8:45 成功进场。在入场前研究了一下俊杰老师提供的预测，发现想要出线就得同时战胜浙大、东大、中科大等一系列强校，而且只能有一个大学的容错，不过热身赛的自信很好的把这部分压力中和掉了。

和我同高中的学长过来和我寒暄，他和另一个同高中的学长同时保研清华，后续可能会尝试再组一个队伍打 XCPC。赛场上和我同高中的还有一个实力应该比我强的学弟，不过由于少年班的原因在大学和我同级。

时间到了 9:05，比赛也是正式开始了。

剧透注意：接下来的部分可能包含题目做法。

6 分钟签了 L 之后，队友跟我大致讲了 G 的思路，我在韦恩图上分析了一下，感觉八种情况都是可以取到的，简单的构造了方案证明之后就启动了。提交后发现 WA 了，再次检查发现没有加入 0，加入后喜提 AC。此时时间来到了 15 分钟。

在 G 通过之后，A 题出现首杀。我自己看过 A 题，在首杀这一信息的提示下，我迅速想到了构造方案，在 23 分钟一发 AC 跟上了榜。

此时 I 和 J 都出现了一血。此时队友已经想到了 I 的一个足够优秀的做法，而 J 由于题面太长还没看。I 相对而言比较好写，而且错点比较少，36 分钟时一发过了。

此时我们终于发现 J 是一个很简单的前期模拟题，在进行一些细节确认之后，在 49 分钟时一发过了。

我们在此时成功积攒了罚时优势，dls 此时一血通过了 B 和 E，队友也受到指引，发现二者确实都是比较中等的题目，但是细节比较多。B 题相对而言比较好写，不过由于队友是从 E 开始看的题，所以在更早的时候给我提供了换根 dp 后差分的思路。我在实现过程中意识到换根 dp 需要计算数组除去某个位置的乘积，而考虑到出题人有可能恶意卡逆元，所以最后写的还是前后缀方案。另外，考虑到这一题样例实在有点水，我选择把 dp 数组全部输出并一一核对，直到和期望情况完全符合为止。

谨慎换来的筹码逐渐叠加，在 82 分钟提交 E 题代码时，我也完全没想到可以一次通过。

随后的 B 题相对而言比较轻松，在 98 分钟一次通过。队友告诉我 K 本质上可以弱化成一个流问题，但是复杂度非常玄学，目前可能需要换上一个更为稳定的匈牙利算法。于此同时，D 题恰好出现一血，而队友提到可能可以通过魔改 sort 的 cmp 函数实现排列排序。我选择和队友对 D 进行了一通分析，最后发现对于两个排列，只需要通过 RMQ 取到某个值域上最靠左的三个位置就一定可以实现比较。在写完代码通过样例后，为了保险起见，我逐个检查了 n = 9 的所有情况，并成功找到并修复了一个致命错误。最后也是在 151 分钟时一发通过了 D。

此时我们作为 8 题队伍，罚时仅有 480 分钟，而紧随其后的队伍对应的罚时则是 610 分钟。在评估罚时情况后，我选择让队友尝试 K 的匈牙利做法，而我在剩下的题目里面寻找稍微可做的一道。半个小时后，队友发现匈牙利做法调不过去，于是我趁着队友重新进行证明的时候抄写了一个费用流板子。在抱着孤注一掷的想法后，费用流版本的代码最终在 207 分钟提交，并出乎意料的通过了。

我们此时对应的状态是 9 题 747 罚时，虽然这个成绩无法和清北队伍抗衡，不过确实成功和其他高校甩开了极大的距离。考虑到此时的操作空间比较自由，我让队友开始想 F，而我开始写 C。

比较遗憾的是，在封榜后，队友的 F 虽然猜到了决策单调性和 wqs 二分，但是在 dp 细节上并没有完善；我的 C 在最后也没能跑出“三步内必然可以确认”的性质。封榜后没过题的问题还是没有得到充分解决。

随着 296 分钟的绝望提交后，比赛也到达了尾声。

剧透在这里结束。

在得知只有浙大在封榜后到达 10 题，并且我们以 9 题和罚时的绝对优势拿下校排第四时，我在长时间的恍惚后，想到的反而是在去年赛站中由于罚时爆炸错失的若干机会。我们虽然没能在本站实现 n+1 超越大部队，也没能在封榜后通过题目，但是至少在罚时上验证了代码能力和准确性的大幅进步。希望在后续的赛站中成绩可以越来越好吧。

随后和其他队伍进行交流，发现很多队伍实际上写完了 F，但是由于精度等问题没能通过；还有一些队伍在 E 题上不够谨慎，没考虑到对 0 求逆元的问题。如果 F 的精度没有卡的太死，或者 E 没有卡 0 求逆的问题，那么我们最后的排名会掉到多少，就不是我可以决定的了。只能说运气也是 XCPC 很重要的一环吧。

另外，晚上骑单车去商场打舞萌中二，最后还是没有用完 20pc，把剩下的 2pc 投到舞萌机子上就走了。

Day 3

本来下午一点半起飞的航班调整到早上九点，只能凌晨打车前往双流机场赶飞机。

广州真的比成都热很多，感觉不如再回成都待几天。

最后，感谢成都各方面的负责人为这次 ICPC 做出的准备。ICPC2024 成都无疑是迄今为止我参加过的区域赛中体验最好的一次。