2024 CCPC网络赛复盘

补题链接：https://codeforces.com/gym/105336

名次：103

赛时：B C D E G I J K L （9题）

赛后：F

首先是OMS与PTA的保留节目：爆炸

去年是新版OMS闪退，今年是直接塞爆进不去。教室一片骚动，不过既然比赛已经开始了，那就可以动键盘，先敲几个板子再说。我上来先敲最黑盒的网络流，小武过来敲了个fhq，我又开始敲sam，敲完sam敲线段树，虽然小武觉得线段树没啥用但是我还是喜欢敲，因为线段树敲的快敲的爽哈哈。

还没等我敲完，大伙就开始躁动好像有人能看到题了（这时候已经过去将近半个小时了），我们点开了G，一看题居然和暑假集训的那个题那么相似，就是一条边的边权可以分给左右两边，想让1号点满足什么什么条件。当时div1+div2一起vp时做过一道，杭电多校也见过一道（最小值改成了最大值，就不会了）。但是思考了一会儿，没想明白咋做，这题也是唯一一个点开的题，剩下俩电脑都卡着进不去。贪心的想法应该是行不通了，因为这题每个人还有个上限，我画了画图，感觉像是反悔贪心的那一类问题，就是一条边权值重新分配的话，相邻边的权值也跟着分配，因为是图，感觉和网络流有些关系。

还没细想，题目列表刷新出来了，一看 L 题签到，赶紧让队友写。（赛后群里有人说 “刷新出来的时候发现已经过了一千多个队，感觉天都要塌了”，我寻思你的天怎么这么容易塌呢。。。这才几分钟罚时啊）

等过了一会儿OMS服务器终于稳定下来了，L 题也终于交上了，看到 B 题有人做。B 题问 a 数组有多少排列的所有子区间极差和最小，因为过的人多 zxn 直接二话不说猜结论答案不是升序就是降序，我就开始写，写的时候他也顺便会证了。这题只需要考虑相同数字，我 WA 了一发因为忘记了如果只有一种数字正序倒序都一样。

K 题博弈论结论很简单，队友写了一分钟过了。之后是 D 和 E 两个字符串题，虽然是easy-mid难度但是却卡了我们一会儿时间。

我发现 E 的期望值没啥思路，就去看 D，D 题字符串的构造方式和 lowbit 数列很像，数据范围看样子是个区间dp，我发现只要先把正中间的字符匹配掉（或扔掉），两边的字符串是一样的，可以递归求解子区间的匹配方案数，这题也不难写，有几个犯唐的地方但是十几分钟就过了。

小武说他会 E 了就开始写，我和 zxn 去看 J。

J 题是个经典的 a b 数组交换，思考了一会儿，我的思路局限在了每一位 1 的数量分配给 a b 数组的奇偶性。zxn 提供了一个绝妙的思路，我们就先让数组固定成这样算出异或和 X 和 Y，然后如果要交换一个位置，相当于 X 和 Y 同时异或上 \(a_i\oplus b_i=c_i\)，所以 \(c_i\) 才是有用的数列，用线性基可以减小工作量。这下就变得很简单，本来我想的是如果某一位不能让 X Y 相等，那就爆搜后面的选择，但 zxn 又想到了另一个关键点就是如果这一位让 \(X=1，Y=0\)，那么之后我们就贪心让 X 尽可能小就行，因为 Y 已经不能比 X 大了。

这题会做了，在等小武过题，结果交了一发 WA 掉了，我让小武先下来我去写 J。他们又讨论了好久，说感觉也妹啥问题啊。

很快 J 过了，E 还是没找到错误。我感觉再开新题状态就不对了，就回来跟他们一起讨论。他们给我输出了好长的思路，结果，我没太听懂。。。不过隐隐约约感觉是对的，就是求期望合并多少个点嘛，所以我一直去怀疑代码哪里写错了。我把答案取模又加固了一遍防止负数，背着他俩偷偷交一下但是果然又错了。QAQ

然后这题怎么解决的呢，在 zxn 给听的一脸懵逼的我讲容斥思路的时候，小武写了个暴力，虽然只能跑很小很小的数据但是够了，已经跑出来错误了。对比这个小数据，zxn 好像发现了小武思路的漏洞，我没听明白，但就是假了，哈哈。

他俩尝试去修复这个假做法，我看榜发现已经过这么多人了会不会想复杂了。于是开始另辟蹊径，我发现求一个点不被覆盖的概率是相当容易的，而且所有点都是独立的，诶我就有点疑问了，所有点数减去每个点没被覆盖的期望值不就是最终答案吗？我把式子写了出来，队友好奇这个补丁的复杂度。我说这不是补丁，这个式子就是最终答案，小武一脸惊奇。

事实证明我们确实想复杂了。。。我的式子就是正解式子，一下就写完了。不过这也没办法，谁也没法保证各自开题和一起看一道题哪个出题更快。

过了之后镇定下来，一起看 I。感觉可以记录每个人最早拿到行李的匹配方案数，如果钦定同样最小时间视作最靠左的人先拿到行李，那么他左边的人必须晚于他，右边的人不能早于他，不重不漏。由于每个人可以不匹配行李，于是我们需要设计个dp，用一维来记录前面有多少人不匹配。发现dp转移是 \(n^3\) 的，总体是 \(n^4\)。但是这个dp对于每个人来讲具有极大的相似性，比如当最早时间 t 相同时，我们相当于把所有人向前移动 t 个单位再进行匹配，所以这可能是个关于时间 t 的预处理，而时间 t 取值范围是 O(n) 的。

想了一会儿发现刚才的dp需要考虑哪个人是最早拿到的，预处理没法做到每个时间 t 用 n^2 跑完所有情况，既然这个设计是关于时间而不是关于人，是不是要像 zxn 一开始提出的那样应该把出发点放在枚举时间 t 上，也就是枚举答案求方案。

在这个新思路下很快我口胡出了正解，枚举时间 t ，让所有人向左平移 t 个单位，所有人都只能匹配自己位置或者左边的行李，且必须至少一个人匹配自己的位置。我寻思这不是经典的小小容斥，让所有情况减去所有人都不匹配自己位置的情况就是答案。而所有人都不匹配自己位置，其实就是平移 t+1 个位置的所有情况。设总方案是 \(dp[t]\)，那么 \(ans[t] = dp[t]-dp[t+1]\)，就可以了。

在我调 I 题的 dp 的时候，俩队友已经把 G 题网络流做法给搞出来了，还把建图都给我画出来了，我惊呼这题还真是网络流啊。因为有开赛时敲的网络流板子，I 题过了之后十分钟就把 G 写完交了，WA 了一发是因为有个小细节处理错了。

这题的建图还是挺有趣的，比较有思考价值。

首先我们肯定是贪心地让主角花的钱最多，所有边权给他，算出这个值 da（和他自己钱数取个min），然后其他人因为不能大于等于他的话费，我们给每个人一个消费上限 da-1，和他自己钱数取 min，再刨去车费 \(v_i\) 得到 \(b_i\)，每个人的花费限制用一条流量为 \(b_i\) 的边来表示，连向汇点。这题中我们可以控制每个菜向两边的权值分配，其实就是流量的分配，用源点向这个菜连一条流量为菜钱的边，然后分给吃这道菜的两个人。如果在满足所有人消费不超过主角的条件下（连向汇点的流量满足了这个限制），能够把所有的菜钱得以分配，输出YES，表示他们吃得起这些菜。吃不起可能不是因为钱不够，而是因为消费不能超过主角。赛后想了想，这种有上限的网络流模型还是比较好建出来的，只要能想到用网络流而不是乱搞。

上完厕所来看 C，看榜感觉只有 C 可做了，这题的风格就非常得像CF比赛，我很喜欢。

队友一直讨论连通块的分法，他们画的图里连通块老是带一个黑点作为根，我说这样不太好吧，毕竟黑点作为根是会把白点分成好多个独立块的，那么子树内的黑点处理就比较棘手。我的建议是连通块要么纯白，要么就把所有黑点带上，但是显然我的思路也是走不通的。

怎么整呢？队友干脆还是讨论一个黑点作为根的情况，虽然我很不喜欢这样，这样不能作为一个独立的子问题，但是毕竟这样是最能找到规律的。我在这个连通块下面画了几个黑点，突然灵感就上来了，虽然最上面的黑白连通块不能作为子问题，但是最底层的连通块是可以作为子问题的。

一个黑点，如果所有的子孙都是白点，那么步数是确定的，偶数直接除以2，奇数需要多一次，而多的这一次可以贡献给黑点的父亲，也就是说如果子树内是奇数个点，我让根的父亲也涂黑，然后从下往上来讨论，方案肯定是最优的。写着写着发现一个问题就是会不会涂黑父亲结点的时候把白色连通块弄得四分五裂，如果我们用拓扑的顺序来考虑每个黑点，那么确实有这个问题，但是可以换个枚举顺序，直接把所有黑点按深度排序，完美解决。

写的时候用了树状数组维护 dfn 数列，这题应该是有 O(n) 的精细处理但是我选择无脑数据结构。

其实我们队伍是学校里最早 9 题的，当时 F 过的人好像才 20 多。因为开局爆炸延长了一小时，我们现在有一个半小时搞 F。如果咬咬牙估计是能写出来的，可是我们已经提不起劲了。

包子鸡蛋III。在听队友讲完这个逆天三合一包装题面之后，我们开始考虑最里面那层的 dp 怎么做。小武设计了一个 nm^2 的 dp，记录了 eg 字符串长度，g 的数量以及 egg 的数量，我吐槽了好久 egg 数量这一维是不是有点蠢，可是发现确实拆不掉，不记录当前数量是根本没法统计字符串egg个数的，毕竟还是子序列的egg个数。队友唯一能想到的优化就是 g 数量这一维不需要枚举到 m，只需要枚举到根号 m，但是长度为 n 的那一维不优化根本没法做。

在犹犹豫豫顿顿波波了好久之后，我才提出了一个很重要的优化，我发现虽然 eg 序列长度可能很大，但是第一个 e 和倒数第二个 g 之间的长度不能超过 m，因为在这个区间，无论是填 e 还是 g，都会至少匹配出一个 egg，这下 dp 部分复杂度已经降到 \(m^2\sqrt m\) 了，但这时距离结束已经不到半个小时。

我说后面的部分你们推一推，我先写这个 dp。队友一推，发现第二层的部分也不是那么容易，而是一个统计总位数方案数的卷积式子。我们在纯 eg 的字符串长度和概率固定之后，它把区间分成了四个部分：第一个 e 前，能填 a 和 g（设a表示所有其他字符）；第一个 e 和 倒数第二个 g 之间，只能再填 a，而且这部分还是个带排列组合意义的统计；最后两个 g 之间，能填 a 和 e；最后一个 g 后面，也是能填 a 和 e。

那个带排列组合意义的部分需要列一个指数型生成函数，用 a 的概率列一个多项式，用 dp 部分得到的值再列一个多项式，剩下的三部分再和指数型生成函数求出来的多项式再进行卷积，就可以求出长度为 i 的字符串是好串的概率。最后的最后这道题的最后一层，把每个长度对总答案的贡献进行累加，\(ans = \sum F[i]*(n-i+1)\)。

当时推到这里就绷不住了，我本身多项式写的就不是很快，开赛的时候还没打多项式的板子，现在还剩下不到半个小时，dp部分还没写完，会赢吗，赢个毛线。

我说咱们是不是多项式的部分想复杂了，正解肯定没这么麻烦吧，会不会一个简单的组合数统计就完了。看队友已经摆烂了，我干脆也摆烂了，只能渐渐看着过题人数增加，渐渐从20多到了40多，最后60多人过。

结果赛后一讨论发现就是这个玩意儿！就是套三层的大码力题，哈哈。

赛后补了补，细节竟然没想象的多，感觉主要就是套多项式的板子，剩下的很简单，然后 dp 部分稍微要写一会儿。

除了这道可以拆成三道题的 F，我们注意到 A 题最后一小时过的人数飙升，虽然没超过 F，zxn 最后读了一遍题，发现这就是个分类讨论。赛后小武看了看榜简直笑死，竟然有只过四题的队伍过了这题，真的是一点科技不会只会讨论啊。

觉得榜有点歪，有点不爽，感觉半小时就能手玩出来，不过吃饭的时候才发现这不是道小分类讨论，而是个大分类讨论。榜歪也是情有可原的，甚至赛后我还不想去补这题，感觉补了对以后也没什么帮助。

总的来说，这次CCPC网络赛的质量还是挺高的，各种题型都有，难度梯度也合理，就是作为金牌题的大分类讨论 A 和仨题合一起的多项式 F 有点难写了。。。可能还是我们队码力不足吧。