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与后一条路径的三段的每一段都不交，因此满足条件。

      1. 否则 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上的风评，你看我头像也知道我其实不太在意我自己被批评，攻击。我现在基本上已经慢慢淡出算法竞赛了，也不知道一年后有没有机会继续我的算法竞赛生涯。可能有些人会问，为什么高三还要花这么多时间来出一场比赛。其实我觉得学了两年竞赛，虽然没有什么荣誉，但是我还是有很多收获。出这场比赛的初衷也是希望能够把一些我得到的一些有价值的方法，经验拿出来给大家分享。也希望能为算法竞赛作出一些贡献。所以尽管你们可能不喜欢这场比赛，但是我希望大家不要对题目抱有偏见而视而不见，而是能客观公正的看待它们。

本来还有一些想说的东西，但我也不是太想在题解下面长篇大论。如果您已经阅读到这里了，我非常感谢您的耐心。再次为我们给大家带来的不便表示抱歉。