2025 ICPC 上海站 游记

wmrqwq · 2025-11-21 01:10:02 · 生活·游记

Tips：本文可能含有对部分题目解法的剧透，如有介意请不要看此文章。

day 0：

热身赛。

ak 了，四个 *800，B 吃了一罚怎么回事呢。

day 1：

正式赛。

没有中文题面。

开局先等其他队伍过题，等了一会儿，发现 5min 没人过题，恐怖。

过了一会儿一步之遥过 D 了，@incra 看了 D，想了一会儿会了，写了一发过了，此时是 30min。

在 @incra 开 D 的同时我做了 G，发现很容易可以发现最多拆分成两个集合，一个集合是好做的，两个集合感觉不难？是不是二分一下就行了。

写了一发 wa 了，同时 @incra 说会 H 了，遂打印代码让 @incra 写，我和 @AvisD 来调试。

看了一下，发现我在写什么【】东西？写的完全错了，这咋过的样例 /yun。

然后继续想两个集合咋做，不会做啊，我有玉玉症。

在玉玉的同时 @incra 写完了 H，交，发现 WA 了，但是 WA 在一个很后面的点。

想了一下，发现线性基直接做是不难的，但是是两个 log，1 \le n \le 5 \times 10^5，0 \le a_i < 2^{60}，O(n \log^2 V)，这咋过？？？

写了一下发现并不慢，卡卡常可能就过了，但是我们考虑继续优化。

想了一下，发现不用按位考虑，直接线性基就做完了，是 O(n \log V) 的，写了一发过了。

然后看 H 为啥 WA 了，发现 @incra 数组开小了，改了，过了。

那么我们稳中向好啊！1.5 小时 3 题，感觉 Au 在向我招手了。

看到 A 是交互并且有人过，故我想 A，一眼就发现直接取当前没确定的点然后划分使得两端尽量平均就是对的啊？

暴力 bfs 复杂度就对了，写了一发，过了。

然后就玉玉症了，我会了 I 暴力咋做，我去做 I，他们去做 J。

中饭给了汉堡王吃，还不错。

在过了 1.5h 之后，队友写写调调总算是过了 J，在队友调的过程中，我想 I 咋做，注意到 I 的 dp 式子是 f_i = \min_{j=0}^{i-1}(f_j + (i-j-1)C + (a_i \oplus a_j)) 的状物，注意到值域很小，于是我们充分发扬人类智慧，对于 j 只取 [\max(0,i-500),i]，然后接下来的瓶颈在于后面的值可能会比较小，那么我们取 B 个 a_i \oplus a_j 最小的值即可。

调调写写总算是过了样例，交上去发现 TLE 了，把 B 的大小改成 30 就过了。

赛后发现我这个做法是正解 /kx/kx/kx。

还剩下几分钟，交了所有题目。