icpc 初体验
2026 年 ICPC 国际大学生程序设计南昌全国邀请赛。
校内机房/5月某天/晚自习
教练说有邀请赛，并指派初中部四名 bro（包我）征战并大杀四方。
没有多余的人愿意参加比赛，于是拉来了两位非人类选手。一个是欸哎哥（高一，因为行为有点人机而得名），另外一个也是欸哎哥（初二，因为 abc 被封号而得名）。
肖某被迫带着两个罗伯特参加比赛，汗颜。
启发下 qifan_maker 得到了『国家极逊队』这个队名，感觉滚榜的时候应该很有花活，下次还用这个。
校内机房/5.16 Sat/上午
教练突然告诉我们 icpc 比赛就在明天。本来我都已经忘记了这件事情，这天突然发现自己参加过 0 场 icpc，炸了。
又何妨，不过是我翘作业的借口罢了，快哉快哉！
寝室/5.17 Sun/早上
昨天晚上订了闹钟 6:50，因为教练说 7:20 要到校门口集合。舍友还在睡觉，似乎有点委屈他了。
赤完石之后已经 7:10 了。检查身份证之后出发了。
由于忘记在哪个门集合，所以（原本打算）被迫爬了一趟八楼去机房，但是突然发现周末电梯居然还活着，天不亡我！
到达南门的时候另外机器队已经提前打车走了，我们队的另两个人和教练正在等车。
小郭同学比较内向一直不说话，突然莫名感觉这个队伍是不是少了一个人。
在车上度过了 40mins 的时间，四个人加起来说了 eps 句话，心里莫名发毛。
JXNU/5.17 Sun/8点左右
出乎意料的，机器队居然比人工队晚到。我们三个人和教练一起尝试进入 JXNU，但是我一直刷不进身份证，最后被红衣志愿者拯救了。
出于某些原因我们不能走正大门，于是被迫进行一个超长的绕路，路上进行了策略的商讨：
qifan_maker 宣称应该每个人直接分配四道题，我个人对此持怀疑态度，最后这个战略并没有被采纳。
教练表示中午赤石三个人不要同时赤，不然会寄寄。我对此感到诧异，这里居然还会发午餐。
qifan_maker 向我补充，原来赛程是 9:00~14:00 共计五个小时，并且主办方会发 kfc 作为午餐，并且 JXNU 还包晚餐。
经过静湖的时候勾起了我对 2026 联合省选的回忆，熟悉的风景却并不伴随着美好的回忆，于是我尝试快速将其抛之脑后，但貌似失败了。
成功在先骕楼与机器队会师，楼梯上有一排大学生蹲着啃 main 包，在楼上还看到了 coser（流萤），并领取了廉价衣服和包，收到了了参赛证。
拍照。为了拉近关系而对小郭同学进行骚扰，效果立竿见影！
三楼机房/5.17 Sun/8:50 开赛前
找机房的时候居然还爬错了楼层，和省选完全一致的机房外面堵满了人。
入场之前向志愿者找来了姓名贴，将一个歪歪斜斜的 Somebody 字样贴在了自己的肩膀上（有病吧）。
入场，很快寻找到了队伍位置，卧槽这个牌子好丑。
为什么电脑要拿 sofree 当壁纸，硬了，拳头硬了。
开赛之前和队友扯一些垃圾话，并环绕观察周围队伍的名字。
左：文清*，队名忘了，貌似是看母鸡卡看的。
右：同济，『样例过了就算队』，好凡庸的名字。
前：没看到学校，『咕咕嘎嘎嘎嘎咕咕』，真是一对。
前左：没看到学校，『咕咕嘎嘎大冒险』，苦命鸳鸯。
后：忘记啥学校了，『还没启动还没启』，还在乳机还在乳。
三楼机房/5.17 Sun/9:00
开赛，qifan_maker 狂暴开袋，获得了三份试卷，这是好的。
qifan_maker 熟读参赛叙述，上机成功找到了 IDE、实时榜单和提交入口。
我在一旁翻看试卷，反复确认后指出 A 题是签到，并指导 qifan_maker 进行编码。
但他非常不适应新键盘，导致我们队三分钟才过题，但至少没挂（笑点解析：有相当一部分队伍的 A 都挂了一发）。
不多时志愿者送来了一个红气球，qifan_maker 说一个气球一道题，我环视了一圈，貌似有气球的队伍不多，应该是志愿者还没那么快把所有气球送到手。
qifan_maker 看 E，小郭同学看 I，我看 B 并迟钝地发现这是唐题，于是我上机写代码，并同样发觉这个键盘就是史。
写了个冒泡排序，写完了并尝试测样例，反复尝试编译但均以失败告终（蛤？），最后尝试重启 IDE 并发现代码被吞了（蛤？？？）。
无奈重写，一发过（21 mins），似乎还行啊。
发现此时榜单上有人切 I，小郭同学便上机写 I，感觉他码速比较悠哉。他说他直接模拟题意写了一个 dij，并同样一发过题（43 mins）。
qifan_maker 尝试拉我一起看 E，但是我不认为 E 题可做，看了 5mins 后放弃了，此时榜单上有人过 H。
我们暂时陷入困顿，我对着胃口看了些题：
C 的图论看着像什么二分答案和 floyd 之类的东西，不过很错。
D 字密密麻麻的不想看。
F 神秘一笔画改版，怎么看着怪没思路，放弃了。
G 数据结构？小郭同学说他似曾相识，并宣称应当向线段树方向思考，但我和 qifan_maker 都表示没什么点子。
H 粑粑博弈（原题名如此），qifan_maker 再看我就没看了。
小郭同学说 J 应该和 kruskal 重构树搭挂，不过完全图生成树还是比较要下苦思，让 qifan_maker 看吧。
K 看着很线性代数，感觉我很行，但是没有很投入思考。
L 数论，回忆起来
M 看着好困难，弃置。
三楼机房/5.17 Sun/10点左右
比赛已经过去一个小时，我们进展很慢。
qifan_maker 发现场上很多切 H，并开始与我讨论 H 题。
他直接猜先手只会取
进一步思考：如果
即此时先手只能取偶数，即至少取
感觉很对，让 qifan_maker 对原代码进行了修改，并手模了些样例，无误后确认提交，过了（1h）。
qifan_maker 突然发现机器队切了 C 题，于是我开始重新思考 C 题。
感觉 floyd 不可做啊，还有什么
等下好像有个东西叫矩阵快速幂...？！
但每次询问做一次矩阵快速幂也扛不住啊，哦等下原来路径长度是固定的吗，那没事了。
我会 C 了！！！抢夺机位进行编码，一发过样例，一发过题（1h 37 mins）。
成为了高贵的五题队，排在榜单很靠前的位置（rk 3）。
三楼机房/5.17 Sun/11点左右
很多人过 J，机器队也过了 J，我们都掉到 rk 5 了，于是 qifan_maker 和我力攻 J 题。
qifan_maker 经过思考提出了公因子虚点的思路，非常具有启发性。
去重之后，因子个数之和为
然后跑 kruskal 重构树，上面写个剖就求 LCA 就可以回答瓶颈值了。
但是直接跑 kruskal 要排序，
后来我去上了个厕所，猛一惊，直接从大到小枚举因子，边权不久自动排序了嘛，wssb。
开写。我的问题，过程中思路一直不太清晰，写 kruskal 重构树写了很久，然后挂飞了。
大概调试了半个小时 ，排名慢慢掉到了 rk 8。修了一堆小锅之后实在找不到锅了，打算手模样例看看建图有没有错...
这个时候小郭同学只一抬头：
欸你树剖 LCA 应该是
dep[top[u]] < dep[top[v]]啊，不是dep[u] < dep[v]啊。
然后过了（2h 38 mins）。
现在成为六题队，榜单 rk 2。
三楼机房/5.17 Sun/12点左右
发饭了，kfc 的外卖盒，一个汉堡两袋小零食，其实感觉不是很顶饱。
我们六题之后挂机了很久，一直不知道做什么题。后来小郭同学说他看不懂 D 的题面，所以我就去看了一眼。
看完之后我立马觉得 D 就是绝世唐题，写个换根 dp 就好了，然后准备控制别人去写代码。
但是它们都对个人的 dp 能力表否定，所以我还得继续自己写。
本来觉得时间应该非常充裕，结果我错了，我锅了很久，非常久，并且这次没人能帮我。
三楼机房/5.17 Sun/13点左右
结赛一小时时封榜，这时候我们是第五。
我们很痛苦的在罚坐，互相扯皮来磨过这段时间。
最后我调对了我的 dp，但是发现它其实假掉了。当时我有点破罐子破摔的想法，不想修它了，但是出场之后还是有点后悔。
其实还倒回去思考了一下 K，然后有了一些点子：
如果提前把带入的值取离散对数，乘变加之后，操作可以理解成线性变换，遂矩阵处理。
不过时间复杂度还是很劣，因为矩阵乘法至少也得是
有些人都提前离场了，但大部分人还是看到了完赛的屏保动画（怎么又是 sofree
一楼讲堂/5.17 Sun/14:00~忘了几点（六点？
好堵的出门。qifan_maker 消失了，和小郭同学捡好东西润了，到外面再联系 qifan_maker。
把队牌（好丑，拉黑了）和气球带走了，六个气球中三个萎掉了，qifan_maker 弃置了其中两个萎掉的气球。
我们教练跑掉了，所以跟着二中的教练出门。在先骕楼二楼又看到了那个 coser，有点好奇它们打的怎么样。
讲评和滚榜在一楼的讲堂，刚好在楼下和人机队会合，但是初二的小贫友消逝了。
据肖某言，初二小贫友全程挂机，高一欸哎一直提供罚时，他则血战血流，战至自刎归天（？），切了六道相同的题目，并同样写 D 并没写完。
由于罚时，它们比我们排名下十几名的样子。它们 A 挂了一发（笑
来的比较晚，座位很零散，被迫坐在礼堂很后面的位置。欸哎由于没有带眼镜还必须被迫在手机上看直播，获得了 10s+ 的延迟。
一开始主持人在那边扯一些 P 话，然后讲评。展示难度的时候，下面全场都沸腾了：
原来 C, H, J 题根本就不是简单题，反而被定义为简单题的 D, F 都没有人切。所有人的切题风向都被榜一大哥给带偏了！
E 和 M 是防 AK 题，幸好没去想。所有人都过了 A，签到题成功让所有人都签上了到。
坐我前面的女生看起来实力不是很行，一直在手机 qq 上和群 u 抱怨好多图论题，以及 D 题换根凭什么被称为简单题（你怎么这么没素质还带窥屏的
讲题解。A, B, C 不听，D 大概差不多，E 听不懂，F 被吓哭了，咋原来是模板题。
讲到一半的时候被糖糖主持人截胡了，开始打广告，然后滚榜。
光速滚完铁榜。十分引人注目的是铁牌第一，队名叫做『拿到牌子让队长女装』，为他们的队长感到好运。
刚开始滚榜的时候挺新鲜的，后面惊讶地反应过来主持人要念整整三百个名字和不计其数的客套话，突然反应过来这个下午将会是如此的漫长。
由于本文编撰时间距离比赛结束已经过去了太久，所以我忘记了滚榜时的很多趣事，只能梦到什么说什么了：
-
主持人好人机啊，一点梗都没有。
-
有一个队名是『听说南昌有妹妹跳舞我们就来了』，希望明年能有。
-
流萤队拿了金牌，名次在我们下面。
-
有一个队名是『故障机器人』，哎，哎哎。
-
由于打星队伍太强，导致金牌不够了，所以打星队伍没有金牌，只能之后邮来补（damn！！！
有很多队伍都在最后一个小时内发愤并翻上了金牌，我们原本封榜前第五，最后掉到了第八，貌似被师大的一个星队给翻了，哭，痛失打星 rk 1。
出乎意料地，最后主持人公布了一个神秘事实：原来榜一大哥其实也是打星队（但是他们忘标了），并且这三位老哥一个个都是人中豪杰。
据传，他们仨之前是某次区域赛冠军，还拿过决赛金牌，好像其中一个人目前还是成七的教练，畏惧了。
最后主持人决定找原第一借用一下奖杯，拍完照之后还回去。怎么感觉这么丐...
滚完榜之后场地里还有 eps 个人，没啥人听题解了。讲评人估计也不得劲，把 ppt 念了一通就润了。
原来 G 题真的是线段树：
-
一个区间内删掉所有极长合法括号子串后势必形如
))))((((，只要记录左右括号个数。 -
查询时，在线段树上二分一下对应括号的位置，就可以做到
O(\lg n) 的合并，时间复杂度就是O(q\lg^2n) 了。
L 题也好牛啊：
-
发现
h(x)=x/\varphi(x) 是积性函数，其中h(p^k)=p/(p-1) ，所以y|x 时必有h(y)\le h(x) 。 -
因此去除掉最大公因数的限制，拎出来每个因子并思考它的所有倍数，问题就变成了找区间内的最大和次大。
-
然后你发现，只要找到每个数前面的支配点（第一个比他大的），再找它后面的支配点，则最大次大点对势必为这样的支配点对中之一（因为他俩之间的数一定比他俩小嘛）。
-
所以预处理出来所有这样的点对，然后再在上面离线询问扫描线就好了，复杂度俩老哥。
K 题我居然只差一步之遥，太可惜了——
-
你发现矩阵乘法太劣了，但是矩阵乘向量是很优秀的。
-
所以你把快速幂改一下，时间复杂度就变成
O(qn^2\lg k) 了。 -
BSGS 要调一下块长。
剩下的没怎么认真听（卧槽这 E 这 M 是啥啊），最后也是快活地跑去吃饭去了。
怎么下发的背包不会系背带，求助欸哎，哎呦我去欸哎牛逼，这背包真好用。
一楼食堂/5.17 Sun/忘了几点~忘了几点（七点多？
吃饭，有饭票就是豪横，啥都敢点。瞧瞧这卤肉，这腐竹，这个那个... 哎呦我去怎么这不是卤肉是鸭脖啊，这下难绷了。
二中教练获得了数量惊人的附加饭票，给我们提供了充足的饮品资源，甚至还令我带两杯饮料回去给我们教练喝。
（内心 os：唉感情真好，羡慕了。
我获得了国窖牢大（大瓶装），qifan_maker 获得了蓝色洁厕灵，欸哎获得了神秘小众饮料（茶
自己点的菜就是安心，一点都不辣。我爱 JXNU 的食堂，比五中的还便宜。唉，想广二了...
就是有点腻，有饮料就还好。酒足饭饱，饮料装包，撤退了。
行程上得知小郭同学急着赶高铁，要回去复习文化，畏惧了，文化课狂魔恐怖如斯。
路上比较无聊，一直看欸哎玩 2048，看这操作怎么感觉有点像 deekpsee 老师（糖
地铁很快啊，中途转了一站，大概四十分钟就到了翠苑路。要返校了嘛，我的作业还一笔未动啊，死了啦...
附加内容（无意义）：
校内机房/5.17 Sun/忘了几点~快到十一点
成功教唆欸哎留在机房，决定找个借口把作业翘了，赫赫。
我决定要入坑 CS！在机房电脑上安装蒸汽平台，不过网速堪忧啊。
一直刷 B 站，好颓废啊。
刷的好晚，刷到十点五十了，要被阿姨肘飞了，溜了。
hyw