2022 China Collegiate Programming Contest (CCPC) Weihai Site

中期梦游般的一场比赛。

其实在赛前的 vp 已有征兆，一周前 vp 了 CCPCF2021，中间也是两小时一题未出。这一周内 vp 的 CCPC2022 桂林也是如此，尤其在桂林 vp 得非常糟糕的情况下。

热身赛很猛，一发过了那道比较麻烦的线段树题，感觉状态还行，可惜比赛开演。

前期非常顺利，我和队友无间隔地签完了到，在队友写那道计算几何的时候我和另一个队友已经胡完其他三道题，此刻捏在手里的有八道题。进行了二十分钟的讨论，那道构造也基本有思路了，这时候我觉得已经很稳了，没想到这才是梦游的开始。

我很快地开始写 K，本以为我已经想清楚所有，但其实写的时候一直断断续续，很多细节都是我未曾考虑过的，甚至还漏了一个大问题。很快我调出了样例一交，WA 了。然后让队友写 J，我看我的 K。很快，队友的 J 也 WA 了，这时候我感觉大事不妙，给 K 添了一些新的细节特判交上去还是 WA。这时候的指挥系统就出问题了，我应该让队友写 D，我来看 J 的，但当时已经迷糊了。两人分别调自己的花了半小时后，我才做出这个决策。很快我就看出了队友的 J 哪里写错了，但队友没有想清楚怎么改，尝试了十几分钟后继续去写 D，这里又浪费了不少时间。耗着耗着，已经要封榜了，这时候队友终于过 D 了。我赶紧让他去看看 K 发生了什么，然后火速改了他的 J，成功一发通过。这时候队友发现我的 K 发生了一个巨大的问题：根本没考虑区间相交的情况。这时候我仍然觉得能开出其他题，于是就让他在那里改了。这也是错误的决策，因为我督促他写能赚到更多罚时，而开题只是一件不大的概率事件。队友写完了，WA 了，然后一直添加特判交。很快就爆了非常多发。此时我也急了，观察了许久后，在最后只剩十分钟不到的时候，我终于发现一个早期的特判我写错了，改了就立刻过了，可惜罚时已经爆炸，无力挽回了。

从赛后复盘来看，我发现互换调题其实很正确，不应该总想着能多过点题，但这时候因为威海没有 Au 心态炸裂，这为广州的崩盘埋下了伏笔。

[A Dunai]

solution

题面：TI 比赛有只冠军队伍，每个队伍由五个选手组成，每个选手分别打号位中的一个，一个选手永远只打一个位置，不会打其他位置。有名选手组队，问最多能组多少队，满足每个队内至少有一名冠军选手。

做法：签到题。

[B Recruitment]

solution

题面：给定一个长度为的形如的式子，每次修改一个加号为乘号，修改次，共有个式子。给定个式子的结果，要求构造数组和每次修改的加号位置，使得个式子均符合给定的结果。无解输出。

做法：

[C Grass]

solution

题面：给定平面上个点，要求选出其中个不同的点，并选定个中心点向其他个点连出条线段，要求这四条线段任意两条的交点都仅有中心点。

做法：队友写的分类讨论几何题。

[D Sternhalma]

solution

题面：给定六边形棋盘每个格子的分数，询问若干初始的棋子摆放方式，问按照规则移除棋子最多得多少分。

• 移除棋子有两种方式，一种是直接移除一个棋子，不得分；另一种是用一个棋子跳过其相邻棋子，移除被跳过的棋子并且得分增加被移除棋子所在的格子的分数。

做法：状压+拓扑排序。

[E Python Will be Faster than C++]

solution

题面：给出个 Python 版本的运行时间，依据最后两个版本的运行时间画出一次函数之后判断是否会在未来某个版本运行时间超过 C++。

做法：可以直接推出通项。

[F Mooncake Delivery]

solution

题面：给出一张每个顶点带有颜色和点权的无向图。顶点有激活和未激活两种状态，最开始每个顶点都是未激活的，激活一个顶点需要花费的代价为其点权。你有一个棋子，棋子只能放在/移动到被激活的顶点上。你可以随时选择一种颜色，回收这种颜色的所有已激活顶点的激活代价并将其全部设为未激活。当然，不能是你棋子当前所在顶点的颜色，因为棋子只能放在已激活顶点上。现在对于图中的每一对顶点，询问若最开始图中所有点均未被激活，从出发走到所需的最小初始点权是多少。