2025 ICPC 南京站

· · 生活·游记

Day -1

周五早上的飞机，落地后在酒店楼下吃了铁锅炖，豪赤！休息了一会儿我去南大找我的初中同学玩，有点远，地铁做了一个多小时，运气不好还下雨了。在校园里随便逛了逛以后就去吃饭了，吃烤鱼，聊天的过程中顺便了解一下他们的课程（由于专业相近，所以还白嫖了个计算机系统基础的课程链接），羡慕南大有这么好的课程体系安排！

Day 0

早上闹钟没听到，还是被队友叫醒的。吃了早饭直接去签到，参赛服好评，然后参与游戏获得一只迷你版袋鼠。骑电瓶车逛校园，十分惬意，刚好 30 min 还车，没有多付款。然后想着有点早，去食堂可以买点奶茶，但是发现餐券有效范围过小，于是就坐下歇着，开始摆弄袋鼠。

下午热身赛，竟然要存包（好像被说了，后来负责人和保安沟通了就不用了）。获得一只大袋鼠，开赛前又是各种袋鼠摆 pos 的传统，群里图片乱飞。热身赛果然都是袋鼠题，其中三道做过，于是很快地再次复现了出来。还有两道题我们分工，然后差不多都有思路，于是上机写。但所剩时间不多（由于一开始发现题目基本做过，于是去调 bash 了，所以没剩多少时间写题），最后这两题没过，打算晚上补一下。回去路上简单瞅了题解，发现思路都是对的，所以说是口胡 AK（。

开局良心签到，飞速通过。之后是一个象棋的简化版，想了一下发现只需要判断一步即可得到结果。然后我第一反应是直接列出所有情况，疯狂敲 if 然后 WA，冷静了一下直接循环枚举所有情况，然后又 WA，瞪了好久才发现有一个 dy 敲成了 dx。成罪人了 WA 了三发 1h 才过。

之后 Zlw 佬发现 F 是一个贪心加 bfs 的题，敲完一发通过。跟了一下榜发现 G,I 有一车人通过，但是想了想这两题发现我们三人都不会。佬提出我们应该多看一点题，于是开了 H，发现可做。

以下证明 SUNCHAOYI 是入机：

Zlw: 这道题我们可以先预处理出 f_{l,r} 表示这段区间内有多少个满足中间条件限制的数量。但是怎么快速处理出来呢？

Scy: 先不管前缀，枚举两个重复子串的同一侧端点，然后就可以把 border 转化成哈希判断是否相等的问题，用二分加个 log 就行。

Zlw: 哦有道理，那么相当于前缀就是等差数列的贡献，随便维护一下就好了。

Scy: 对，可以用差分代替线段树。

Zlw: 那两侧的答案怎么统计呢？好像和刚刚的过程有点像。

Scy: 前缀和就行了。

Zlw: 哎，那好像这题做完了。

Zlw: 啊呀，差分咋写来着？

Scy: 两次前缀和，阿巴阿巴阿巴！

证明完毕。prompt 正确，直接胡出来了。

然后就过样例了，差点忘记取模，然后提交！测了一万年，一发通过！

然后剩下的两个小时疯狂的在 G,I 之间徘徊，但是最后都不会，4 题遗憾离场。赛后在洛谷管理群里水，竟然发现他们打星队竟然和我们四题同构，疯狂吐槽为什么我们做不出 G,I 却做出了最后只有 50 个队伍通过的 H。

讲题，发现 G 题可以将两个参数分离，于是就可以简单贪心了，懊悔怎么没想到，但是转念一想过了也 Au 不了，又感觉还好（bushi。

滚榜，竟然意外的守住银了，在正是队伍中排 80 多名，就这样吧，SUA 题真的好难！

不知道还有没有机会打 EC，感觉离退役不远了，滚回学校学 CS 去了。

【赛后补题】

G 主要就是理解合并，即让较小容量和较大流速失效。将桶分别按照容量由小到大排序，记为 A，再按照流速由大到小排序，记为 B。那么也就是最后需要保留 A 与 B 的一段同样长度的后缀。当想要再失效一组容量和流速，发现水会漏完时，情况已经不优，因此对于一组询问直接二分答案即可。

I 是一个读题细节很多的 DP，读完题后需要意识到需要从后往前 dp。因此，设 dp_{i,j,opa,opb} 四维表示前 i 天剩 j 元，A,B 两人是否已经支付一次的最大价值。注意 j < 0 的状态直接设为非法，又由于需要从后往前，dfs 记忆化即可，代码竟然异常好写。

M 组合加 NTT 优化题，还是相当的不熟练啊，借着 AI 的理解又推了一万年。考虑 (P_i,P_{(i + d) \bmod n}) 为凸 k 多边形的一条边，则两线段右侧的 d - 1 个点失效，剩余的 n - 2 - (d - 1) = n - d - 1 个点需要选择 k - 2 个组成 k 凸多边形。

令 F_d 表示选距离为 d 的点作为一条边时的贡献，则有凸 G_k 边形的面积和的两倍 G_k 为

G_k = \sum \limits_{d = 1}^{n - 1} \binom{n - d - 1}{k - 2}F_d \\ = \frac{1}{(k - 2)!} \sum \limits_{d = 1}^{n - k + 1} \frac{(n - 1 - d)!}{(n - k + 1 - d)!} F_d

令 A_d = (n - d - 1)! \times f(d)，B_d = \frac{1}{i!}，则有

C_k = \sum \limits_{i = 1}^{k} A_i \times B_{k - i}\\ G_k = \frac{1}{(k - 2)!} C_{n - k + 1}

当然，还需要快速求出 F_d 的值，用叉积表示面积的两倍，则有

F_d = \sum \limits_{i = 0}^{n - 1} (x_i y_{(i + d) \bmod n} - y_i x_{(i + d) \bmod n})

以 \sum \limits_{i = 0}^{n - 1} x_i y_{(i + d) \bmod n} 为例，先倍长数组，令 X = [x_0,x_1,\cdots,x_{n - 1},0,0,\cdots,0]，Y = [y_0,y_1,\cdots,y_{n - 1},y_0,y_1,\cdots,y_{n - 1}]。再令 Y^{rev} 表示 Y 的反转数组 Y^{rev} = [y_{n - 1},\cdots,y_1,y_0,y_{n - 1},\cdots,y_1,y_0]。则有

H1_d = \sum \limits_{i = 0}^{2n - 1} X_i \times Y_{i + d} \\ = \sum \limits_{i = 0}^{n - 1} X_i \times Y_{i + d}\\ = \sum \limits_{i = 0}^{2n - 1 - d} X_i \times Y^{rev}_{2n - 1 - d - i}

其中上限可以改变是因为倍长的时候 x_{n} \sim x_{2n - 1} 均为 0，而最后 H_k 也就是卷积后 C_{2n - d - 1} 的值。

计算另一半 H2_d 同理，最后 F_d = H1_d - H2_d。

做三次完整的 NTT 即可得到答案，时间复杂度为 O(n \log n)。