Codeforces-Edu-Round-Notes

退役老狗的 codeforces 摸鱼记。准备做做 Educational Round，一场做个五六题，试图维护一下捉襟见肘的代码能力，同时也拯救一下跌破下限的智商。

Educational Codeforces Round 144 (Rated for Div. 2)

A

注意到当 \( i \) 大于 \(30\) 时，产生的效果与 \(i\) 从 \(1\) 开始相同，所以原串是有循环节的。

my-impl

B

结论：最多使用两个 * 。

做法：

• 0 个 * : \(a\) 和 \(b\) 相同。
• 1 个 * : 答案是 x* 或是 *x 的形式，只需要考虑 \(a\) 和 \(b\) 的首字母或是尾字母是否相同。
• 2 个 * : 答案是 *xy* 的形式，如果答案是 x*y* 或是 *x*y 的形式，则可以等价替换为 x* 或 *y ，同理，使用 3 个或以上 * 一定不优。只需要考虑 \(a\) 和 \(b\) 中是否有两个连续字母相同。

my-impl

C

眼瞎了，没看到取模。

首先做这个最大\(size\) ，很好做，直接将 \(l\) 不断乘 \(2\) 直到超过 \(r\) 就可以得到最大的 \(size\) ，记为 \(n\) 。

然后考虑方案数，首先枚举一个集合中最小的数 \(x\) ，那么需要满足 \(l \leq x, x\prod_{i = 1}^{n}d_i \leq r, \forall d_i \geq 2\)，所有 \(d_i\) 的取法就是方案数。

可以设计递推计算这个方案数，设 \(f(x, n)\) 表示集合中最小的数为 \(1\)、当前集合中最大的数是 \(x\) 、集合大小为 \(n\) 的方案数，转移比较简单，那么此题答案就是：

\[ \sum{x = l}^{r}\sum{i = 1}^{\lfloor \frac{r}{i} \rfloor} f(i, n) = \sum_{x = l}^{r} g(\lfloor \frac{r}{x} \rfloor, n)\]

上式中，\(g(\ , n)\) 是 \(f(\ , n)\) 的前缀和。

整除分块，时间似乎刚刚好。

Tutorial 里面似乎有数学方法可以直接把这个方案数算出来。

my-impl

D

贪心。

可以将题目中的操作看做将所有 \(a_i - x\) ，然后选择 \(k\) 个位置 \(+ 2x\) 。

套路地将区间和拆成前缀和相减的形式，考虑枚举右端点对于答案的可能贡献。接下来按照 \(x\) 的正负讨论，如果 \(x > 0\) ，那么希望尽可能将 \(k\) 个位置放在区间内，否则尽可能放在区间外。

需要把一点点细节全部都写对，老年人为了复习线段树没有选择更快的做法。

my-impl

E

写半天没写出来，最后抄的题解，qaq。

还是看 Tutorial 吧。🥹

my-impl

可能需要注意的是，当 multiset 为空的时候，*s.begin() 似乎是未定义行为，会返回一个奇妙的东西？

Educational Codeforces Round 143 (Rated for Div. 2)

A

把两个序列拼在一起，中间切一刀，两边各自满足条件即可，暴力可过。

my-impl

B

考虑选择所有包含 \(k\) 的区间 \(l, r\) 。

所有不包含 \(k\) 的区间一定不优，而加入一个包含 \(k\) 的区间不会使 ideal 的点集变大，所以全部加入之后判断 \(k\) 是否满足 ideal 即可。暴力可过。

my-impl

C

对于每一个 \(a_i\) 在 \(b[i: n]\) 的区间上二分找到最后一个吃完的位置 \(p\) ，然后通过差分统计答案，\([i: p - 1]\) 的区间上每一个答案增加 \(b_j\) ，\(ans_p\) 增加剩下的价值。

时间复杂度 \(O(n\log n)\)。

my-impl

D

因为所有 \(w_i \geq 0\) ，所以价值的代数和最大等价于扔掉最少的边。

一个三角形的三个顶点只有两种涂色方法：

• 三个点同色，这种情况下扔掉三条边，不优。
• 两个点同色和最后一个点异色，这种情况下扔掉一条同色边，全部选择这种。

因此，答案中有一个因子为 \(\binom{\frac{n}{3}}{\frac{n}{6}}\) ，上面是三角形数量，选出一半的三角形赋给两蓝一红的颜色，剩下的赋给两红一蓝的颜色。

然后对于每个三角形的边权 \(a \leq b \leq c\) 分类讨论即可，考虑到所有的三角形涂色方案独立，答案为所有因子的乘积。

my-impl

E

一个很贴近真实算法的题，比较喜欢。

考虑对于每一个 \(h_i\) 使用操作 2 能够解决全部所需的最小操作 1 的数量，很显然 \(i\) 这个位置是不应用操作 1 的，所以可以只考虑 \(i\) 的每一个前缀和后缀，方法类似。

维护一个单增的单调队列，当遇到 \(h_i\) 时：

• 将所有大于它的队尾元素出队，出队的过程中统计需要的操作 1 的数量，注意到假设队列中原有 \([5, 6, 8]\) 遇到 \(4\) ，其实会将原来的序列变成 \([1, 2, 3, 4]\) 的等差数列，因此将四个数压缩成一个节点放入单调队列中。
• 另一个限制是当遇到比较小的 \(h_i\) 比如 \(2\) 时，实际上需要将 \(i - 1\) 以前的数统统使用操作 1 点死，这也是队头移动的条件。

细节有一、、多

时间复杂度 \(O(n)\) 。

my-impl

F

二分答案，考虑如何检验，令 1 为根，每一个黑点都尽可能向下（更深处）移动，如果无法往下移动，则向上移动到父亲尝试检验。移动到根或两个及以上黑点交汇则失败。

时间复杂度 \(O(n\log n)\) 。

my-impl

Educational Codeforces Round 146 (Rated for Div. 2)

A

按照 \(n\) 和 \(k\) 的奇偶性分类讨论：

• \(n\) 是偶数，可以直接令 \(y = 0\) ，\(x\) 一定有解。
• \(n\) 是奇数，若 \(k\) 是偶数，一定无解；否则因为 \(k \leq n\) ，只要让 \(n\) 减去若干个 \(2\) 一定可以到达 \(k\) 。

my-impl

B

好题，不要把算法题当成数学题来做。

先考虑只有一维的做法，一个直观的想法是先将 \(m\) 增大到 \(\sqrt{a}\) 左右，然后再走约 \(\sqrt{a}\) 步，这样最少。

但是在两维的情况下，这个想法并不一定成立，参考 \(a = 8, b = 4\) 这组样例解释，一个较大的 \(m\) 可能会对于上面这个最小的性质带来一些破坏。

考虑当 \(m\) 不超过 \(M\) 时所需的最少步数，答案为 \(M + \lceil \frac{a}{M} \rceil + \lceil \frac{b}{M} \rceil \) ，对于那些多出来的部分，只需要在 \(m\) 还没增大到 \(M\) 的时候先走即可。

结合最开始的观察，发现当 \(M\) 很大的时候是无意义的，而 \(M\) 应该 \(< \max(\sqrt{a}, \sqrt{b})\) 。

my-impl

C

先考虑只有一个 \(a\) 的情况，很显然是把 \(r\) 逆序排序，直接按顺序构造最小，证明可以参考排序不等式。

那么如果有两个数组可以构造，只需要把 \([s_1, 2s_1, \ldots, ns_1, s_2, 2s_2, \ldots, ns_2]\) 排序，然后取前 \(n\) 项即可。

my-impl

D

发现答案具有单调性，即如果改变 \(x\) 个 \(d_i\) 能做到，那么改变更多个 \(d_i\) 也一定能做到。

于是可以二分，这边考虑二分的是最多的不改变 \(d_i\) 的数量。原因是：设 \(p’\) 表示 \(p\) 从小到大排序的结果，那么不改变的这些点一定是 \(p’\) 中的一段连续区间。

现在问题变成了有了一段连续区间 \(p’[l: r]\) ，如何检验外面的这些点改变 \(d_i\) 之后能不能满足极差 \(\geq k\) 的条件，可以把区间外的这些点分成两类：

• 通过改变 \(d_i\) 能够放进 \([p’(l), p’(r)]\) 这个区间里面的点，这一部分点一定不会破坏目标性质
• 通过改变 \(d_i\) 不能放进这个区间里面的点，这一部分点可能会放在区间的左边或者右边，针对这一部分点的检验变成了：每一个点有放在左边或是右边两种选项，是否存在一种选法使得极差 \(\geq k\) 这个条件成立。

可以枚举这些点的左边的值，同时记录他们对应的右边的值，按照从小到大的顺序枚举这些点放在左边的值，每当端点右移时，相当于要把这个点放在右边，这时只需要维护延伸出的右端点最大值即可。

我认为，最后一步这个算法还是有一定的价值的，并不是完全套路。

时间复杂度可能是 \(O(n^2\log^2 n)\) ，但是不怎么满。

my-impl

E

有点没意思，搞了半天就是动态 dp 。

结论是：一定可以把这个链条划分成若干个 \(2\) 个相邻点和 \(3\) 个相邻点的集合。

证明可以分为两步：

1. 如果两个置换环之间存在交叉，一定不优，可以通过把交叉互换的方式减少开销。
2. 如果存在一个 \(> 3\) 的置换环，那么可以通过拆分成若干个大小为 \(2\) 和 \(3\) 的置换环的组合更优。

分析到了这里，dp 呼之欲出，设 \(f(i, 0 / 1)\) 表示到 \(i\) 这个点，选 / 不选 \(i\) 这个点的最小价值和，初值为

\[f(1, 0) = 0, f(1, 1) = \infty \]

有转移，

\[f(i, 1) = \min(f(i - 1, 0), f(i - 1, 1)) + a_{i - 1}\]

\[f(i, 0) = f(i - 1, 1)\]

套上动态 dp 那一套理论，先重新定义矩阵乘法：

\[C = A \cdot B, c(i, j) = \min(\sum_{k = 1}^{n}a(i, k) + b(k, j))\]

然后把转移写成矩阵乘法的形式，寄了 hexo 为什么连矩阵乘法都打不出来，看来还需要再调教一下这个博客。qaq

最后用线段树维护矩阵即可。

my-impl

接下来准备结合 THU 的机考题，对于目前的训练情况做一些调整。