CCPC2023 吉林站游寄

大概是个临时博客。到机房把这个放到 Github 博客里。

## CCPC 吉林站 游记

队员：日记 推车 HMY

天气很不错。昨天晚上大致计划了一下流程，反正开场和封榜期必然是我的，中间让队友分了吧。

大约 7:55 到的校门。碰到了 HMY 家长并被送到了目的地。/bx

接下来 20 分钟人就陆续来了。8:15 签了 rp++，顺便给推车签了一下。

推车出发晚，8:25 左右才到。简单商量了一下分配（三人一机），推车自己又签了个字，然后就去三楼等着了。

8:40 放进机房。发现甚至给了水和笔，那我为啥要带捏。acm 给东西给的好齐啊，甚至有三份纸质题面。CCF 快学习一下。

9:00 准时开考！读题是按在膜 3 意义下题号的余数分的，推车分了 1，我分了 2，HMY 分了 0。上来看到 B 是裸的二分答案，可惜手生，5min 才过去。最快的好像 1min 就过了，好闪！

读过大部分题之后，一共筛选出了 4 道签到题：B C E K，其中 C 是高精板子，K 是期望板子。K 没开 long long，吃了一发，11+20。这次可以用 python，所以随手写一发 C，16min 过了。E 看起来并不是那么板子了，需要预处理一点东西，然后取个前缀 max。仍然比较签到，是在 46min 的时候一发过的。

现在的时间是 09:46，刚刚过掉四题。接下来我们的计划是按顺序走一遍。HMY 在推 F，推车在推 A。

很快，推车给出了 A 的一个思路：逆序对个数 mod (k-1)。显然这不对，但我们以一发罚时的代价才确认。推车仍然在找新的结论。同时，HMY 也给出了 F 的题意与大致思路，在简单模拟之后我找到了一个 dp 转移式。可是，这个转移式会算重，并且没办法套用容斥。意识到这一点时大致是 11:20。大部分时间都用在了 A F 三题上。

推车放弃了 A，转战 G。同时，我选择从 H 开始依次读到 M（即最后一题）。H 是一道游戏题，数据范围略大，但同样有大量剪枝，可以暴搜。J 类似，看起来是暴力 $O(n^2 m^2)$ 的，但是 $n, m \leq 600$。暂时放一下。I 看起来是可持久化数据结构的题，直觉告诉我不会很难，因为此时已经有队伍切了。L M 相对前三题难得多，并没有考虑。

接下来的时间，我一直在接管电脑并写 H。大约 12:10 时基本完成，但是样例仍然跑不对，会得到一个错解。此时，我们发现 acm 赛场甚至管饭！CCF 学着点 /fn

盯 H 代码的同时，简单吃了一点东西，推车在写 G 的一个 $O(nm)$ 做法，并且由于我记错数据范围认为这是正解，吃了一发 TLE。

封榜前最后 30min，大家都在尝试 A F G 三题，并没有任何进展，结论都是错的。

封榜后，抱着死马当活马医的思想，我将 J 题的暴力写了出来。在实现到一半的时候，我突然意识到可以用 bitset 优化！对时间复杂度的分析显示，优化后可以获得 $2^{-10}$ 的常数，且程序本身结构简单，也拥有小常数。我认为这是正解，并且提交后一发通过！当时感觉大致跟周六 CF 末尾切题差不多，就是很紧张，很激动（锤击桌子）。语文水平不好，难以表达当时的情感，已知的是旁边队估计有些生气。

此时离结束仍然有 30min 以上，H 题我选择牺牲一定时间，来对搜索结果进行二次检查（程序内的函数名也叫 check_again）。（加上这个检查前，样例已经能跑出正确结果，但提交会 WA）我认为是有一些地方写假了，但是比赛已经快要结束，无奈之下选择了提交这个半成品。没想到，这题同样也过了！（掀桌）

最后几分钟，摆了一下，收拾东西跑路。推车去后台把每道题的气球都拿了一个，真的好可爱！

出场前，推车认为我们应该统一口径，说我们只切了四题（封榜前的成绩）。我并不表示赞同，但是推车这么说了，那就听吧。毕竟推车才是真正的队长（？）我只是打的代码比较多而已。突然意识到，我们封榜前的成绩是 4(78+1=98)，在四切里是排名最高的。这是因为我们前四题都是在 1h 内切掉的，虽然吃了一发罚时但仍然以速度取胜。

出场之后看到了其它队。感觉他们都并没有藏私，JJ 队切了 6 题但是罚时比我们长一点，猫猫队切了 5 题，雨羊队和喵喵队大概都是 4 题。再往上是学长们的两个队（最终成绩）：大爷队 9 切榜二，zkq 队 11 切榜一。强大的！

下午会有一个讲题。因为中午吃了饭所以并不是很急，就去听了，顺便继续跟推车贴贴。被洛浔抓了，拍了照片 /lb 感觉好多题都是思维题啊，被诈骗了。还是要多加练习。关于题目的实际做法，可以参看附件：简要题解。

讲题之后就是激烈的滚榜环节了！咩咩似乎被推车骗到了，一直认为我们 4 切。滚榜的时候仔细看了一下，好像并没有很多队伍封榜后 2 切，但是 1 切真的很多。看到 5->6 的队伍感觉很慌。我们到 6 切的时候是 rk12，后来看到了一个 6->7 的，把我们反超了；还有一队是靠罚时反超的。所以我们的最终成绩是 6 切，rk14。JJ 队是 rk15，罚时比我们长 69min。

滚榜结束后，“各回各家，明天上课”。跟推车道了别，所以，下周六见！

## 简要题解

A：有一个关于奇偶性的结论。当 $k$ 为偶数时，每次操作会使得相对逆序对个数改变一个奇数，因此最终可以使得相对逆序对个数为 $0$；当 $k$ 为奇数时，每次操作只能使其改变一个偶数，因此当且仅当相对逆序对个数为偶数时有解，否则一定无解。证略。逆序对可以使用归并排序求，打归并排序耗费了我们较长的时间，需要练习。

B：二分答案即可。注意二分的左边界不能为负数，否则可能导致错误。

C：考虑贪心，先选择大的一定更优，因为我们想让更大的被倍增更多次。需要利用高精度，注意本场允许使用 python。听说猫猫队不会用 py，现场写高精。

D：纳什博弈，结论为 $n \in (3Z, 6Z]$ 时公平。题解给出了三种情况下的最优策略，并证明了 $n \leq 3Z$ 时 A 必胜，$n > 6Z$ 时 B 胜率超过 $\frac{1}{2}$。并不是很理解后一种情况，同样可参考题解。

E：考虑预处理。定义一种颜色的权值为这种颜色两次相邻出现的距离最大值，若只出现一次计作 $n$。之后取一个前缀 max 即得到答案。

F：我们理解错了题意。只包含若干个环相当于说每个节点度数均为偶数。一系列推导后得到答案为 $2^{\frac{(n-1)(n-2)}{2}}$，比较震撼。

G：推车推出了正确的式子，“只”需要二项式反演简化公式，并使用分治 NTT 等阴间技巧计算。

H：注意输出格式中“the answer is **unique**”。这侧面说明了数据中 `.` 的个数不可能很多。另外，有以下情况可以特判并填充：`.00. .11. 0.0 1.1` 以及所有可“trivial”确定的情况（平凡情况）。特别注意一下第三个条件，可以二进制压缩并使用 vis 数组检查。

I：转换题意，则其变成一个二维偏序问题。可以考虑离线树状数组，也可以使用一些更强的数据结构，但不需要。赛时并没有想到这种转换方式，看到可持久化就跑路了。

J：朴素的暴力是 $O(n^2 m^2)$，但若我们定义工作区窗口的长宽分别为 $w,h$，则需要计算的次数至多为 $(n-w+1)(m-h+1)wh$，平衡一下可发现其具有 $\frac{1}{16}$ 的常数。继而，利用 bitset 优化得到另一个 $\frac{1}{64}$ 的常数，总常数为上面提到的 $2^{-10}$。事实上，因为发现不合法可以直接跳出，程序具有比此更小的常数，可以轻松 AC。题解提到了需要手写 bitset，但并不必要。

K：$\frac{(m+1)n}{2}$，向下取整。注意使用 `long long`，避免不必要的罚时。

L 是 SAM 题，M 大概可以 Trie 解决。这两题并不是很会。

正在渲染内容...

CCPC2023 吉林站 游寄