49th ICPC南京站【游记】

省流

这是我们队 2024 赛季的第一站，阵容是我，BrotherCall 和大四神犇 snowy。

根据民调，我们队赛前预测南京是今年 ICPC 强度最高的赛站，依据网络赛的排名我们队也只能排在银尾。

最终 \text{rk}79 打银了。同时这也是我 ACM 生涯中第一块 ICPC 银牌，算是意料之中，但也充满遗憾。

总体体验还是非常不错的，而且意料之外地顺利要到了 jls 的签名和合照，算是让人永生难忘的回忆。

11.1 Friday

下午坐高铁从秦皇岛去南京，到南京已经晚上十一点多了，但还没吃晚饭，于是跟队友在酒店附近觅食，发现有一家还没打烊的火锅店，直接进去爽吃了一顿，凌晨两点多才睡。

11.2 Saturday

中午之前去报道，今年南京的衣服是袋鼠色系，衣服右胸前印的代码是欧拉筛，从颜色上来说感觉没有去年的黑白色系好看，但整体的布局风格还是挺帅的。

领完物资出来发现帆软有集赞活动，集到 68 个赞居然直接送机械接盘，然后ICPC南京群就直接变成了说说互赞群/xk/xk/xk。吃午饭的功夫，队友飞速集了远超过 68 个赞，但悲报是键盘已经被领完了，于是只领了一个 38 赞的蓝牙音箱，我领了一个 38 赞的筋膜枪（说实话我之前还不知道这是什么东西）。

下午热身赛

赛前发现我们后面几排坐的是打星队，一回头就能看到 qingyu，dls，zak 等众神，当时刚好赶上 jls 进场，直接冲上去要到了签名和合照，拍完合照那一刻瞬间感觉正式赛打成什么样已经无所谓了，来这一趟南京已经值了。

我预测赛题是 5 个历年的袋鼠题，结果是只有 4 个袋鼠题加一道签到，构造地图卡掉随机输出的那个袋鼠题被砍掉了，那组 hack 数据也被加到了原题目里，所以我上来交了一发随机直接喜提 Wrong Answer。

坏消息是这题的做法我们队都没研究过，最后一直基于一个手搓出来 hack 数据，魔改随机做法各种乱搞，但还是没搞出来，于是最终热身赛 5 个题我们只过了 4 个，大概排在 50 名左右。

11.3 Sunday

以下内容包含剧透，如果想 vp 请不要阅读。

正式赛。

开赛先找签到，随机开了几道题发现都不是，到了 10\min 看榜才发现最签的 E ，因为太谨慎了，所以写的有点慢，花了十分钟才写完，好在一发过了。

此时看榜发现 B, J, K 都有人过了，我去看了 J 题和 K 题，两个队友研究了一会 B 题，写了一个用栈维护的贪心，结果发现样例最后一组数据过不去，认真思考之后发现没有那么简单。

与此同时，我发现 K 很显然是把黑点隔开的段独立计算，但我误以为这需要用 dp 来做，发现很难优化，而且貌似有后效性，于是暂时放弃了去想 J 题。

发现 J 题比较简单，跟 snowy 讨论了一下，发现只需要先计算选了每个点之后直接产生的贡献，然后枚举第一个点选哪个， 第二个点从剩下的里面找个贡献最大的就行了。snowy 上机写了一会就写完了，结果因为 n, k 打反吃了一发罚时。

接下来三个人又分别想了一会 B 和 K ，发现都没太有明确的思路，于是只能看榜，发现开出来 G 题的队挺多的，于是 snowy 去看 G 题了。

看了一会 snowy 直接把 G 题秒了，每次问直径然后分情况讨论，每次把直径砍半，感觉非常对，然后我就上机开写，写了半天终于调过样例了，而且构造了好几个数据都很对，就直接交了，结果 WA 了。仔细思考后我发现每次问直径并不能砍半，这样问次数不是 \log 级别的，然后我和 snowy 讨论了一会发现要改成找重心的三个儿子分类讨论，每次问两个儿子，这样每次能把二叉树的 size 砍半，于是又改改改，改了半天，最后吃了两发罚时过了 G 题。

然后这个时候 BrotherCall 提出了一个关键结论， B 题的答案只跟 0 和 1 在的位置的奇偶性有关，snowy 受此启发手玩了一下猜到了一个巨大简单的做法，看了一眼榜，发现一血队伍开赛 7\min 就过了这题，于是便更加确信这个做法是对的，上机写了五分钟就一发过了 B 题。

连过两题让我们士气大增，排名直接冲到了前 60 ，我们发现再写一题就能直接冲到金牌区，而且还有一道过了 100​ 多队的 K 题我们没开，好巧不巧的是，BrotherCall 此时提出了 K 题的一个看起来巨大无敌正确的贪心做法。

感觉我们距离胜利只有一步之遥了，巨大的喜悦冲昏了我的头脑，导致我没有第一时间看出 BrotherCall 提出的 K 题的贪心做法的问题，而且我们两人分别对于一个做法写了两份代码交上去都 WA 了，这个过程中我一直坚信这个做法是正确的，直到我打印出来代码看了无数遍也没有发现问题，我才开始怀疑做法的问题，结果在最后半小时叉掉了这个思路，也想不到怎么改，snowy 开的计算几何 M 题也因为一种边界情况不知道怎么处理一直 WA，最后无力回天了。

赛后

本来觉得又要铜了，结果滚榜发现封榜之后过题的队不多，加上我们队 4 题罚时比较少，滚到我们上面的队只有两支，最后还是拿到了银牌。

事后发现 K 是个套路题，一个很套路的贪心。那么这种套路题做不出来到底是什么原因呢，是套路刷少了还是思维不够呢，我感觉都有。而且这个套路其实不难想，即使从来没见过最后也应该能想出来，赛时还是太不冷静了。感觉除了积累套路之外还是要狂训题来练思维，赛时因为各种临场效应，思维总是会被降一个等级，所以想要赛时打出 vp 的表现，思维还是要再提一个档次。

所以总之就是一个结论，还是实力不够，得多多加训！

最后放几张图