CCPC 分赛站 郑州站 游记

· · 生活·游记

:::warning[剧透警告]{open} 警告：本文包含剧透内容，涉及比赛包括：第 11 届 CCPC 中国大学生程序设计竞赛济南站，第 11 届 CCPC 中国大学生程序设计竞赛郑州站（热身赛），第 11 届 CCPC 中国大学生程序设计竞赛郑州站。 :::

2025.11.21 Day 0

抵达郑州时正是午后。大街上没有几个人几辆车。

郑州的红绿灯有些神秘，部分红绿灯是不显示的，需要通过其它的红绿灯推断当前信号灯的状态。

到达酒店，放下行李，与队友一起出去吃了烤肉。回酒店，_Vector_ 说要睡觉，于是不想睡觉的我决定到 real_man 房间。

然而实际情况是，real_man 过了一会儿也睡了。

然而实际情况是，我过了一会儿也直接趴在桌子上睡着了。不过我睡的时间并不算太长，以至于我醒来之后发现 real_man 还在睡觉。

等到大家都睡醒了之后开始 VP 济南站。

根据武汉站和沈阳站的经历，似乎我应该上来先看 C。于是果然发现 C 是大水题，一个 DP 秒了。于是写了一发。挂了。发现把字符串长度上限设为了字符串个数上限，改完过了。

这都能罚一发？

然后看 M，不会做。看 L，感觉可以对每一层分开考虑，交换两个人的时候暴力修改一下。这样是修改是 \log n 的。然后查询的时候把所有涉及到的线段全部查询一遍，也是 \log n 的。感觉很对啊！

显然我是不会写数据结构的。于是简单的跟 real_man 交流了一下之后他去写 L，我继续往前看。

看 K。先大胆猜测了一下答案不超过 1。显然如果 Alice 的第一张牌的另一张也在她手上，那这一分是不能阻止她获得的。否则应该有办法阻止她得分吧？

那我对于她手里自匹配的牌，只要在每一对这样的牌前分别加一张自己手里的匹配牌就行了。至于我手里与她手里都有的牌，我只需要把她出牌顺序的序列记下来，然后向后平移一步就行了。

L 还在写，我先去看 F。

F 有些段是固定的，这些段的代价不可避免。剩余点如果有超过两个选择方案，那必然是可以和前后独立出来的。否则试一下这一组连续二选一段落能不能与前后都错开，如果不能的话中间花 2 的代价调节一下奇偶性。

那如果一段只有一个数，且它总是会和前一段或者后一段连上呢？

那就总是选较短的一段连上，如果一样短选前面那段。因为一段最多加两次，所以这样一定是不劣的。

还有 E。E 直接对于每种颜色建一棵虚树，然后枚举虚树上每个点是多少个集合的 lca，以这个集合作为 S，统计一下外面的 T 的数量（这个大概可以启发式合并）就行了。当然代码量巨大。

此时队友表示 L 要看一下。于是我把 K 先写了。一发通过。接着 L 也过了。

接着就开始写 F。写完提交，挂了。

为什么呢？因为单点的情况没有判它是否与后面那段相等。改完提交，还是不对。

为什么呢？因为我把 2 选一写成 3 选一了。改完提交，还是不对。

为什么呢？

现在 _Vector_ 在想 A，real_man 在想 E 有没有好写的做法。我在对着 F 大眼瞪小眼。怒调 2 小时无果。

最后发现是在填数的时候使用了假定法，但反悔的时候忘撤销了。改完过了。

那这场倒闭完了，而且后面我也帮不上忙。

不对，好像 H 非常可做！

用常规的二叉树数量统计的方法先写了个框架。接着经过长时间的推导和对数据的拟合，把小样例全过了！

就是……模意义下除以 2 怎么做？

怎么模数可以是合数？？

那没救了。

A 题最后会了，但也没调出来。

彻底失败。

感觉被 CCPC 克制了啊，一个 Ag 两个 Ag。不过往好处想起码不是个 Cu。

感觉后天（不过已经后半夜了，所以说明天更适合？）也要 Ag 了啊！不管了，前面那 20 个出线队打不过也正常。

2025.11.22 Day 1

上午签到。签完到差不多已经是吃饭时间了，于是在学校食堂吃饭。

食堂离比赛场馆相当近，而且选择非常多（起码对于一只猫来说够了），满意度 + +！某某赛站学着点。

怎么一个学校的所有队伍的牌子是一起发的？我们还要把另一支队伍的牌子带过去他们才能进场？满意度 - -。

吃完饭回酒店睡大觉。看到牌子上标的 3 点半的热身赛，我定了个 3 点的闹钟，然后就倒在床上晕过去了。

下午 2 点 50 醒了。迷迷糊糊看到隔壁队伍在群里问“你们什么时候出发”。

“我们再过几分钟出发。”

“那不是开始热身赛了？”

诶？不是三点半吗？

“胸牌错的，要看册子”

于是赶忙叫醒队友紧急行动，慢慢赶到赛场（跑步可能会快一点，但谁会刚睡醒就跑步的？）。看热身赛。

A 题是原题，直接找所有的最大值就行了。于是 real_man 写掉了。

B 题 n \le 10^4 的数据规模非常神秘啊，这个题难道是双 \log？或者是根号带 \log？

“哦它好像暴力就行了”real_man 说。

哦它好像 n^2 还要再除以一个二的！那 5 \times 10^7 就说得过去了。

至于 E 题……猜出题人生日？？

究竟是谁想出来的这题？？

通过 QQ 群侦察找到了一个出题人的生日，不过我不确定它对不对（毕竟我 QQ 生日也填的是假的），于是我决定先看后面的题。

“C 题枚举前面加多少个数推推式子就行了。”_Vector_ 说。

“那要不你写一下？”real_man 说。

“不行，我要压榨 real_man！”

那既然他们都会 C 了那我直接看 D 吧。

D 是个树上计数题。我先提出了一种树上背包的做法，然而在换根的时候遇到了问题——树上退背包（应该）是 O(n^3) 的（网络赛的“美好”回忆）。然后接着 _Vector_ 也提出了一个做法，不过我感觉不是很对。然后 real_man 的 C 也卡住了。

于是我上机把 E 写了，发现之前搜集的信息居然是对的。然后顺便测试了机速，用题目中给出的式子能跑 1.5 \times 10^8。当时觉得很慢，但后来意识到取模本身是个很慢的操作，突然意识到机速实际上应该很快。

然后 C 到最后也没调出来式子错哪里了。

被热身赛击毙了！

晚上在路上想出来了 D 的做法。感觉挺有道理，不过也没心情验证了。

晚上随便跳了几道数论题。第一题是个大水题，被 _Vector 秒了，一看 *2800，感觉完全没有这个难度啊！第二题猜出结论了不会证明，一看证明发现看不懂。数学定理这一块。第三题完全就是天才啊！一开始我和 _Vector 完全没有看出来这是哪门子数论，结果一看题解，对那个 x + y - 2z = k 的式子，它先对 2 取模，然后递推到对 4 取模，再递推到对 8 取模……这是人能想出来的？出这题的人做梦都要笑醒吧！

上床，很快睡着了。

2025.11.23 Day 2

早早起了床，去学校吃了早饭。不过好像都是我在吃，_Vector_ 习惯性不吃早饭，real_man 也只是点了一杯豆浆。

背包不能带进考场。不过存包处秩序还挺不错，从这点来讲应该夸夸承办方。

手机记得关机……诶我手机呢？！

于是 real_man 陪同我赶到的食堂，发现我手机落在食堂桌子上了。还好没丢掉，不然真随时都有可能失联了。

开场了。

根据前两站的经验，开 C 题准没错！于是开 C 题。

哇是 n \le 700 的数数题，我们完蛋了！于是滚回去开 M 题。

M 题看起来就比较简单了，而且榜上也陆陆续续的有人过了。这题应该不难！让我想想。

假如第一位是 1 的话，那有效长度至少为 n-2 吧？那比较一下第 2 位改为异或和倒数第二位改成异或哪个更大就好了。如果第一位是 0，但第二位是 1，那就要多考虑第 3 位该为异或。否则把第 2 位改为异或总是最优的。

上机写了一发，29 min 提交，WA 了。一下子调不出来，此时 real_man 会 B 了，于是打印代码，让出机位。

过了一会儿发现是前导 0 的判断有问题。45 min 的时候 realman 过 B 了。于是我上机改了一下，又交了一发，又 WA 了。此时 _Vector 会 G 了，于是继续让出机位。

再看了一会儿发现有个分支写了个小错误。于是直接上机改。64 min 再提交，终于过了。

完成了本场卡题任务！接下来一定会很顺利吧！

_Vector_ 随后把 G 写完了，68 min 提交的时候没过，稍微改了一下，70 min 的时候过了。

接下来看 J，推了一下找到一个非常优美的性质啊！real_man 上机一写，怎么对不上样例？

“你这个结合律少异或了一个啊。”real_man 说。

哦，式子推假了。那怎么做呢？

接下来 real_man 开始打表找规律，而我尝试从理论角度进行分析。两个 b 差 1 的性质是显然的，可是 a 的性质就比较神秘了。前面几组似乎是两数之差是 2 的幂次，但后面又拟合不上了，不过 real_man 倒是提出了一个非常有用的观察：对于每组 a，对其造成贡献的 b 两组之间差的也是 2 的幂次，且从哪个 b 开始似乎有一定的规律。

后来，我意识到两个 a 一定先是一段相同的前缀，然后再是中间的 01 是交替的，并且最后一位是相同的 0。怎么构造 b 呢？异或上一个 1，相当于把交替段的某一组 01 交换。我们只要把交替段的第一位换成 0 在上 1 在下，后面全部是 1 在上 0 在下，那加 2 之后就相等了。那前面的所有观察都说得通了！

于是上机写代码，155min 时提交，挂了。难道我这场要卡两个题？

于是写了个对拍，磕磕绊绊的把问题拍出来了，发现之前的代码允许结尾不止一个 0，而是有多个 0。改完再拍，没拍出来，感觉很对，176min 时再交，又挂了。

为何呢？

此时 _Vector_ 的 D 会了，于是我打印代码，让他上机写。瞪眼等了一会后发现有个地方循环上界小于等于写成小于了，改完再交，162min，过了。

怎么已经进入后半场了？

接着 real_man 和我说了 I 的一个大致思路，说是能用多项式优化但显然这题不能这么做。我花了很久才理清楚他的思路，然后也不知道怎么优化。接着他又提出了一个 O(n^3) 的做法。这个做法很容易懂，而且看起来很简洁啊！于是我又开始思考怎么优化它。

趁 _Vector_ 整理 D 后半段的思路时，real_man 上机验证了一下 O(n^3) 的式子，过样例了。当然不可能直接通过题目，但这是个很大的进展！

就是……这带个组合数系数还不定，怎么优化啊？感觉很困难啊！不过一定是因为我太菜才想不出来的，这感觉很像正解啊！

于是乎我最终终于在数小时的思考后放弃了。转向其它题目，也是一个比一个不可做。

D 也写不出来。

整个后半场，我就像无头苍蝇一样乱撞，做不出任何实际的贡献。而且这还是 CCPC 赛场，没有部分分能打——比起虽然不会做题但总是能想特殊性质的省选来说，坐牢多了。

最后时刻 real_man 想出了一个和前面的做法毫无关联的容斥，而且听起来更有道理了！

就是没时间写了……

于是比赛结束了。

吃饭。马斯卡彭好吃！

一定是上海那边把郑州献祭了，上海要 3 Au 了吧。

怎么上海那边也倒闭了？

看讲题。real_man 说 I 题最后想的做法完全正确！有点可惜。不过多一题也金不了，倒也算不上遗憾了。

K 题跟我想的第一步就对不上。哈哈！

滚榜，毫无疑问的银牌了。

听说上海三块银牌。我们学校银麻了。

不过没关系，至少还是银牌中位，比 VP 济南的银尾好！不是铜牌就不算输！

上台领奖的时候借了队友的猫耳帽子。怎么感觉我比队友更适合这顶帽子？

赛后和同校另一支队伍一起吃了晚饭。一支签一块钱的火锅，性价比还挺高。晚上坐高铁返校。

感觉这场银牌也正常吧，不是说哪道题明明会但是没写完（其实 D 题算这种情况，但问题是 D 过了也是 Ag），纯纯是题目不会做。不过后半段完全零贡献有点对不住队友们了。

武汉的 A 题，沈阳的 A 题，还有这场的 I 题，怎么每一场的数学题都没做出来？这下必须要加训数论还有计数了！

两场 ICPC，一场 CCPC，学期内的比赛也就圆满结束了。下一场，我们 EC Final 见！