CCPC2024 区域赛（济南）游记

2022 年我写了最后一篇 OI 游记以后，这个博客就暂停更新了。所以时隔两年再次写游记，文笔、想法可能和以前有很大的差异。

9.7 ~ 9.29

进入大学，学校分配了队伍。在九月打了三次网络赛，校内队伍排名 RK 6。不过学校一队太强了，平均每个队都能分到 3 个名额。

我们是新队，可能还需要适应比赛，在讨论间商量了一下，我们打算先打 CCPC 作为试水。然后哈尔滨太早了不太想去，于是选择了济南。

虽说我是队长，但准确地说是行政性质的，负责队伍的报名报销交通食宿等等（）

Before the contest

进了济南的比赛群，群里很活跃，包括主办方的鹿老师。然后发现哈尔滨的选手也在这边水群，原来他们群禁言了（）

之后得知比赛给每个人提供了 100 元的美团卡，以及赛时提供麦当劳午餐，让我对这个站的印象还挺好的。

10.20

赛前一周和队友 VP 了 2023 年哈尔滨CCPC，结果不如人意……发现自己漏洞还是好多，这一年还得要积极复健。

10.25

和队友商量了出行方式，感觉地铁还是麻烦了点，而打车可以从宿舍楼下直接开到航站楼，然后人均价格不是很贵，所以选择了打车。

晚上十二点睡的，但是是星期五晚上，某舍友在打 CS2。不过他带耳机打的，我有床帘，所以问题不大，就睡了。

10.26

6:40 起的，结果发现昨晚打 CS2 的舍友已经起床了，他和某同学约好 7 点开 CS /jy

收拾好后就悄无声息地出宿舍了，去吃了点早饭后 7:40 和队友会合，叫车去机场。上初中以后这还是我第一次坐飞机，以至于到机场以后不知道要先去值机（）

不过时间还是挺充裕的，我们 8:50 就到对应登机口，距离预计起飞还有 50 分钟。（其实延误了，10:10 才起飞）

结果小航班公司不提供免费餐食，拿了一瓶咖啡付了 10r（悲）

下飞机后就直接打车到高新国际会展中心，领完物资拍照后刚好赶上开幕式，有看了几个节目。同时面基了高中时期的两个学长。

热身赛的时候感觉键位有些不适应。开赛后全队打了前四题，被第五题硬控了。赛后知道了这是原题，然后合法解构造地非常简单，感觉自己降智了（）

晚上和其中一个学长吃饭，回来后也没复习什么，就用电脑准备了一个交流课的 pre，然后感觉好疲倦，10:30 就上床睡觉。

10.27（比赛日）

6:45 起床。三个人吃了早饭就去现场。看到了现场百余个穿红+黄色卫衣的山大志愿者。他们有的已经入场，有的在门口给气球充气。

进场之后发现键盘上放了三只小熊。试题袋和档案袋好像。之后便是等待开始比赛。

During the contest

一开题我坐机位，就先给 VSCode 设置存放文件夹，队友先看题。然后发现 TA 们分别看 E~H, I~M。

我就先看了 A，发现是签到，就直接开写了，在 8min 的时候一发 AC 了。

然后队友说 TA 可以写 L，而我感觉 M 可做。在 TA 上机写 L 的时候我去看 B,C,D，然后 B 看是模拟就先搁置一边，而 C,D 看了又没什么思路。

队友交了 L，然后挂了，让给我写 M；我写完 M 交了，也挂了（）

第一个小时除了 A 并没有新的过题，这时我们去看排行榜发现大家都做的是 J，而 L,M 有很多队有提交，但都没有通过，于是就不打算想了。

看了排行榜发现了大家都过了 J 题，于是我们就去想了 J 题。然后降智了好一会儿才发现直接按照 $\max(a,b,c)$ 从小到大的顺序处理就是对的，在 83 min 的时候才过掉。

之后我又去尝试改了一下 M，但很遗憾还是没有通过，就彻底断了这条路了，和队友去 F。

看到 F 我很快就联想起了 CF1359E，显然条件可以转化成 $a_2,a_3,...,a_n$ 是 $a_1$ 倍数，于是组合系数是一样的，关键在于计数方程怎么转移。

一开始我想简单了，以为答案就是 $\sum_{i=1}^m \sum_{j=1}^n \binom{\lfloor m / i \rfloor - 1}{j - 1}$ 然后上整除分块加速，但是感觉不对劲，写了个暴力发现样例都是错的。

队友甚至都想到建 DAG 去数链，但我觉得没有那么麻烦。想了一会儿，发现删数操作最多只需要执行 $O(\log m)$ 次，所以马上就出来一个式子。

让 $f(i,j)$ 表示最小元素是 $i$，且保留 $j$ 个元素的方案数，那么有 $f(k \cdot i,j) = f(k \cdot i,j) + f(i,j-1)$。

由于 $j \le \log m$，这个转移复杂度粗略计算是 $\mathcal{O}(m \log^2 m)$ 的，实际上更小。

然后答案就是 $n \cdot \binom{m}{n} - f(i,j) * \binom{\lfloor m / i \rfloor - 1}{j-1}$。我去写了，加上队友的修正，最后在 167min 过了 F 题。

此时我们队伍位于铜牌区，抬头一看校内有一个强队过 6 题了，有点惊恐。然后我一个队友认领了 B 题，另一个队友说 I 可以做，然后跟我讲了一些。当时可能我猪脑过载了，好像没太听进去（）

然后写 B 题的队友写完代码后发现样例没法过，就打印代码，把电脑让给了写 I 题的队友。我又去看了其它题，感觉没什么头绪，于是也去和队友看 B 的代码。七改八改后大概改好了。

之后便是两个队友轮流交换上机。期间 I 题 WA 了两发，B 题始终有一个样例卡着了，不过所幸还是发现错哪了，不然模拟题真的会急急急。

具体细节有点忘了，反正就是 I 题恰好在封榜的时候 240min 过了，然后我去上厕所；上厕所回来后队友的 B 也过了（248min）。但是气球就定格在三个了。

顺便说一下，我当时穿着两件卫衣（里面是自己的，外面是 CCPC 的），摘胸牌时卡帽子那里了，脱了好久，感觉自己好糖（）

然后写 I 题的队友说 E 也可以写，加上 TA 说会写 python（这题有高精度），就让 TA 冲刺了。

结果逆天的是我们三个在输入数据这块编译一直过不去，浪费了不少的时间。可能以后还是要备用一些 python 板子（悲）。

最后比较可惜，队友已经争分夺秒了但是没调出来。比赛就这么结束了。最终成绩 5 题，罚时 787min。

Tutorial & Rankroll

赛后看提交记录发现 E 基本都是 python 通过的；听题解发现 M 漏了一种很特殊的情况（这道题到最后全场没有队伍通过）。

我们的最终成绩滚榜前是 78 名左右，银牌线 84 名以内，肯定能保 Cu，但感觉 Ag 没什么戏。

然后滚榜的同学也挺会整活，印象最深刻的就是滚到“锐刻没有电”队伍时用的是理塘口音。

还有一些很戏剧性的结果，比如铜首队伍是“败犬acmer太多了”，顽强拼搏奖队伍是“这是一场豪赌”。

我们队伍最终是 Rank 101，我高中一个学长的队伍有大爹，直接干到 Au。大学校内的那个强队最终也是金，第 13 名。

After the Contest & Summary

这是我们队伍的第一次比赛，取得的结果还行吧，至少没打铁（）但我真的要加练了，反应力和耐久度还是不够。

济南站的体验真的很好，如果明年还有济南站的比赛我还会来的。

【此处补上奖牌照片】

回程的飞机坐的是深航，有免费饮料挺好。排了不少珠三角的夜景图，还是相当好看的。

【此处补上夜景照片】

但是大晚上打车是真的贵（哭哭），价格是早上的两倍。一个周末打车花掉了 270 块。

然后回到学校就得准备高数和线代的期中考了。11 月注定闲不下来了。

半个月后杭州见。