XCPC 2025

蒟蒻第二年参加 XCPC，目标包保 Ag 争 Au，目前实际 Ag。

参加以下赛站：

  • 2025.11.02：2025 ICPC 武汉站。
  • 2025.11.09：2025 ICPC 南京站。
  • 2025.11.30：2025 CCPC 重庆站。

队伍配置

  • 队名：正在验证该队是否是真人。

  • name: Verifying we are human.

  • 成员：

各站游记

为避免出现大量神秘 emoji, 故以 scy 代指孙✌。

武汉

本赛季第一场。

Day -1

学了整天 MAT3007，但是学习五分钟，划水两小时。

晚上考 CSC4120，发现不会算时间复杂度，前面题大量宕机，好在后面的算法题很水，一个堆上 bfs 的作业题，一个分治双指针，一个 2-SAT。过程写的很屎，光写写写了 2h。但是有大四老登半小时就交卷了，畏惧。

Day 0

MAT3007 不出所望的炸了，准备 late drop。还好没有转移这门课的权重到期末，不然到期末直接一考挂科。

考完赶紧出考场找sky，结果sky才刚出宿舍（邪恶sky）。坐地铁赶到机场，卡着点上了飞机。

sky的同学开车来接我们。我社恐发作瑟瑟发抖，sky 同学跟他讲话，sky 竟然还在玩手机，太邪恶了。

在武大转了一圈，本来以为马上到酒店了让 scy 下来帮忙 check in，结果预错了时间让 scy 等了好久，邪恶 sky。

总之在房间里 scy 拿了3大袋物资来分赃，然后洗洗睡准备第二天比赛。

Day 1

早上起来往体育馆去，走了一会看到有公交车顺路就直接坐了两站到西门，到体育馆的时候时间差不多，上了个厕所就开考了。

开局先看了 A，猜测是否是找循环节然后通过某种方式离线所有询问，但是并未进一步想法，感觉像是类欧的形式，但是就算真的是也不会写也没有板子，遂只能往其他方向看看有没有乱搞做法，但最后也没搞出什么来。

scy 中间还把 J 丢给我看，以为是什么神秘哈希题，结果到最后鉴定为 $0$ 人题，邪恶 scy。

看得差不多发现 F 开始过的人多了，想到如果根据典中典贪心找到最少的点覆盖区间，然后直接在这些关键点上 $\log_2$ 即可。写了写过了。

EM 两道题 scy 和 sky 很快秒了。他们在看M的时候我看了下K，分析了一下答案的下界一定是考虑每种颜色，每种颜色内按位置排序，然后相邻两个匹配的总和（再除2，因为可以在往左边换的时候顺手把一个前面的东西换到后面去）。再拿样例验证了一下发现都是下界，猜测这道题一定能构造出下界的结果。又分析了一下 $\sum \vert p_i-p_j \vert $ 一定是偶数，更加确定。于是考虑了一下会使得答案高于下界的情况，一定是把同位置的另一个数换到了比匹配位置更远的地方，于是发现如果从左往右左，每次只取下一次出现位置更近的那个数换过来就可以避免上述情况，然后拿 multiset 随便维护了一下就过了。

过完这题以后 scy 在看他最喜欢的纯血构造题 C，我和sky在想H，但是交互题一直没对上脑电波，虽然想过 01trie 但是觉得 $2n-2$ 的询问次数并不像是有 $\log$ 在里面，于是直接抛弃了这个想法（可恶），然后宕机了很久。scy 的C暴力打表出一个很优美的 $3\times 3$ 矩阵，然后发现了规律，我和他验证了一下发现确实可行，考虑到我不擅长H这类的猜猜题，scy 让我上机写代码，然后他帮忙想 H。我写了一会能过大部分情况了，但是经过 scy 的验证被 $$3n+1,4n$$ 等情况卡了，于是又调试了很久，找了很多个hack，最后才蠕动着过了。

最后半小时对着H还是没有想法，遂倒闭。本来还看了B，觉得是某种优化建图，但是神秘的是当时只想到怎么用单点建图而没有想到 2-SAT，而且B过的人少没敢继续想，赛后听到 2-SAT 线段树优化建图恍然大悟，但是回到深圳补题的时候发现各种各样的算法叠到一起写了一个半小时，仍然倒闭。

$5$ 题银了，预料之内，只是一开始过K的时候非常高光，最后天神下凡脸着地非常可惜。

晚上约 cy 出来面基，饱餐了一顿，感叹 cynb，%%%。

回到酒店到 scy 房间串门，拿 scy 电脑开卡车，成功让 scy 的欧卡负债 $+10^4$ 。

Day 2

上午起床白嫖酒店早餐，然后视奸 sky 拿 scy 电脑赶作业。

下午绕东湖骑了一小圈，东湖的绿道很好骑，非常爽。

坐地铁晃了 $24$ 站到机场，回到宿舍累瘫了，开始躺平摆烂。

南京

二刷神秘袋鼠站。

Day -2

跟队友使用 deepseek 检测代码屎度，某个叫 jr_zlw 的家伙写的代码荣登屎榜榜首。

骗牢邓发了一份代码来评，牢邓发了个虚树板板，想了想之前还没打虚树板子，遂直接 copy 下来。

晚上尝试补了一下 CSP-S 的 t3，神秘字符串题，虽然能推出 A?B 按问号分组的形式，但是并不会 AC 自动机倒闭。看了下题解拷了个AC自动机板子写过去了，然后还翻到了某种离线字典树写法，感觉自己已经退化了。

看了下 t4 但是没有想法，也是延后补了。

Day -1

一大早起床吵醒舍友，然后赶飞机。

可惜南京在下大雨，只好在酒店里摸鱼了一天。

尝试补 t4 但是又咕咕咕了。

Day 0

骑电动转了两圈南航，然后到处吃吃吃。

热身赛划水被队友逮捕了，开了 E 口胡了一个神秘基环树，但是没调出来。

回去终于把 t4 的神秘 dp 写了一下，完全没想到明天还有一道更屎的 dp。

晚上继续吃吃吃。

Day 1

正赛开局在讨论应该先做哪个颜色的气球，然后再度开到不太可做题 E，想了很久没有思路。

scy 和 sky 把 CK 切了，我在想 F。一开始以为是某种神秘字典树，但是发现贪心上树的过程很难描述。然后想到可以维护每一个最终答案对应的并查集，但是加边是 $O(W)$ 的。然后开始继续研究某些神秘的优化建图或者优化加边的策略。直到最后发现实际上只会加 $O(Wn)$ 条边，只要精细实现就不会超时。在位数上拿一个 bfs 把边加进去，直到不可加入即可。

然后开了 $H$，找了 scy 来讨论：

  • （zlw）我想要得到 $f_{l,r}$ 表示 $[l,r]$ 中 PAA 串数量，请给出算法：
  • （scy）可以枚举 $l,r$ 然后二分得到以 $[l,r]$ 结尾的 border，然后对 $f_{l,r}$ 进行等差数列加。
  • （zlw）然后做个区间和，但是我不会写等差数列加，给出例子，请帮我处理。
  • （scy）可以建立两个差分数组，二次差分。
  • （zlw）现在需要枚举两侧的 PP 串，如何得到答案。
  • （scy）仍然枚举区间 $[l,r]$ 使用 border，定左端点，答案是 $f_{l}$ 的区间和。
  • （zlw）我已经写好代码，请帮我检查一下是否有明显错误。
  • （scy）答案需要取模。

尽显入机本色地通过了。

之后的两个小时继续坐牢没有过题，尝试了一下 I 题，但是是个巨型dp，感觉比某 t4 还难。scy 和 sky 在开 G，但是也没有什么想法。赛后问了一下牢周队用李超树干过去了，我们隔壁队猜到了贪心结论贪过去了。

最终还是保住了 Ag。