ICPC 2025 上海站

· · 生活·游记

由于换电脑导致暂时无法 update 个人博客，所以先发这边了。可于 我的博客 观看 2024 年 EC Final 和各区域赛的游记。

day -1

前往上海。事实证明和教练交涉酒店问题大有成效，获得了一个显著强于去年上海站的酒店。到酒店摆烂，给 MX 讲题，摆烂。这个概统作业怎么这么难啊，这个 frontwars 怎么这么难啊，这个 pentiment byd 怎么这么难啊。

发现在上海从周五晚上待到周一早上预计将吃 0 顿上大食堂，蹭饭王这一块。

day 0

早上起来研究了一下发现酒店似乎没有早饭，于是点了个麦当劳的外卖，结果点过来之后教练在群里说酒店有早饭。

大概十一点去报到。报到现场一片混乱，感觉我一遇到这种比较混乱的场合就会高血压。于是像以往一样忽略了所有企业活动并在外面台阶上坐着搓 Arcaea。

报到过程没有碰到群友。报到完成后前往 Minimax 蹭饭。被 Minimax HR 咨询了为什么 OI 圈的二次元浓度和 mtf 浓度很高。这我哪知道啊.jpg。他们还称之前与其他 OI 选手开 ktv，并惊讶于很多 OI 选手可以吟唱日语歌词。不懂，感觉我其实是纯拟合 / 罗马音战士。

蹭完 Minimax 回校启动热身赛。D 是交互。看 D，感觉很神奇。但是几分钟之后就发现 \log 次就可以把 1 随到开头，然后就做完了。B 是去年 CCPC 重庆的原题，C 是 thupc 的原题，A 队友糊了个不知道啥结论就通过了。二十分钟下班。

下班之后在赛场里面随机游走。听说 skc 要去参观米哈游，感觉很厉害。但是时间不太够，遂摆烂。发现尺子捧杯了，很厉害。偶遇 yhk 老师和 wzj 老师，并获得一张合照。

晚上和 fdu 学妹聚餐 & 散步，从静安寺走到防御塔附近，但是由于路上的蜜雪冰城休息了导致没有受到攻击。路两侧全是各种商场，印象里在 bj 也根本没见过这么繁华的地方，乡下孩子也算是长见识了。交流了一些大学相关和高中相关。听说了很多高中老师的神秘八卦，感觉学妹的消息还是太灵通了。拍合照，但是我的拍摄技术仅限于将手机举到一个随机高度并点击拍摄按钮 /ll。被送了小礼物，很开心。

day 0.5

晚上似乎没太睡好，四点多醒了一次。

day 1

好困。不想研究酒店早饭，于是继续启动麦当劳。把报到时候发的写着队名的牌子拿过去了，但是被教练指出（似乎）并没有什么用。

开题。M 看着不好做，L 看着不好做，K 看着不好做，J 看着不好做，I 看着可能比较好做。然后做了一会发现修改可以等价于删除，然后随便 dp 一下再随便分块一下似乎就做完了。

但是没有直接开始写。此时似乎有人通过了 D，和队友看了看发现是暴力就行，于是队友写了写过了。期间发现有人通过 H。于是我开始对着 H 自闭，搞了半天没有发现任何有用的做法。

队友认为 F 是简单题，但是写了一会发现无法简单判断一个点是否在一条直线上面，然后我发现要李超树，队友感觉难写，先扔。

然后队友研究了一下 G 就通过了，我对着 H 自闭了半天还是没有任何靠谱做法。把队友叫过来对着队友随机说话，结果说着说着队友突然就会了然后写了一下就过了。

此时大量人通过 J，观察了一下发现好像直接利用一下 w \leq 8 跑个爆搜就行。和队友对了一下实现细节，然后队友实现并通过。队友实现 J 时我开始思考 E，自闭了一会发现 E 这个树的结构其实可以直接拿过来 dfs，这样 dfs 一个点就只需要改 k 个位置。队友通过 J 后又调了一会 F，我得到做法后抢过电脑火速实现 E 并通过。

让队友接着写 F，样例通过后 WA 了几发，打印了一下让我写 I。然而这个分块是值域上的，导致我直接清空会带一个 T \times a_i \log a_i 的部分，然后写出来果不其然 T 了。

自闭了一会，期间队友上机修改了 F 的一个位置，但是仍然未能通过。最后无奈决定把 vector 换成数组，结果换过来直接就过了。本来还以为 vector 挺快的。

通过 I 之后一个队友继续调 F，我和另外一个队友研究 A。发现二分出深度之后可以测定目标点是否在一个子树内，然后二叉树保证存在一个子树大概在 1/3 到 2/3 总大小的范围。队友算了算差不多能过就写了。看到 adaptive 就没想随机化的事，结果事后发现群友各种逆天随机化纷纷通过。

队友写 A 期间我开始研究 B。一开始想的是可以类似某个 WC 题把环异或起来，但是后来发现和那个题还稍微有点区别，并且似乎无法做到低于 n^2。然后发现往返一条边可以把两个端点都 xor 1，而往返一条边两次就可以在没有影响的情况下连通整个图。于是只需要把根的权值对上，那么显然就是在没对上的情况下找个奇环走一圈就对上了。

队友的 F 似乎无法对拍出问题，于是挂了个拍然后让我上机写 B。我写了一小会翻回那个 terminal 发现队友的 F 好像拍出来了，于是又把队友抓回来改 F，然后队友改了一会于封榜后 5min 通过。

我随后抢过电脑写 B，期间队友说 M 有个 n^2 做法，然后我跟他们说时限 7 秒，但是他们此时还以为数据范围是纸质题面上面写的 5 \times 10^4，而我也没有想起来比赛开始的时候的那个说纸质题面的数据范围写错了的 announcement。他们以为可以轻松通过，于是我火速冲完 B 并于封榜后 27min 通过。

队友上机，此时我突然反应过来好像说 M 的数据范围不是 5 \times 10^4，但是我们还不知道在哪查看线上版本的题面。最后在 announcement 里面发现实际数据范围是 2.5 \times 10^5。我以为倒闭了，然而队友直接拿起板子开始抄 NTT。我由于不会 poly 只能围观。最后队友 288min 提交，未能通过，测了几个样例然后修改了不知道什么地方，290min 再次提交，未能通过，发现需要特判 n=1，并于 293min 通过，10 题 / 特别巨大罚时光荣下班。

晚上翘掉颁奖去和 sjtu 高中同学体验神秘网红日料自助，并被参观了另一个 sjtu 校区，不过他说这个校区似乎主要是一个公园，他好像甚至找了半天没找着校门在哪。想起来了 pku 军训期间有一次要求在博雅塔下面集合，结果我半天没找到博雅塔在哪 /xk。

最后拿到了 rk2，希望能有 ECF 打。