ICPC2025 武汉站游记

· · 生活·游记

背景信息:pku 的“注意到不难发现”队,队长 cqbzly,另一位队员是 nKessi。我则负责提供饮食保障和情绪价值。

这里就直接 Day 2(正式比赛)起手了。

开场采取经典战术:nKessi 看 A - D,我看 E - I,cqbzly 看 J - M。

然后感觉 E 看上去比较小清新,跟 cqbzly 讨论了一下发现自己想复杂了,然后一发通过(0:28)。

nKessi 随后表示 C 似乎是可做的,上机写了一会发现有点细节,先鸽掉了;与此同时,我和 cqbzly 经全面、充分、详实的讨论,给出了 F 的一个直接对着区间贪心的绝妙做法,写了一发却 WA 了(1:00)。

仔细想了想发现正确性好像确实不显然,因为我们不能保证区间集同构。看着榜上越来越多的人过了 F,我忽然注意到我们其实只关心用来覆盖所有线段的点集,对着这个贪心就显然了。然后在第二发通过(1:15)。

在 cqbzly 写 F 时,我开始看 A,并注意到这好像是个类欧板子,但没带板子 /ll 遂开始现推,然后迅速一发通过(1:31)。

与此同时,nKessi 注意到 M 的一个简明的构造方式。简单验证后就开冲,进而更加迅速地一发通过(1:40)。

随后我和 cqbzly 开 H,nKessi 继续构造 C。

H 看上去非常的神秘啊!首先会了 n = 2,然后又会了 n = 3,接下来尝试推广,发现我们需要在一个 01-Trie 状物上干一些神秘的事情。然后我开始一边想细节一边写,第一发却 WA 了(2:18)。

接下来修修补补了一些细节问题,又交了第二发(2:28),但还是 WA 了 /dk

我和 cqbzly 对其正确性深信不疑,我随后便尝试加了一些特判,尝试减少 O(1) 次询问。

与此同时,nKessi 的 C 取得重大进展,于是跟我 swap 了好几次机位占用,也交了第一发(2:39),但也 WA 了。

这时 nKessi 注意到原本的讨论因有误而显得过于繁琐,大修之后交了第二发(2:56),然后过掉了 /se

为确认我们的 H 的做法的答案正确性,我尝试在询问次数超限时强制 RE,然后交了第三发(2:59),发现真 RE 了!被 Adaptive Interactor 制裁了 /ll

随后我成功构造了一个会让原做法刚好多一次询问的数据,陷入沉思。忽然注意到只需将 dfs 改成 bfs + 神秘剪枝,就可以确保省去(可能出现的)那一次多余询问。修改后交了第四发(3:36),这才终于通过。

随后 nKessi 接过鼠标键盘开始码 B,写完之后开始调样例;我和 cqbzly 则在想 K。暂时对 K 没有想法的我便开始帮 nKessi 调代码。

进行了较多的细节修改后终于成功通过样例的第一组数据,然后被第二组数据杀害了 /ll

接下来我先回来跟 cqbzly 讨论 K,然后渐渐地对原问题和部分(埋下伏笔)的实现有了眉目。接下来 nKessi 打印了 B 的代码,cqbzly 开写 K,我则继续帮 nKessi 纸面调题。

随后,我注意到 nKessi 对 dfs 序和 bfs 序的存储形式,尝试分析其正确与否,然后被绕晕了 /yun 接下来进行的讨论让我最终看懂了各个数组的含义并在纸面上进行了相应的修改。

接下来 nKessi 跟 cqbzly swap 了一下机位占用,虽然 B 第一发(4:37)WA 了,但经过简单的修改,交了第二发(4:38)便成功通过。

而后 cqbzly 继续写 K 并过了样例和手造的几组数据,随后交了一发(4:45),但 WA 了 /yun 接着又修了一些细节,但第二发(4:53)还是 WA。

我尝试把第一部分换一种写法,然后还没等我没写完比赛就结束了。

封榜前 rk33(所有队伍)/ rk28(不含打星)。

最终 rk32(所有队伍)/ rk27(不含打星),虽然以 7 题中段的成绩取得 Au,但荣登 pku 五队 /ll

遗憾的是 K 想复杂了,实际上“第一部分”可以去掉,相邻匹配是可行的。Constructive algorithms 害人不浅(确信)

虽然每个队只被颁发了一块牌子,但神秘的是主办方以 30r / 块的价格出售与实际应得相同的牌子。于是我们又买了三块(

你说得对,但是金钩蓝气球好可爱(

愿我们明年还能一起打 XCPC 拿下金气球