526互联

Educational Codeforces Round 151 (Rated for Div. 2) 题解

发布时间 2023-08-05 15:02:49作者: cantorsort2919

A. Forbidden Integer

显然，当 \(x\not=1\) 时，直接输出 \(n\) 个 \(1\) 即可

否则，如果 \(n\) 为奇数，那就输出 \(\lfloor\frac{n}{2}\rfloor-1\) 个 \(2\) 和 \(3\)；如果 \(n\) 为偶数，那就输出 \(\frac{n}{2}\) 个 \(2\)（要看一下 \(k\) 的大小）

B. Come Together

因为 Bob 和 Carol 都是走最短路，所以以 \(A\) 为原点建立坐标系后，只有 \(x_B\) 与 \(x_C\) 正负性一样或 \(y_B\) 与 \(y_C\) 正负性一样才能计算距离

所以直接判断即可

C. Strong Password

记密码为 \(P\)，考虑记搜：

令 \(\text{dfs}(i,j)\) 表示当前匹配到的是 \(s_i\)，需要查找的是 \(P_j\)，那么显然可以对此进行记忆化

考虑到子序列的性质：若 \(P_j=c\)，那么我们可以 \(i\leftarrow nxt_{i,c}\)，其中 \(i\) 表示从 \(i+1\) 开始到字符串末尾出现的第一个 \(c\)，那么显然可以通过后缀的方式求解。那么我们接下来对 \(nxt_{i,c}\) 进行分类讨论：

  • \(nxt_{i,c}\) 不存在，那么此时因为保证 \(l_x\ge r_x\)，那么后面一定是存在一种密码的，并且因为选择了 \(c\)，此时 \(P\) 一定不是 \(s\) 的子序列，那么此时就是可行的
  • \(nxt_{i,c}\) 存在，那么此时我们就要考虑下一位是否可以得到不是 \(s\) 子序列的位置元素，于是此时就需要调用 \(\text{dfs}(nxt_{i,c},j+1)\)

注意：\(nxt_{a,b}\) 是不包含 \(a\) 的

D. Rating System

不妨记 \(S_i\) 为前 个\(i\)数的前缀和。那么有一个显然的结论是：最优情况下，\(k\) 的一种取值为 \(S_m\)，其中 \(1\le m\le n\)

我们考虑进行了前 \(i\)次操作且 \(s\ge k\) 成立后，进行第 \(i+1\) 到 \(n\) 次操作对 \(s\) 产生的影响

那么在不考虑 \(k\) 的保底作用下， \(s+S_n-S_i\)即为最终答案，也即这个数会小于等于真实答案

然后我们再考虑真实答案：\(s\) 达到了某个极大值时刚好达到 \(k\)，后面的若干次操作使它在保底作用下不小于 \(k\)，最后可能有若干次操作使其增长，其中 \(s\) 一直不小于 \(k\)

既然最后的若干次操作摆脱了 \(k\) 的限制，我们就枚举这个摆脱限制的起始位置

那么第 \(i\) 次操作后面的这段操作对答案的影响即为 \(S_n-S_i\)

考虑前 \(i\) 次操作使 \(s\) 最大，即为前 \(i\) 次操作中 \(S_i\) 的最大值，这个最大值即为 \(k\)

此时在 \(s\) 达到最大值 \(k\) 后，经历第 \(i\) 次操作后，\(s=k\)

E. Boxes and Balls

考虑 DP

主要考虑 \(0\) 比 \(1\) 多 的情况，如果 \(1\) 比 \(0\) 多就取反再算

设计状态 \(dp_{i,j,l}\) 表示，用 \(l\) 使得前 \(i\) 个位置有 \(j\) 个 \(1\)

可以发现移动前后所有 \(1\) 的相对位置不变，所以转移时可以直接令第 \(j\) 个 \(1\) 移到 \(i\)

设第 \(j\) 个 \(1\) 的位置是 \(p_j\)，那么有转移 \(dp_{i,j,l}=dp_{i-1,j,l}+dp_{i-1,j-1,l-l-|p_j-i|}\)

暴力转移加滚动数组时间复杂度 \(O(n^2k)\)

考虑压缩一下状态，可以发现，要将 \(x\) 个 \(1\) 挪出前 \(i\) 格，至少需要 \(x^2\) 步，反之同理

所以，前 \(i\) 格在操作过后 \(1\) 的个数与原来相差的值最大为 \(O(\sqrt{k})\)

在这个范围里转移即可，时间复杂度 \(O(nk\sqrt{k})\)

最后要注意，我们可以浪费偶数步进行反复横跳，所以答案还要累加上与 \(k\) 同奇偶性的值

F. Swimmers in the Pool

小学学过的相遇问题和追及问题让我们得到，如果当前时间 \(t\) 和两个人的速度 \(v_a,v_b\) 满足 \(t(v_a+v_b)=2kl\) 或 \(t(v_a-v_b)=2kl\)（\(k\) 为正整数），那么此时这个时间 \(t\) 就是一个“相遇时刻”

首先可以用 FFT/NTT 求出所有符合的 \(v_a+v_b\) 和 \(v_a-v_b\)，这样可行的 \(v_a+v_b\) 和 \(v_a-v_b\)我们称作 \(v\)

然后考虑怎么不重不漏地计算出所有 \(t=\frac{2kl}{v}\)

首先如果一个 \(v\) 可行我们可以把它的所有因子也加入集合中，这会方便我们操作

接下来考虑每个 \(t=\frac{2kl}{v}\) 仅在一个地方计算贡献，也就是如果存在 \(v\) 的一个因子也满足上式，那么就不在原先的 \(v\) 处计算这个 \(t\)

所以我们从小到大枚举 \(v\)，然后用容斥减掉每个因子的贡献就行