XCPC 2025

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

参加以下赛站：

  • 2025.11.02：2025 ICPC 武汉站。(Ag)
  • 2025.11.09：2025 ICPC 南京站。(Ag)
  • 2025.11.30：2025 CCPC 重庆站。(Cu)
  • 2026.02.02：50th EC-Final，杭州。(Fe TAT)

队伍配置

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

  • 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。

重庆

嗯，我们有打重庆站嘛？据说是牢邓后援会出去团建，送了一个铜牌。

Day -1

起飞去重庆玩，$4$ 个人打一辆车有点挤，晕车了。于是到了重庆以后改成了 $2$ 辆。

下午坐地铁去城区玩，吃了一顿大火锅（广东宝宝只能吃白汤QAQ），然后前往洪崖洞。

但是人巨多，大家都没什么心情在里面逛，只好溜出来沿着江边走了一道，过了一个大桥然后坐地铁回酒店了，江景还是很不错的。路上还领略了一下山城的迷路属性。差点看不懂导航。

Day 0

签到+热身赛，早上在校园里稍微走动了一下，中午又开始对饭票做01背包，发现一大堆根本用不完，吃的很饱。

下午热身赛 scy 去支援牢邓了，我和 sky 双排。

开局一道找规律贴脸，我寻思是不是随便填一个数都算过，输出 114514 然后寄了，sky 找了好些规律也都没过。最后无奈 OEIS 运气好选到了正解。（到底是谁在放找规律题）。

中间有一个神秘合并果子没想出来，感觉可以倍增但是细节很多。此时惊讶的发现高中 WF 老学长 Jeff 竟然就坐在我们队的前面，遂直接上去请教，貌似听懂了但是没有补。

最后一道碰见了一个曾经高中同学发我的复旦羟基题（要说他也是猛到零基础去搞复旦的信息羟基）。

受到 vp 成都站斯诺克题的启发，晚上是神秘台球时间，和 scy 和牢邓去打台球，我和牢邓都不会，遂二打一 scy。随后发现我是负收益队友，最终被牢邓带飞。

晚上还有烧烤环节，每场比赛完都要胖十斤。

Day 1

开赛了，开局先搓了五子棋。队友很大胆地开了shi题，然而并没有什么想法。然后开到了心心念念的数据结构题，M题一开始以为要用 LCT 或者 ETT，看了一会发现树最终的结构是确定的且并没有强制在线，于是可以直接开始上数据结构。但是发现若干空间带log的数据结构都被卡了，于是继续思考，发现每一个质因数是独立的。于是对每一种质因数拆开来做然后树状数组即可。

中间一直在看那道神秘 KMP，但是对 KMP 的理解并没有很深，没什么想法。

最后大家一起写神秘矩阵dp，scy写的式子有点神秘，跑出来的结果一直不太对。最后 sky 重新设计了一下状态，我验证了一下没什么问题，遂开始画矩阵，scy负责写代码。虽然配合的还可以但是 299 交了一发 WA 了，比赛结束后 5s 发现有个东西忘记初始化为 0 了，Cu 遗憾离场。

晚上继续打台球。

Day 2

又出去玩了一天，看了李子坝的神秘地铁，然后跑了个神秘景区，并没有很好玩。晚上的飞机回深圳了。

杭州

Day -3

不可打印次日的登机牌。

买错机票被迫花费600大洋改签，被迫坐午夜档飞机。被迫3点钟才到酒店。

Day -2

下大雨了，但是还是想出去玩。

scy带我们到他的母校附近吃了非常好吃的杭州菜，狠狠打破了对杭州美食荒漠的刻板印象。

然后下着雨逛西湖，全是雾，鞋子也湿透了（都怪 sky 不把雨停了）。

不像广东，树都掉光叶子了，甚至荷叶也枯了，也是很新奇的景象了。湖很大，还有鸭子在游。总之也是打卡了一下。

sky去找在杭州实习的牢周了，我和scy，sqx晚饭在酒店搓了一顿火锅，还白嫖了sky 30大洋的饭票。

晚上在酒店打游戏，看sky拿平板玩粥特别爽，sky建议我也买一个。

Day -1

中午流连在各个摊位白嫖物资，顺便签了一个道。

然后一直摸鱼到晚上去腾讯的沙龙当学术大拿，大拿茶歇吃。

Day 0

热身赛+华为挑战赛。热身赛有点摆，4道都是做过的。

先上去写了个通信题，结果发现那道通信题为了强行加交互改的很恶心。允许100次询问结果是 0~100 还得排除最后一个数。

然后帮 scy 回忆那道构造题，也是回忆起了空出最后两行构造最右下角的2*2小方形作为唯一反例。

最后scy把南京的神秘dp敲掉就下班了。

华为挑战赛之前一直没准备过，本来打算都靠队友了，结果他给的题目格式过于神秘，都不怎么会。

然后想了一些神秘2NN和神秘bf16，都因为没给一个合适的调试方法一直RE，然后就寄了。

晚上去吃烤鱼，各看了几道神秘贪心热热身，然后就睡了。

Day 1

开局上来盲开到一个0人题C，以为是什么可做的数据结构题。

然后发现 J 题有人过了，于是过去看。很快 B 也有人过了，但是那道题又是问号题，以为是一些神秘构造，于是 sky 和 scy 去看了。此时我写了一个巨恶心的3项dp式子，想了想还得继续写 $3\times 3=9$ 个式子畏惧了，此时 B 过了一车人，据说是 dp 而不是构造，于是我才从scy那里听来思路，他不会处理两个 u，看了看发现只需要每一种方案对应唯一状态即可，把第二个 u 贪心地算成ucu即可。然后把 J 丢给他们，我开始写 B。中间调试用的方法有点恶心，浪费了一点时间，发现是当新出现c而单u已经被用完时，还可以从ucu里面拆一个出来。

写完 B scy马上分享了他们讨论出来的 J 题思路，发现直接叶子两两匹配，理论上是可行的，但是暂时不会证直接构造的合法性。我想了一下这个确实是答案的下界，看起来也是可以实现的，于是先写了一个朴素dfs。然后发现出现了隔着很远的叶子匹配的情况，加了一个深度较深的叶子优先各自匹配。但是还是不对，接着花大量时间写了一个拍，又发现从下面染色到上面时会出现一条路径覆盖到之前的若干个顶点，于是又按照路径 LCA 的深度排序过了。

刚过完题 sky 马上提出了 K 题比特数为 $n$ 的做法，可以01染色。然后我意识到可以直接默认节点 $1$ 颜色为 $0$，直接做完。写了写直接过了，膜拜 sky。

然后一个叫 zlw 的 sb 把 H 题的题意读错了，以为是要总和最大，然后思路一直在往剩余数的平均值上飘。在看了约莫半小时后被 scy 纠正，然后发现可以枚举免费的 $k-1$ 次刷新出的最大值。但是我们卡在了最后要不要赌第 $k$ 张牌。由于之前看错题引出的错误思路，我一直以为需要比较所有剩余数的平均值与 $k-1$ 次刷新的最大值，导致发现剩余所有数的平均值根本无法计算。更可恨的是我当时以为组合数需要直接算出来，忘记了经典的浮点组合数概率可以递推得到的trick，认为组合数不可计算，活活把这道题葬送了，虽然后面发现了取所有数的平均值是有问题的，但也因为组合数这个不会算没有继续想。赛后问了mophie才发现组合数可以递推、以及枚举到最大值以后，只需要算更大数的后缀和（是个定值）。

然后最后一直在帮 sky 调 A，虽然好像也没帮上什么忙，神秘计算几何最后又挂在某些神秘细节上了。

最后非常遗憾的拿了铁牌第一，就差 5 分钟罚时之前少查一点bug都有牌子了。

晚上华为晚宴一直在悲伤中，但是最后抽奖补位中了一个华为平板，好耶。

我们学校一队卡线进了WF，Jeff 他们比一队高了一名，也进WF了。

Day 2

本地人带我们逃票去爬西湖后山了，山景很漂亮，有很多茶田，但是据说叶子都老了。

本来一人带了一瓶水，结果才爬了十分之一水已经见底了。承包了一整个学期的运动量。

顺便收获一张scy的帅照。

晚上飞机终于没有买错票了，但是晚点了两个小时。

灰溜溜回到尼龙，还要准备神秘 CSC3060quiz。