10th CCPC (ChongQing) 游记

听说可以投官方了，开个坑先，欢迎催更，更完了。

后面应该大概还可以更个 49th ICPC ShenYang，再说吧，鸽子要去整点薯条了。

\mathsf{10th\space CCPC(ChongQing)\space Swimming\space Log}

咕

Day -1

不咕，因为本科生教学检查不能请假，加上重庆与武汉之间极其优秀的交通，我选择了红眼航班。
写下这段话的时候是 20：30，准备收拾东西滚去天河机场乐。
可能到机场或者上飞机继续更了。

飞机困困，坐的红眼航班，快十二点从天河起飞，一点多到重庆，先在机场旁边找个酒店沉睡吧。

不过重庆这个机场和学校的偏远程度都快赶上武汉了，明天也不能爽睡，稍微早点起来滚去重庆大学。

落地发现一些本来该周五晚上做的事情都搞忘了，也是赶路兴奋把本来该做的忘光了。

然后其实 Day -1 在两个小时之前已经结束了（？

所以晚安，Day 0 见

Day 0

在机场边酒店睡到差不多 10.，打车去重大了。

感觉不知道是重庆道路规划比较厉害还是车少，三十多公里十分的畅通。

签到领了衣服和牌牌，先去吃个午饭。
随机在路边挑了个火锅店，体验的确很不错，感觉随机挑选重庆火锅店放去学校边上会被吃爆。

吃完饭和一个队友去 2v3 热身赛了，热身赛感觉很数学，A 是个数数，被队友秒杀了，B 好像是个生成函数，推了一半把剩下的给队友又被队友秒杀了，C 倒是很简单，同一种货物的买与卖可以看成左右括号，然后跑括号匹配，询问就是问区间内有多少对匹配的括号，那么记录每个右括号匹配的左括号位置，做个二维偏序就完了。

本来想写一下的，毕竟好不容易碰一次电脑（
但是被队友 80 了，也很快被队友写完了。

我们两个实在是太厉害了！!1

时间还早，主要是一起来重庆的没有很多认识的人，也没有出去玩的精力，于是直接缩回酒店打了会游戏就到傍晚了，感觉莫名的很累，于是打开双城之战一边看一边睡着。

晚上吃了点夜宵，洗澡结果浴室地漏堵了，洗的时候没发现，发现的时候浴室的水都漫到外面去了。差点在浴室开始游泳，然后外面洗手台下方的地漏堵了不说，位置也不在地势最低处。清理了地漏然后喊保洁来把水推了。

睡着的倒是很快，也没什么压力的感觉，虽然上个赛季一边鱼鱼一边拿了两个银首，倒也没觉得是个很大的遗憾，正常打（又不是没有人带

Day 1

因为做噩梦比闹钟早三分钟醒了。
玩了会手机，知道回笼觉肯定没得睡。
也并没有早饭打算，加上上周末南京窜的经历，也不敢去买咖啡喝了。就收拾东西退房去赛场了。

进场排了很长的队伍，发现甚至在安检？现在都管这么规范了吗。

进到赛场，台上的老哥在和志愿者确定到场队伍数量，原本是 278 队，如果缺 3 个以上的队伍的话金可就要少一个咯。

因为进场拖沓延迟了 20 分钟开赛，开场让我坐的机器位，简单改了一下 VSCode 和 CodeRunner 配置，主要是配置文件 IO，然后看了眼 B 题，没读完就去看别的题了，很着急的在找签到，然后看到榜上有人过 J 了，让队友看 J，自己很迅速的读完 B 并且也知道是个签到了，也开始写。写的差不多的时候队友 J 的结论也有了，于是把 J 的代码两行一写交上去了，回头把 B 写完，有个浮点数结果四舍五入的问题，印象里是直接 +0.5 转 int 就行的，但是样例二过不了，浮点数误差魅力时刻。

队友好像把题读错了然后在我后面说了句直接用 ceil，然后我也不知道咋回事就信了交了发 ceil 上去随后马上意识到自己的笨蛋，把 原本的 +0.5 后面再加了个 eps 就过了。

后面貌似写了个 K，然后队友会 E 了就把机器交给队友，开始嘴题目，解决了 I，另外一个队友跟我讨论了一会 C 之后去厕所顿悟了 C 回来跟我讨论完善了解法，然后喂给写代码发现有地方假了，不过队友很快把做法改好了，提交上去挂了，思考过后是两列的情况没处理好，过了 C。

随后写代码的想 A 没想出来，交给另外一个队友想 A 然后被秒杀，写了个状压+分组背包的东西，听起来就好重口味啊（

然后另外一个队友猜了个 D 的结论和写代码队友合力过了样例，但是始终都是 WA，看起来貌似被卡住了，问得做法后前提出疑问，原本的想法是假设 b,d 通分之后不会引入除了 2,5 以外的新的质因子，然后枚举通分之后的结果去算 c ，假设 b 去除了所有 2,5 之后剩下的部分为 p，那么 c 和 a 相加之后就是 p 的倍数。但是这么算出来的 c 是一个 c^\prime+kp 的形式，导致可能加了几个 p 之后可以和 d 约分，举了若干个反例思考之后，决定直接枚举通分之前的分母然后通过不定方程去算分子，于是他们写代码我看看题，看完 H 感觉其实是可做的，但是没啥队伍过的样子，然后被叫去看 M，不久之后队友通过了 D。

这时候基本上就没什么题有队伍过了，看完 M 之后我有一个结论跟队友说，给定一个序列，那么这个序列的值就应该是所有长度为 3 的子区间的中位数的最大值，队友认可了这个结论，但是还是解决不了之后的计数问题，之后就是他们俩一块讨论我单想。

如果确定了中位数是谁的话，整个序列可以被划分为三类数字，分别是等于、大于、小于中位数的数字，可以简单的认为是 0,2,1 三个数字，然后要求最后操作的结果是 1。

然后如果我们可以枚举这个 1 具体等于多少的话，对于整个序列，我们可以进行一个 O(n) 的 DP 去算有多少个序列的最后结果是这个中位数，并且思考容易发现这个 DP 的结果是一个关于中位数的 n 次多项式。

但是我并不会多项式，加上本题的值域达到了 10^9，我就问队友给定一个 n 次多项式 f(x)，能不能快速求 \sum\limits_{i=L}^R f(i)，但是队友听到多项式还没听我说完就说不会了，那我也只好作罢。

此时差不多封榜了，再翻翻榜看到浙师大过了 H，于是去看 H。

还是跟之前一样的感觉，把符号都分一下类，然后记 f_{k,x} 表示进行了 k 轮操作之后下标 模 p 为 x 的字符 ASCII 之和，然后按照规则可以 O(1) 转移算一算就好，就是细节特别多，于是我跟写代码的队友一起写，他写代码我报规则提建议。

一会也写完了，过了前两个样例，准备提交的时候我看到还给了大样例，然后让他下载了大样例测试了一下发现挂了，不知道咋回事，我和写代码的队友都觉得写的很仔细不应该出问题，试了一下也不是 long long 的问题，于是表示写都写了，比赛也没多久了，先交一发得了，第一发交了 MLE，因为理论空间是 480 M，但是队友两个九百万的数组都多开了一单位，于是紧急改小，准备再交的时候发公告说第三个样例有误，顿时释然通过了 H，同时痛骂 THU 出题组草台班子，加上本场题本身也不是很均衡，大把大把的数学相关，不是很舒服。

9 题稳金，剩下时间也不够写 M，何况都不会，于是开始看榜指点江山，队友指着两个学弟队伍：都多过一个的话 8 题都有希望。

赛后直接问多少题，一队罚时比较低，一队罚了 8 发才过 D，于是认为低罚时队伍也稳了，去食堂搓餐券的路上一路香槟都快开到常凯申故居了。

学弟们过了 M，遂询问做法，发现几乎是做对了，因为 f(x) 是一个 n 次多项式，那么其前缀和也是一个可以通过插值得到的多项式，所以就把前缀和多项式插值插出来，然后用 F(R)-F(L-1) 去算刚才的做法就做完了，感觉有点点可惜。

在食堂痛快消费餐券：

回来的时候已经在滚榜了，然后 8 罚过 D 的队伍不出意外的寄了，但是低罚时的队伍以 8 分钟的罚时劣势拿到了银牌第一名的好成绩，于是痛斥队友香槟塞子冲破地板把学弟开飞。

最后是拿了 rank13？不过发现就算过了 M 也只能去到 rank 9，感觉区别不是很大（

之后队友要去讲课，我背着很重的背包去找武大的 friend 聚餐，在路口的台阶随便坐着歇会，抬头看高楼还得高仰起头，顿时觉得自己好小一只（

然后是同样的红眼航班，20.30 打车去机场，22：55起飞，快两点才到寝室，飞机上邻座的大叔喝了不知道多少酒，呼吸之间都是酒精的味道，下飞机之后有种我也喝了酒的那种奇怪的恼怒感，爬回寝室睡个好觉吧，后天软件工程还得验收呢。

匆匆一瞥了重庆，没有旅游的悠闲，偶得的感悟只有飞机起飞前戴着耳塞听着歌，几乎没有一丝杂音的安静，在发动机的震颤之中问了自己一句：

你听过自己心跳的声音吗？

LeavingZzz, November 11th, 2024