CCPC2024山东省大学生程序设计竞赛 个人总结与解题思路整理
本文最后更新于 2025年1月2日 晚上
赛前几天
Abut Day -20
报名，因为太菜主动单调队列了。
Day -3
被告知一位队员需要参加考试，ltr队有一个名额。
另外整个年纪的信竞都去了，周六下午没课上，只能跟着去。
Day -2
确定比赛场地，了解比赛规则，和往届选手浅谈了一下比赛策略。
Day -1
复习网络流，感觉会考到。翻开书，谁知满书上竟只写了两个字：“不会”。
Day 0
和两位大佬队友汇合，试机。
测试题最后一题在洛谷上过了，但是现场评测机过不了，不得其解。
那天很累，晚上六点半就睡了。
队伍成员
> 具有丰富CCPC比赛经验的大佬，去年曾组队切掉5题：
队长：高一 ltr
- 妥妥的信竞大佬，实力最强的一个。
队员：高一 wzx
- 退竞半年但实力依然强悍，熟练掌握计算几何。
> 第一次参赛的蒟蒻，只会看代码和造数据，三分之一时间都在打酱油：
队员：高零 gtr
- 妥妥的信竞蒟蒻，实力最弱的一个。
早上
04:00 起床。
07:45 到达比赛场地，但记错时间。
07:55 换好衣服，跑去打印店打印材料。
08:30 坐在位子上等待比赛开始。
比赛过程中
我从11:10开始吃的东西，还停不下来。wzx说得对，吃了东西之后脑子转速会降不少。
纸、笔、饮料和吃的都不缺，书也派上了一些用场，唯一的问题是我没带身份证（
试题
I. 左移
我还没看完题两位大佬就写好了，还没造完数据就A了。
A. 打印机
第一次WA了，发现界限开小了，$2\times10^{18}\rightarrow1\times10^{18}$，第二次过了。
F. 分割序列
非常顺利地一遍过。
C. 多彩的线段 2
先是按右端点排序，结果WA$\times2$，调试无果，暂时停下。
做完K之后用左端点排序+优先队列，过了。
K. 矩阵
ltr和我各给出一个构造，使用了ltr的，成圈排，过了。
J. 多彩的生成树
我一开始读错题了，误以为同种颜色之间连接不需要代价（
想了一阵，一遍过了。
D. 王国英雄
最曲折的一道题。
一开始我误以为拿初始的钱倒卖就行了，但是看了一眼榜发现没这么简单，于是认真读题（
我们写出了暴力代码，测试各种极端条件都过了，于是自信地交了上去，结果TLE。
于是开始分析时间复杂度，确定为$O(\sqrt n)$，构造各种极端样例和随机样例，分析卡死循环的条件……百试无果。
最后wzx给出除法加速循环的优化，过了样例，但是WA。改了条件，过了样例，但是TLE。
然后继续分析时间复杂度，确定为$O(\sqrt n)$，构造各种极端样例和随机样例，分析卡死循环的条件……百试无果。
看着代码，绞尽脑汁思考着能卡住的样例，我的手上全是汗，眼里尽是绝望，吃饭的心都有了。
wzx一直对我们说“稳住，稳住……”，自己冷静地分析代码的漏洞。终于在剩余10分钟时，他发现了问题：pp这个变量是除法中的分母的一部分，在特定条件下会很小，导致除法无法加速循环，导致超时。
改正，提交。第8发，293分钟，AC。
H. 阻止城堡
这道题ltr想出来了二分图最大匹配的正解，但是剩下7分钟没时间写了。
M. 回文多边形
wzx整理了一晚上的计算几何，但是他看了许久也不会做，有点可惜。
比赛后
赞助商宣讲好无聊，但是有吃的喝的也听得津津有味。
滚榜好无聊，但是有了主持人和有趣的队名也看得津津有味。
最后队名牌子和气球都带了回来。
试题解题思路
不想详细看的请前往剪贴板，这里是现场简单记录的。
以下的题解来自SUA程序设计竞赛命题组现场讲解的PPT中，最简单的几道题没记。详细题解SUA在几天后会更新到这里。
前面的题
比较简单，所以没转录。
A. 打印机
二分答案$x$，计算每台打印机在$x$秒内能打印多少试题，看加起来是否大于等于$k$。
最差情况下，$k=t_i=w_i=1\times10^9$，$l_i=1$，所以二分上界是$2\times10^{18}$。
然而$x=2\times10^{18}$时，如果打印机每$1$秒打印一份题，$n=100$台打印机一共可以打印$2\times10^{20}$份，超出了long long的上界。所以二分过程需要判断和已经大于$k$时提前返回$true$。
复杂度$O(n\log x)$。
F. 分割序列
设最后$m$段元素的总和为$p_m$，其中$p_k=\sum a_i$，则目标式可以改写为$\sum^k_{i=1}p_i$。
所以答案就是从$(n-1)$个后缀里，选最大的$(k-1)$个加起来，再加上序列的和。预处理后缀和并排序即可。复杂度$O(n\log n)$。
C. 多彩的线段 2
（说实话我觉得讲得太复杂了）
首先考虑$k$最小是几，答案才能大于$0$。
这就是经典的interval partitioning问题：最少把区间分成几组，才能让组内区间不相交。
贪心解法是：所有区间按左端点从小到大排序，维护每一组的右端点$g_j$。若存在一组右端点小于当前区间的左端点$l_i$，则将当前区间分入那一组（如果多组满足要求，随便选一组都可以）；否则新开一组。
从这个思路出发，如果我们把$g_j<l_i$的组都看成$g_j=0$可以发现，无论把区间分到哪一组，排序后的$g$序列都是一样的。因为我们把所有区间按左端点排序了，所以$g_j=0$将一直保持，直到有个区间分到了那一组里。所以答案就是每次$g_j=0$的数量乘起来。
因为$k$很大，所以用一个堆只维护$g_j\neq0$的值即可。复杂度$O(n\log n)$。
如果从弦图的角度解释，本题其实就是弦图的色多项式$P_G(X)=\prod^n_{i=1}(x-d_{G_i}(v_i))$。详见《弦图与区间图》(陈丹琦) 定理2.5。
J. 多彩的生成树
对每种颜色需要维护：这个颜色的所有点是否在同一连通块内，以及颜色之间的并查集。
模仿Kruskal算法的过程，按边权从小到大考虑每对颜色$(u,\ v)$的连边，并分类讨论。
情况一：$u=v$
若颜色$u$所有点都已在同一连通块内则跳过。
否则连$(a_u-1)$条边，标记这个颜色所有点都在同一连通块内。
情况二：$u\neq v$
若颜色$u$和$v$在同一连通块内则跳过。
否则若$u$和$v$所有点都不在同一连通块内，连$(a_u+a_v-1)$条边。
否则若$u$所有点都不在同一连通块内，连$(a_u-1)$条边。$v$同理。
否则连$1$条边即可。
连边结束后，标记$u$和$v$的所有点在同一连通块内，并连接颜色的并查集。
D. 王国英雄
每次交易额外花费$(b+d)$秒，所以在时间足够的前提下，每次交易一定尽可能多花钱买入商品，以减少交易的次数。
注意到如果$\lfloor\frac m p\rfloor$相同，那么每次交易的结果也是相同的。而每次交易后$m$在不断增加，因此可以通过除法$O(1)$地把$\lfloor\frac m p\rfloor$相同的交易合起来处理。设一共需要处理$k$种交易。
由于买卖一件物品至少需要花费$2$秒，$(1+2+\cdots+k)\times2\le t$得出$k\sim O(\sqrt t)$。所以复杂度$O(\sqrt t)$。
H. 阻止城堡
放一个障碍物最多可以阻止一横一竖两对城堡的攻击，称这种放障碍物的位置为好位置。
把处于同一行，且能相互攻击的一对城堡，看成二分图左边的点；同样地，把处于同一列，且可以相互攻击到的一对城堡，看成二分图右边的点。这样所有的好位置就连接了一个二分图左边的点，和一个二分图右边的点。
为了最小化额外障碍的数量，我们要选尽可能多的好位置。求这张二分图的最大匹配即可。因为可能是完全二分图，所以直接用匈牙利算法，在$O(n^3)$的复杂度下求最大匹配。
添加完二分图对应的好位置之后，剩下的位置最多只能阻止一对城堡互相攻击。这种障碍物直接放在对应城堡的旁边即可。
如何维护方案？可以给每一行以及每一列都维护一个set，保存这一行哪些列，或这一列哪些行有城堡或障碍物。这样就能快速将障碍物插入到set里，以及检查某一行或列是否有两座城堡之间有没有障碍物。
M. 回文多边形
设$f(l,r)$表示从顶点$l$逆时针转到顶点$r$，能构成回文序列的最大凸包面积($a_l=a_r$)。有转移方程$f(l,r)=\max{f(l’,r’)+S_{\triangle ll’r’}+S_{\triangle lr’r}}$。其中$l’$和$r’$位于$l$和$r$之间，且$a_r=a_{r’}$。
直接计算这个转移方程的复杂度是$O(n^4)$的。注意到对于每种权值，最优情况下，$f$和$r’$其中之一肯定市这个权值在$(l,r)$开区间内最靠近左/右端点的顶点，否则额外选择最两边的顶点，面积能变得更大。
因此枚举$f$可以直接确定$r’$，枚举$r’$可以直接确定$f$。复杂度降至$O(n^3)$。
后面的题
太难了，所以不想整。
总结
这次收获还挺大的，有了比赛和团队协作的经验，也不像之前那么慌了。
下一次争取参与到解题上来，别光造数据啥的。