Codeforces Round #745 中文题解与总结

## 题解 在题解前我想先说明一些基本情况。本人目前是高三学生，并没有太多时间来准备题目和题解，给大家带来了诸多不便，对此我深感抱歉，还望大家谅解。此外，Div 2 B， Div1 C，F 并不是我出的，我也没有时间再去做一遍，所以很抱歉无法带来这些题的题解。如果日后CQXYM给了我对应题目的中文题解，我会再进行更新。 ### D2A CQXYM Count Permutations 一个脑筋急转弯。如果一个排列满足条件，那么我们把它翻转过来一定不满足条件，且这两个排列不同。所以答案是 $\frac{(2n)!}{2}$。 ### D1B Mathematics Curriculum 确实这个题的数据范围有点大，理论上 $n \leq 50$ 或者 $n \leq 80$ 会更好。之所以我会出这个数据范围，主要是因为确实这道题的常数很小。我大概估算了一下，状态大概有 $\frac{1}{12}$ 的常数，转移的常数大概也是这么多，基本上常数已经是 $\frac1{n}$ 级别了。不过不管怎么说，我还是为这道题的数据范围的不合理感到道歉。 做法是很简单的，设 $f[l][s][d]$ 表示正在考虑一个长度为 $l$ 的子区间，其中包含 $s$ 个题目中要求的数，并且在所有包含这个子区间的区间中已经有 $d$ 个不同的最大值。转移枚举区间最大值和两个子区间包含的要求的数的个数即可。式子是 $$ f_{l,s,d}=\sum_{a=1}^{l} \binom{l-1}{a-1} \sum_{x=0}^{s}f_{a-1,x,d+1}f_{l-a,s-x-[d=k],d+1} $$ 实际上有很多状态用不到。从另一个角度理解，我们是在数恰有 $k$ 个点的深度为 $m$ 的二叉树的数量，可以想象这对状态的要求非常高。因此即便是 $O(n^5)$ 的复杂度也足以通过。 标程加了一些剪枝，但实际上只要写的是记忆化搜基本上都能过。 ### D1C Train Maintenance ~~关于这道题为什么是 $2 \times 10^5$ 的数据范围和 1s 时限，因为我发现暴力可以在 1s 内跑过 $10^5$ 的数据。~~ 我个人认为 $O(n\sqrt{n})$ 算法跑 $2 \times 10^5$ 是一件很合理的事情。现在看来的话确实如果时限是 2s 或者 3s 会好一些。不管怎么说，我为这道题过紧的时限道歉。 考虑对列车按 $x_i + y_i$ 分类。 如果 $x_i + y_i > \sqrt{m}$，那么这辆列车维护的次数不超过 $\frac{m}{\sqrt{m}}=\sqrt{m}$ 次，因此我们可以直接在时间序列上差分，在每个列车开始维护的时刻加上1，停止维护的时刻减去1。单组询问的时间复杂度是 $O(\sqrt{m})$。 如果 $x_i + y_i \le \sqrt{m}$，我们不妨令第 $i$ 辆列车在时刻 $s_i$ 被修好，当前的时刻是 $t$，那么第 $i$ 辆列车处于维护状态当且仅当 $(t-s_i) \ mod \ (x_i+y_i) \geq x_i$，所以我们可以对每一个 $a \le \sqrt{m}$ 开一个 $a$ 大小的数组记录所有 $x_i + y_i = a$ 的列车处于维护状态的时刻 $t$ 在模 $a$ 的意义是哪些时刻。由于数组大小不超过 $\sqrt{m}$，因此对于单个事件维护 $(t - s_i) \ mod \ (x_i + y_i)$ 的时间复杂度不超过 $O(\sqrt{m})$。 因此总的时间复杂度是 $O(m\sqrt{m})$，可以通过此题。 ### D1D Subsequence 考虑笛卡尔树。以数组下标为优先级，$a$ 为权值，建立一颗满足小根堆性质的笛卡尔树，并且把连接节点 $i$ 和节点 $j$ 的边边权设置为 $\lvert a_i-a_j \rvert$。 化一下式子可得一个子序列的价值为 $\sum_{i = 1}^m \sum_{j = i + 1}^m a_{b_i} + a_{b_j} - 2 \times f(b_i, b_j)$，而 $a_{b_i} + a_{b_j} - 2 \times f(b_i, b_j)$ 就是在笛卡尔树上节点 $b_i$ 与节点 $b_j$ 之间的距离。因此问题被我们转化为：在一棵 $n$ 个节点的树上选择 $m$ 个节点，最大化他们两两之间的距离之和。这样我们就可以使用一个简单的 $O(n^2)$ 的树形背包解决这个问题了。 具体地，设 $f[i][j]$ 表示在 $i$ 子树内选择 $j$ 个节点的最大价值，那么我们有： $$ f[u][i+j]=max(f[u][i+j],f[u][i]+f[son_u][j]+ \ j \times (m-j) \times val_{(u,son[u])}) $$ 而最后的答案就是 $f[1][m]$。 ### D1E Railway Construction 很抱歉由于时间并不充足，本题的数据非常水。题解中也有一些细节可能没有提到。 加边不会改变最短路长度，所以如果一条边一开始不在最短路上，那最后也不会在。因此可以先跑一个 $1$ 为源点的单源最短路，然后只保留最短路图。接下来的讨论中我们忽略点 $1$​。此外，我们称两条路径相交当且仅当这两条路径除了 $1$ 号点外都经过至少一个公共点，这样的公共点我们称为交点。 注意到如果此时一个点只有一个入度，则这个点一定不满足题目要求。所以每个点至少都应有两个入度。接下来我们证明：每个点都恰有两个入度，且两条入边的起点要么都是点 $1$，要么不是同一个点，该方案满足题意。 考虑任意一个点 $u$，假设 $u$ 之前的所有点都满足题目条件，现在我们证明点 $u$ 也满足。不妨设 $u$ 的两条入边起点分别为 $s$ 和 $t$。 1. 如果 $s$ 和 $t$ 中有一个是点 $1$，不妨令 $s$ 为点 $1$，则我们可以选择 $1 \rightarrow u$ 和 $1 \rightarrow t \rightarrow u$，这两条路径显然不交。 2. 如果 $s$ 和 $t$ 都不是点 $1$，首先我们可以任选一条路径 $1 \rightarrow s$，称这条路径为路径0，根据我们的假设，我们可以找出两条不同的路径 $1 \rightarrow t$，并且这两条路径自身不相交，分别称它们为路径1和路径2。 - 如果路径1和路径2中有一条路径与路径0不相交，则选择这两条路径，此时满足条件。 - 否则路径1和路径2都与路径0相交，则路径0上至少有两个交点，我们取出最靠近点 $1$ 的交点 $a$ 和最靠近点 $s$ 的交点 $b$。 1. 如果 $a,b$ 都在路径1或路径2上，不妨假设它们都在路径1上，如下图所示：  则我们可以选择：路径2，点 $1$ 沿路径0到点 $a$ 后沿路径1到点 $b$​ 最后沿路径0到点 $s$，由于路径2与后一条路径的三段的每一段都不交，因此满足条件。 2. 否则 $a,b$ 在不同的路径上，不妨假设 $a$ 在路径1上，$b$ 在路径2上，如下图所示：  则我们可以选择：从点 $1$ 沿路径0到 $a$ 再沿路径1到 $t$，从点 $1$ 沿路径2到 $b$ 再沿路径0到 $s$，这两条路径同理不交。 此时我们已经讨论完所有情况，因此结论得证。 于是我们可以得到一个如下单次 $O(n)$ 的算法：按最短路长度递增的顺序遍历所有点，同时在一个数组 $val$ 中维护前缀最小值和前缀次小值的位置，贪心的为每个入度为 $1$ 的点连边（如果可以选最小值则选最小值，否则一定可以选次小值）。考虑到有 $q$ 次修改，这一算法复杂度为 $O(nq)$​。 这一算法的优化很简单。首先我们倒着执行修改，这样修改只会减小 $w$ 的值而不会增大。考虑在这一过程中直接维护 $val$ 而不是每次重新计算一遍。 根据 $val$ 中的值是否相同，我们可以把整个数组分为很多段，每段中的值都相同。对于一次修改，显然它会影响一段后缀，则我们先找到这段后缀的起始段，然后暴力的修改每一段直到不需要修改（已经修改完整个后缀或者修改值已经大于某一段的次小值）。 对于某一被修改的段而言，根据修改值和这一段的 $val$，我们可以把修改分为三类： 1. 修改值此前就是这一段的最小值。这样的操作可能会进行若干次，但是它不会修改 $val$ 数组，因此我们可以将多次操作合并为一次，用线段树查询并更新答案。因此单次修改中此类操作最多执行一次。 2. 修改值此前是这一段的次小值。考虑到每一段的次小值一定不同，因此单次修改中这类操作最多执行一次。 3. 修改值此前既不是最小值，也不是次小值。我们将这类操作继续细分： - 修改值在修改后是该段次小值。考虑下一个段的 $val$，如果下一个段的 $val$ 的次小值是这个段的最小值，则显然这次修改是最后一次，否则除非这是第一次操作，段数会 $-1$。因此这类操作要么只会执行一次，要么会使段数 $-1$。 - 修改值在修改后是该段最小值。我们可以这样考虑：如果当前区间的最小值一直到数组结束都是最小值，则该次操作会把这个段及以后的段全部合并为同一段，因此每次操作均会使段数 $-1$​。否则当前段的最小值一定会在某一时刻成为次小值，则在这两个段之间的所有段也都会被合并为同一段，因此每次操作还是会使段数 $-1$。 因此总的操作次数不超过 $O(n+q)$。借助可持久化线段树和set，我们可以在 $O(logn)$ 的时间内实现单次操作。总的时间复杂度为 $O(mlogm+(n+q)logn)$。 ## 总结 下面我要说的并不是为这场比赛辩护，只是单纯的陈述一下个人感受。可能会有很多跟题目无关的东西，如果不感兴趣可以直接跳过。 就像我此前说过的一样，我并没有很多时间来准备这些题目，有很多工作都是CQXYM帮我完成的，在此我想表达对他的感谢。 这道D2A给了我很多感触。个人认为，既然是算法竞赛，而不是编程竞赛，那么参赛者理应具备一定的数学推理能力，想要推导出D2A的结论并不困难。就我个人的OI经历来讲，我最大的一个感受就是算法竞赛对数学能力的要求非常高。但凡是OI学的好的，数学大多都不会差。 关于卡常，我也没有想到这场比赛会被认为对常数优化有很高的要求。现在感觉好像很多我觉得很正常的写法都被算成了常数优化。这方面确实是我考虑不周，希望大家谅解。 关于CF上的风评，~~你看我头像也知道~~我其实不太在意我自己被批评，攻击。我现在基本上已经慢慢淡出算法竞赛了，也不知道一年后有没有机会继续我的算法竞赛生涯。可能有些人会问，为什么高三还要花这么多时间来出一场比赛。其实我觉得学了两年竞赛，虽然没有什么荣誉，但是我还是有很多收获。出这场比赛的初衷也是希望能够把一些我得到的一些有价值的方法，经验拿出来给大家分享。也希望能为算法竞赛作出一些贡献。所以尽管你们可能不喜欢这场比赛，但是我希望大家不要对题目抱有偏见而视而不见，而是能客观公正的看待它们。 本来还有一些想说的东西，但我也不是太想在题解下面长篇大论。如果您已经阅读到这里了，我非常感谢您的耐心。再次为我们给大家带来的不便表示抱歉。