退役之战 | ICPC2026沈阳站游记

· · 生活·游记

Day (-1)

这次比赛来的很晚,周五的高铁晚上八点多才到,找了个酒店就休息了(东北的烧烤好吃!

在高铁上复习了一下好久没写过的计算几何板子 敲了一遍半平面交和凸包,不过前几场计算几何都没有可做题可惜

我在期待一个可做的计算几何(

晚上因为一些原因睡得很晚很晚 /ll

Day 0

cxy 请了一顿午饭!(东北的烧烤好吃!

下午报道,沈阳站依旧寒酸(不过今年的马甲还不赖),餐券只有三张晚餐券还是自选餐(没吃够 /kel

非凸玩游戏抽到了 miku!(可爱捏

热身赛,A 题被队友速切 Orz,又是全场第二发 AC(哭)然后 jcgg 跟我在研究 B 题,ztd 在研究 D 题

我感觉 B 的做法可能是并查集然后用某种神秘方式合并一下,不过这个并查集好像不太好维护,jcgg 好像有个神秘搜索,不会。

然后 ztd 开了传奇 Truly 交互题,和神秘 Qwen0.6B 对话,一开始采取了 A or B or C or ... 的方式结果一直 WA,一个多小时的时候赛时提醒不要用这种方式(

然后我也去看 D 了,我首先给了一个方法四六分(是否 man-made),然后后面就比较好办

但是一直 WA 为什么呢?然后问了几个大模型发现答案跟预期略有出入,然后改了一堆 最后还是 WA 了

后面裁判回应是 Qwen 给 tea 是否 man-made 判成 No 了结果一直不对 /ll 好像改成 made by man 就可以

回去装了个 Qwen0.6B 玩玩(

第一天晚上和队友加训...ztd 速敲了若干签到题,ztd 太强。我把闵可夫斯基和的板子敲了一遍感觉没啥问题,万一明天有可做的计算几何呢(

Day 1

昨晚加训到了快一点 今天七点半一直赖床到快八点才起(

然后是正式赛,依旧有中文题面,撕成三部分分开看,我看到了 L 一眼就看出了做法应该是签到 然后丢给了 ztd(好像这个时候我去写可能更快(?)也说不定 相信 ztd 的手速!

然后 ztd 一眼就看出 H 然后 28min 直接切了 H(太强!)但是离首杀差了几分钟不过是全场二杀!

此时排名一度来到了全场第五名 Orz

然后 jcgg 把 D 写了,我一起造了几个 corner case,后面发现构造也有点问题,不过只吃了一发罚时,问题不算大

现在还在金牌区,然后我开始研究 J 题,jcgg 在看 C 题,他们很快想出了做法,ztd 就上机写了

J 题考虑什么样的数是锚定数,首先如果区间内的所有数在二进制表示下,都被 x 包含或者都包含 x(a 包含 b 指的是 a | b = b),那么肯定 x 是锚定数

如果区间存在其他数呢,考虑把 x 的 0 位先排,1 位后排,那么存在某种排法使 x (除了那些有包含关系的数)最小;同理存在某种排法使 x 最大,因此上面的条件是充分必要的

然后考虑如何回答询问,jcgg 给了个建图的思路然后最后找链即可,问题在于图不一定能在规定复杂度内建出来并且也不太好找链

然后就卡题了,等 ztd 写完了 C 就来一起看 J 了,jcgg 就看 F 题去了

ztd 伟大地提出可以在 O(nm^2) 内求出,对于每一个数 使得存在包含关系的包含这个数的区间的最长长度(即左端点 l_i 和右端点 r_i)并且先写了

然后问题就转化为,给出一个询问区间 [ql_i,qr_i],求有多少组 l_i,r_i 满足

l_i\le ql_i\le i \le qr_i\le r_i

然后 ztd 给出了很多神秘数据结构解法,包括但不限于分块、线段树、st 表、莫队,最后写了一个莫队的代码但发现复杂度假了

现在 F 也没什么思路,排名一度掉到了银中下区,金是没有希望了因为一直在卡题(

然后我想了想刚开始想 J 时有个假掉了的思路:考虑将所有数按二进制中 1 的个数来排序,那么如果存在两个数有相同的二进制中 1 的个数,那么它们一定不可能是锚定数(两两不同性质),因此锚定数最多只有 m 个,O(qm) 一个一个判断即可

但是当时想到的是不同询问区间是独立的重排,因此就没再想下去

然后我在想能不能记录二进制中 1 的个数为 i 的下标集合,然后二分找区间中可能是锚定数的数(二进制中有 i 个 1 的数是唯一的),最后按上面给出的 l_i,r_i 判断即可。

ztd 很快就把这个做法写出来了,并且过了样例和手造的样例,然后交上去 WA 了

结果发现 1<<n 没写成 1ull<<n,又交上去耗时稍微久了点但还是 WA 了

然后造了一大堆 corner case,只剩下十五分钟也没有时间拍了 急急急

结果有一组 corner case 给 hack 掉了,发现位数要判断到 m,应该改成 i<=m 而不是 i<m,结果一交就 AC 了

惊奇地发现竟然 6 题都金不了 之后滚完榜后面的 THU 队对队对队 7 题都 Ag 了,只能说这场强度太大了而且我们太菜了 /ll

非常好的题目使我们从金牌区被筛选出来 /kel

啊!也是 77 名 Ag 离场了

想来接触算法竞赛已经快十年了 /ll 不过期间断断续续地学 由于各种巧合缘分好几次重新和算竞重聚 想到这可能是算法竞赛生涯最后一场也有点感触(

感谢 jcgg 的带飞 /ll