ICPC 区域赛 沈阳站 游记

从来没有想到这样一天的到来吧。

我本可以忍受黑暗，直到我见到了光芒。

晚上 VP 南京场。_Vector_ 在赶作业，前期无法做题。

倒序开题。M 题多边形肯定不是我的题。L 题几何题显然不是我的题。K 题……中国象棋？？

按下棋常识，车能捉住马……只能是把一路马压住吧？反正我从来没有在其他情况下遇到马被抓死的情况。

real_man 把 C 秒了。我开始写 K。诶等等，是不是马在角上而车在 $(2,2)$ 之类的位置也行？加上去。

诶怎么 CE 了？哦 y1 会与关键字冲突。诶怎么 WA 了？

哦，好像马在角上时车在 $(3,3)$ 也能吃掉马……为什么还是不对？

打开 chess.com 手玩。发现马在 $(1,2)$，车在 $(3,4)$ 之类的地方也能捉到。

为什么还是不对？？

我反复划动着鼠标，试图找出代码中的错误。然而没有找到。

real_man 过 F 了。

会不会是……马在 $(2,2)$，车在 $(4,4)$ 也能捉到马？交一发。

终于过了。

这题到底考的是什么鬼啊？！考察选手的棋类水平吗？

接下来看 I。感觉 I 非常一眼啊，倒着跑一个 DP 就没了。队友没题，果断开写。

写完发现样例挂了。此时沟槽的“我最喜爱的老师”问卷调查催着要收了，被迫先完成 400 字小作文。浪费机时。

写完小作文得知队友进度为 0，于是继续调试。发现转移方程挂了，于是重写。中间 real_man 会 B 了，让他先过了。

这题几乎就是为了长而长，故意要在确保最坏情况下还有钱的情况下决策，还要特判 $p=0$ 或 $p=100$ 的情况。不懂出题人怎么想的。

说是自己不写超过 1.5KB 的代码，这一下又到 3.6KB 了啊。

等我写完了一交——又挂了。

为什么呢？？这个 Corner Case 讨论的完全正确啊，怎么可能错呢？

难道是用 $-1$ 作为合法表示不行？改成 $- \infty$ 再试试？还是不对啊？而且确实也不应该有用。

晚自习下课了。趁 _Vector_ 在写 H 的时候，我赶回了寝室。继续看代码。

经过跟 real_man 长时间的讨论，我发现我代码读取答案时里有允许初始时队友已经付过钱的情况，而这可能导致主角本来应该在后面比较贵的时候付的车钱提前付了，然后就错了。改完过了，让 _Vector_ 继续写 H。

那这场是彻底倒闭了，都 3h20min 了才 4 个题，还有着 499 的超大罚时。可能是最失败的一场吧。

看 G 题。G 题 _Vector_ 之前提出过基于交换与偏序的理解，感觉很有道理，但不太有思路。

那这题是怎么过了快 90 个队的啊？那我要开始 guess 了。

直接大胆猜测答案等价于让容量最大的 $k$ 个水在 $k$ 个最小的洞下漏，其中 $k$ 是最大的能让所有桶里的水不漏完的自然数。听起来就很假啊，但手玩样例对了！交一发过了！！

有用吗？

诶 _Vector_ 的 H 也调出来了！real_man 的 M 一发过了！

诶好像金牌了？！不过罚时比现场任何八题队都多。也是拿到天狼星封榜过三题剧本了。

但正赛这样就完蛋了啊，哪里有正赛还有勇气随便猜猜过的？然后前面罚一堆时心态崩了后面怎么玩？假如 M 没一发过不也没了吗？

但愿沈阳不会这样吧。

real_man 的 B 被 Hack 了。据说是同向向量没判好。改完又过了。

J 题是神秘结论题，就是找出所有与之相连的边不是桥的割点。这真 CF 场吧。

但哪有 CF 场塞 I 题这种东西的？

还有一年我就是大猫了呢。

real_man 的 B 又被 Hack 了。据说是极角排序被卡精度了。改完又过了。

回归计算几何本色了。

互相提醒第二天要带的东西。

队友提议要不要晚上加训一场。可我第二天还有早八啊！那算了吧。

8 点 41 分。

_Vector_ 提醒道带学生证和模板。“打完 ICPC 网络赛第二场以后我还会忘带证件吗？”正在上数学课的我想。

real_man 提到了字典。那我还要回寝拿一趟。显然我没有注意到他后面说的“好吧那我带”。

real_man 顺带提了一嘴他会晚点到。可能也是早上课上完还要回寝拿东西吧。

_Vector_ 表示北门集合。从主楼到寝室再到北门，距离不算很短。

一切准备充足，至少我当时是这么认为的。

9 点 18 分。

“查询 @lizihan250 人呢？”_Vector_ 在群里问道。

诶？

现在集合吗？

可我还在上课啊！！

啊原来昨天说的是 9 点集合吗？！

关键我还坐在第二排不可能说溜就溜吧？！难道我要背着个大包跟老师说“我就上个厕所”吗？

“算了等你下课吧。”real_man 说。

终于熬到了 9 点 50 下课时间，早就收好书包的我飞奔出教室，回寝室带上词典和充电器，又急匆匆的往北门跑去——速度跟体测不相上下。等我气喘吁吁的赶到北门时，已经是 10 点了。

好在我们都不用托运行李，赶到机场后还是留了充裕的时间。算是有惊无险吧。

飞机上我在想我前两天出的 Chaos and Abyss -3rd Movement- 那题（请和我供给高中校内的同名比赛区分）有没有单 $\log$ 的解法，想出来了之后开始睡大觉。_Vector_ 折纸的时候想出了一个 idea，不过后面多项式有些做不下去，准备下飞机后和 real_man 交流（不过好像当时下飞机就忘了这事）。

下飞机的时候手机没电了，好在 real_man 有充电宝，稍微借用了一下起码坐地铁扫码不是问题了。

在地铁里或许是有供暖的缘故，居然感觉有些热。

晚上 real_man 找同学玩了，我和 _Vector_ 一起吃的饭。吃完饭回来发现飞机上想的单 $\log$ 做法假了，于是回滚回双 $\log$ 版本，写完标算一测发现两秒跑不过 $5 \times 10^5$，评价为拉完了。于是把数据规模改为 $2 \times 10^5$。

早上 7 点 58 分醒来。那就把 8 点的闹钟关掉吧，_Vector_ 还在睡觉呢。约的 9 点的 VP，现在出去还能买个早饭。

独自一人前往买早餐。早晨的沈阳温度挺低，但相比西安也没有冷到哪里去。买了两个包子回到酒店吃。到酒店了才想起来应该要给队友带一份的，但想到 _Vector_ 前一天就说自己本来就没有吃早饭的习惯就算了。

依旧网瘾，打开电脑为自己出的题写题解。我怕吵醒 _Vector_，发 QQ 问 real_man 有没有起床，如果起了的话去他房间写。没有回应。

事实是，real_man 到 9 点 50 才回消息。姑且认为他现在才起床吧。10 点钟这个时间，不上不下的，VP 一场先不管我自己的作息，对于两个没吃早饭的队友来说等打完肯定要饿晕了。于是改变计划，先签到，下午再 VP。

签到效率挺高。按惯例我不喜欢挤在签到处玩小游戏，于是在外面拍了两张照，等待队友出来。出来后大概是 11 点，我们吃了顿中饭，开始 VP 哈尔滨站。

至于 VP 结果……呵呵。

开局 ALG 一人一道没什么好说的。然后 K 题 01 背包，推了一下式子感觉就是诈骗题，$n=2$ 非常合理啊！交了一发挂了。

为什么呢？哦好像如果 $w1 + 2 = w2$ 的话可能 $w1$ 往上加 $1$ 之后更优。再交了一发又挂了。哦我代码写错了。再交了一发又挂了。

那这又是为什么呢？

一旁 _Vector_ 的 I 题也挂了。

哦！我明白了，刚刚的构造可能在 $W = W_{lim}$ 的时候是可行的，但 $W < W_{lim}$ 的时候是不可行的！那我又会了，只要构造 $W_{lim}$ 个物品，使得 $w = 1$ 的优先级最高，剩下的物品 $w$ 越大优先级越高就好了。

怎么又挂了？哦！我没输出 $n$！我是笨蛋！……怎么还是不对？

唉我在构造什么东西啊！怎么 $w$ 越大优先级越小啊？改一下。怎么又错了？？

唉我在干什么啊？$v_i$ 要严格大于 $v_{i-1} + v_1$ 啊！再改。凭什么还是不对啊？

哦，如果这么构造的话 $n$ 的性价比可能会大于 $1$。那还要再枚举 $1$。啊，终于过了。

$+7$ 都来了，这还是人吗？

然后又卡住了。_Vector_ 去写 J 了。于是我去看 I。先给出了一个不断选择最上方的黑点，选取下方一格点一下，重复类似 $6 \times 10^5$ 还没消完的话就无解，否则有界。然后被队友两票否决。

J 挂了。

我给了个观察就是有解的话每条线上的黑点必须都是偶数。这当然是必要的啊，那凭什么是充分的呢？不管了，交一发。反正不会了。

诶过了？凭什么啊？

J 随后也过了。

然后 B 一个代码题，M 一个推式子题，队友把工作都包了。于是我去看 H，连两个集合的情况都不会做。后面比起看题目，更像是在摸鱼。队友两个题都没干出来。于是获得了第一个 VP 银牌。

如此水平，如何区域赛？

总共拿了十发罚时。我贡献了七发。怎么空有罚时没有“十发罚时”那支队伍的实力呢？

“其实是在为明天积攒人品。”队友说。

好吧，先相信。

吃晚饭。食堂晚饭……不予评价。前往热身赛场。

来看 A 题……啊？？

通信题？？

这……这是 ICPC？这不是 IOI 吗？

通信题加入 ICPC？但我除了 P12509 以外没有做出过任何的通信题啊！

啥，B 题还是交互？明天不会一道通信一道交互吧？

哦，这个 B 是送分题，从 $0$ 到 $99$ 一个个问过去，就做完了。要是还没问出来，就是 $100$。上机秒了。

A 题是将 $1923$ 到 $2024$ 中的数编码为一个 $8$ 位 01 串，编码可能会反转，可能不会反转，然后对处理后的编码进行解码。

理论上 $7$ 位就可以编码数字本身，再加一位编码空间肯定够了。那怎么构造校验码呢？

哦，因为编码空间是充足的，而且正串与反串形成双射，所以其实直接把每一组正串与反串绑在一起，然后强行构造映射就行了。让 _Vector_ 写，过了。然后 real_man 也写了一发。

C 题跟导览图完全不是一个题。一开始认为遍历每棵子树后直接统计大于这个子树的根节点的点的数量就好了，后来发现不对，要统计每个子树内比根节点编号大的点数。

“那这样要写一个树上启发式合并。好烦！”_Vector_ 说。

“诶不对啊，这是不是能直接用可持久化线段树做啊？”我想起前两天刚学会的数据结构，说到。

“不对啊！”我突然意识到，“直接拍平成序列然后用权值树状数组做就好了啊，哪里要可持久化线段树啊！”于是跟 _Vector_ 说明白了思路后，让他写了。55min 的时候过了。

接下来是测机速时间。评测机跑的飞快，$10^9$ 都不成问题。最后我再写了一发 A，encode() 和 decode() 写反了半天没调出来。过了之后就跑路了。

至于 D 那个圆面积并板子，谁爱写谁写去吧。

晚上看 CF 的通信题测试轮。由于 Cloudflare 坚持我不是人（好吧其实是小猫，那确实不是人），我没办法提交代码，于是只能口糊。

A 题直接在 10 进制下逐位映射就行了，甚至不用转成 26 进制。Hard 在哪里？

B 题感觉跟通信没什么关系，基本就是通过二分找出同时包含 $1$ 和 $n$ 的极小区间，然后通过第一次跑的时候给出的 $1$ 在 $n$ 左侧还是右侧的信息确定那个是 $n$ 就行了。

C 稍微复杂一些。$20$ 位中 $15$ 位用来编码数字，剩下 $5$ 位用来校验。怎么办呢？

先假定校验码不会被破坏吧。注意到 $15$ 可以用 $4$ 位编码表示。我们记这个校验码为 $x$，初始时为 $0$。那对于 $1 \sim 15$ 的每一位，如果第 $i$ 位为 $1$，那就让 $x$ 异或上 $i$。这样，假如编码位被破坏，那么可以用前面编码区再异或一遍，然后异或上 $x$，得到被破坏的位，把那一位取反就行。

但怎么确认校验码会不会破坏呢？再用最后一位校验。通过最后一位校验码使得最后 $5$ 位的 $1$ 的数量为偶数。解码时，如果最后 $5$ 位的 $1$ 的数量为偶数，那么校验码有效，进行上述步骤。如果最后 $5$ 位的 $1$ 的数量为奇数，那么校验码无效，说明修改位在校验区，那直接按原编码区信息解码就行。注意到 $x$ 的范围是 $1$ 到 $2^{15}$ 而非 $0$ 到 $2^{15}-1$，故编码时要进行偏移调整。应该做完了。

已经是十点半了。该睡觉了。希望明天不要被通信题区分吧。

9 点钟，正赛开始。

real_man 一眼看出 M 题是本场的 LOL 系列题目，应该是一道简单题，于是我跳过 M 看 L。L 光是样例解释看起来就很不可做啊！这时候我想起来这场应该是有一道通信题的，于是去翻找这题，发现它是 C 题。

这道题给定 $n$ 个 $1$ 到 $m$ 中的整数，要将它们分别编码为 $3m$ 且 $1$ 至 $m$ 中每个数均出现 $3$ 次的数组，编码完毕后，每一种数可能会变为 $0$ 或 $1$ 中的一个。然后要把这些 01 串还原为 $1$ 至 $m$ 中的整数。

13min，我 C 题还没完全读懂，_Vector_ 已经把 I 切了。real_man 上机写 M，_Vector_ 转头看 B。

唔……感觉这题有点神秘啊，而且当 $m$ 非常小而 $n$ 非常大的时候，怎么可能构造出那么多种不同的构造呢？

诶，要编码的数是 $1$ 到 $m$ 中的，所以只要我能为 $1$ 到 $m$ 中的每个数都给一个可互相区分的编码就解决了。那 $1$ 到 $m$……这怎么表示呢？不太能用二进制表达吧。

31min，real_man 过 M 了。此时 _Vector_ 也会 B 了，上机去写了。

那我这场还没做出来任何一道题呢！快点把 C 做出来啊！

考虑循环移位，前 $m$ 个位置放 $1$ 到 $m$ 是自然的。当编码的是 $x$ 时，通过循环移位将 $x$ 移到第一位。怎么避免循环同构呢？后面放两遍 $1$ 到 $m$ 可以吗？显然不行。那 $1 1 2 2 3 3 \dots mm$ 呢？

“这个 A 题，”real_man 说，“你看一下，要算第 $k$ 大的 $(i-j)(i+j+\frac{2a}{b})$”。

数学题显然不是我的题啊！我想了一下没思路，于是放弃了，继续看 C。

感觉这个构造非常合理啊，刚好每个数在前段和后段的距离都是不一样的，虽然我不会证，但感觉就是卡不掉啊！

就是……这怎么维护呢？

“这可能是个字符串，”我说，“等 _Vector_ 写完 B 之后讨论一下。”

于是看 K 去了。K 一眼看上去非常恐怖啊，说是要不断的进行“反射”操作，还保证跳的次数不超过 $2 \times 10^5$，难道我要把这个跳跃的序列找出来？

49min，_Vector_ 把 B 过了。我把刚刚 C 题的构造给他转述了一遍。

“K 这个题，”real_man 说，“可能就是跳跃前后比如 $\sum x + \sum y$ 的变化能够指向最后一个点的，你去看看。”

感觉很有道理啊。我于是试了一下，发现 $\sum x + \sum y$ 似乎中间的变化量会抵消，最终的变化量好像就是 $2(x_t + y_t - x_s - y_s)$。但这样只有一条直线。

那我再算个 $\sum x - \sum y$ 不就有第二条直线了吗？我把方程解完（此时我甚至并没有意识到 $x$ 和 $y$ 是可以分开算的），上机写了一发，过了。

_Vector_ 说 C 会了，说后面搞个哈希就行了。我不太懂。不过会了就行，管他呢。

我接着看 F。F 感觉很显然啊，两个点不相邻的情况显然，相邻的话找个包含这条边的环就好了。

real_man 此时 G 也会了！

C 没过样例。于是我上机写 F。写到一半意识到不能随便找一个环，如果环上的两个不相邻的点之间连边的话就会出事。于是重新思考。real_man 上机写 G。

后面注意到找一个最小环就不会有这个问题，并且在 real_man 的点拨下，我意识到并不需要用 floyd 之类的算法求最小环，直接把边断掉跑 BFS 就行了。

此时 _Vector_ 发现 C 题的问题了。改了一下，在 113min 提交了。

我站起身来看大屏幕。

通过了！诶好像是深绿色？

啊？？一血？！

我已经兴奋到大叫出来了，以至于旁边的志愿者都小声提醒我们安静一些。当然我心里还是满心期待着一血气球的送达。

当 C 题的一血气球绑在我们的矿泉水瓶上的时候，感觉满足感已经比金牌还高了。

136min，real_man 又把 G 过了！此时我们排在 #2！计划有变？

于是我乘胜追击，接着把 F 改了。148min 提交了……并没有通过。

“本场比赛第一发罚时。”我说。

“其实签到罚了一发。”_Vector_ 说。

“不重要！”

然而我反复检查代码，并没有找到任何错误。于是我开始漫无目的的测试各种数据。然而也没有找到任何错误。至少我是这样想的。

“是不是这样，”real_man 说，“只要他们能走到一个环上，就算他们一开始不在那个环上，也是可行的。”

啊，好有道理啊！那这题一下子就变得复杂起来了。

那现在怎么找最小环呢？floyd？但我之前从来没写过最小环啊！

“你先去对每个点判有没有过这个点的环，然后从 $x,y$ 出发找最近的有环的点。”real_man 说。

“对吗？对吧？哦不对。”找到了这个点之后，还是要找最小环。还是绕不开吗……

起码是否有解会判了，也算一种进步吧。

与此同时，A 题和 D 题都有了可观的进展。再做出来三题，感觉这场要捧杯了……吗？

哦，不一定要找最小环，只要是极小的环就好了。那可以直接给环上的每个点标个“势能”，然后找出环之后再从势能最低点不断的跳到一步能到的势能最高点就是一个极小环了。然后最后还要把 $x$ 或 $y$ 走到环的路径标出来。哇，好复杂！

于是开始磕磕绊绊的写这题。写完测样例，不出意外的挂了。

接下来是漫长的调试，期间多次与写 A 题的 _Vector_ 以及写 D 题的 real_man 换机位，不过多数时候是我在调 F。时间来到了封榜。此时已经没有一点兴奋的感觉了。

好不容易把样例和手玩样例都过了，4h17min 一交，RE 了。

我直接打印代码（5KB 还多，我自己都不敢相信），把机位让给 A——尽管 A 也是处于卡住的状态，似乎是分类讨论的时候出现了问题。

real_man 说，自己 D 题做法假了。

其实到这个时候假不假都一样了，就算做法没问题也大概率没时间写了。

“不可能啊，怎么会 RE 呢？”我看着代码，嘀咕着。

数组没有开小，那一定是访问负数下标（我代码里的无效标记是 $-1$）的问题吧。哦！这里的 $-1$ 在后面使用的时候可能越界了！

我立刻上级修改，交了一发，还是 RE。

不对，看错了，那个 $-1$ 根本不会作为下标。那为什么会 RE 呢？

此时 _Vector_ 也放弃了 A 题，所有人都在看这个 F。

经过持久的瞪眼无果之后，我又开始检查起算法竞赛最古老的错误之一——多测不清空。真找到一个！赶紧清空之后再提交——这次变成 WA 了。

“还有没清的吗？”

“这里没清空。不过这个是每次赋值的，应该不用清吧……”我自言自语道。

那还能有什么问题呢？

还剩 10min。算了交一发吧，已经不抱希望了。

……？

为什么过了？

啊……啊？

没有多少喜悦，我感到更多的，是一种解脱——以及一种不解。

不过过了就是过了。剩下的就是吃饭时间了。我确实也有些饿了。顺便把 F 代码打印下来了，5.7KB，比结构体长多了。

队友开玩笑说只要其他队伍封榜后的提交全挂了就捧杯了。哪有这种事呢？

比赛结束了。

隔壁天狼星也 7 道题，罚时比我们少 5 分钟。还有一支队伍 6 道题。XJTU 这场感觉要 3 Au 了啊！

武大 8 题老哥来问我们多少题。被薄纱了。

滚榜滚出来 XJTU 校排 #4，三支队 #6/#7/#17！但凡 F 切的再快一点，留点时间给 A，说不定就出线了。当然当时没想这么多，毕竟一血这东西估计这辈子拿不到第二个了。

晚上在飞机上用 real_man 的手机打 Phigros，打的一塌糊涂。三个人还玩了 A=B，很显然大家并不是很擅长提交答案题。到机场后我们队跟隔壁泞2的如心拼了一辆车回学校，聊天气氛非常欢乐。

还剩一场 EC Final，这场别说出线了，连能不能拿金牌都是个值得商榷的问题。不过沈阳区域赛，也让带来了一丝光芒，不算太亮，但也指引着我们前进的方向，激励着我们更进一步。

我的个人能力终究是薄弱的，NOI 提高组大纲外的多数知识点一窍不通，单挑往往连银牌都拿不到。但在讲究团队协作的 xCPC 中，在这样一支队伍中，我真切的感受到我不是一个毫无作用的角色。相信队友能做出不在我的领域内的题目，与队友接力完成题目的观察与实现，尽自己的一份力去完成自己应该做的事情，这才是比起纯粹的个人水平更重要的东西。在 xCPC 的赛场上，有的时候，三个 CF 紫名组成的队伍，不一定比三个 CF 红名组成的队伍弱。

这座里程碑，也是下一段征程的起点。