退役之战 | 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 伟大地提出可以在
然后问题就转化为,给出一个询问区间
然后 ztd 给出了很多神秘数据结构解法,包括但不限于分块、线段树、st 表、莫队,最后写了一个莫队的代码但发现复杂度假了
现在 F 也没什么思路,排名一度掉到了银中下区,金是没有希望了因为一直在卡题(
然后我想了想刚开始想 J 时有个假掉了的思路:考虑将所有数按二进制中 1 的个数来排序,那么如果存在两个数有相同的二进制中 1 的个数,那么它们一定不可能是锚定数(两两不同性质),因此锚定数最多只有
但是当时想到的是不同询问区间是独立的重排,因此就没再想下去
然后我在想能不能记录二进制中 1 的个数为 i 的下标集合,然后二分找区间中可能是锚定数的数(二进制中有 i 个 1 的数是唯一的),最后按上面给出的
ztd 很快就把这个做法写出来了,并且过了样例和手造的样例,然后交上去 WA 了
结果发现 1<<n 没写成 1ull<<n,又交上去耗时稍微久了点但还是 WA 了
然后造了一大堆 corner case,只剩下十五分钟也没有时间拍了 急急急
结果有一组 corner case 给 hack 掉了,发现位数要判断到 i<=m 而不是 i<m,结果一交就 AC 了
惊奇地发现竟然 6 题都金不了 之后滚完榜后面的 THU 队对队对队 7 题都 Ag 了,只能说这场强度太大了而且我们太菜了 /ll
非常好的题目使我们从金牌区被筛选出来 /kel
啊!也是 77 名 Ag 离场了
想来接触算法竞赛已经快十年了 /ll 不过期间断断续续地学 由于各种巧合缘分好几次重新和算竞重聚 想到这可能是算法竞赛生涯最后一场也有点感触(
感谢 jcgg 的带飞 /ll