ICPC2025西安邀请赛 游记

Day1

不知道是不是因为什么奇怪原因，热身赛和正赛是放在了同一天，早上赶了个早八去热身赛，小困

热身赛的题目出得很难，好像都是金牌题难度，DLH 口胡了一个 A 的 DP 做法感觉很对，但是没有调试出来，我在看 C，想了一个做法，先对树进行 dfs 序遍历，然后按照时间从小到大加点，在 dfs 序序列上建立线段树，线段树的每一个节点是一个平衡树，每次查询就在平衡树上二分，时间复杂度 $O(n\log^3n)$ 不知道对不对

然后就是半个小时的开幕式，好像开幕式还没结束人就跑完了，哈哈哈

10点正赛开始，开局我在看 I，DLH 找到了签到 L，上机写，写了一个暴搜，叫了一发 wa 了，I 也是个签到，很容易能找到其实第一次之后就是有规律的，我就写了一发 I，结果因为一个小细节，也 wa 了，痛失一血。后面 DLH 给我说了一下 L 的题意，感觉思路没问题，改成状压枚举就过了，然后我回去看 I，发现错误，53分钟的时候也过了，开局签到不算很顺，一共 wa 了 4 发

后面 ZY 给我说了一个 G 的题意，我感觉可做，然后 ZY 和 DLH 去看 A，说 A 是个模拟题，顺着题意写也过了，对于 G，我发现每个 $mod \gcd(n,m)$ 同余的 $b[i]$ 对答案的贡献是相同的，所以可以一起处理，简单写了一下一发过了

写完后 ZY 和我说 M 是个图论，让我去看，我读了题意之后说就是裸的，用 BFS 找出王国的范围，然后树上差分就答案就好了，写了一会儿结果电脑死机了，喊了技术组搞了一下，期间顺便吃了个汉堡，感觉还不错。电脑恢复了之后 M 也是一发过

之后场上可做的题就还有 J 和 K，DLH 想了一个 J 的做法，交了一发 wa 了，这里讨论了很久好像都没有一个很好的做法，我看了一下 J 的过题数，感觉是一个猜结论题，就想到可能是 222333 这样子排，然后用拓扑找出起点，写了之后发现真的这样

写完差不多封榜了，现在 6 题稳银了，只要开一题有机会金，K 也是个图论，就开始想 K，K 的题意很难读，读了半个多小时读懂了，很自然的想出了 MST 的从小到大建边然后用拓展域并查集那样黑白染色，当发现矛盾就退出，写完之后 wa 了。又注意到没有考虑 黑 - 白 - 黑 这样子的情况，就加上了一条判断与之前最小边的和作为答案的情况，结果又 wa 了，当时距离比赛结束还有十多分钟，感觉思路很对，又去看了一遍题目，发现可能有重边，改了一下在第 296 分钟过了，由于比赛延迟了 10 分钟，最后就开始看榜，发现 K 后面交的人很多，我们罚时比较多，不知道能不能金，处于这种叠加状态还是好紧张的

闭幕式的时候没有讲题，直接开始滚榜，最后 1 小时大家在疯狂过题，名字一直在往上跳，滚到银牌区的时候，很多 6 题都变成 7 题了，而且罚时都在 1000 以内，我一度感觉要银首了，后面滚到上面看到我们排名第 39 前面还有两个打星队，就知道有金牌了，好激动，拿下了学校在 ICPC 赛事的第一块金牌！好梦幻

虽然说邀请赛金牌含金量不高，但是也是金哈哈哈

总的来说，这次能拿金牌取决于这些因素：赛站大，金牌数量多，强队少，还有作为一个图论选手，出的题我做的很顺，当然也离不开团队配合

希望能在接下来的南昌邀请赛有一个好的发挥吧