一些 Codeforces 简单题的一句话题解 - 壹
今天的 Codeforces 有在下饭吗?
是原先在 洛谷的文章 的精神续作, 直接原因是受 某个学长的视频 的启发.
新的在前头, 老的在后面. 当然只有我写过的 = =
不配打 Div. 1, 有些 Div. 1 的题只是因为出现在了 Div. 2 里, 所以有写.
Edu Round #132 (Div. 2)
F
首先对题意进行转换. 给定一棵完美 01 Trie, 根结点是源点, 所有叶子是汇点, 需要对所有边赋一个流量限制 $c_i$, 使得最大流恰好为 $f$.
设 $g_d(x)$ 表示 Trie 上深度为 $d$ 的结点与父亲连边流量为 $x$ 时的方案数, 则有
是卷积的形式, NTT 加速计算就好了. 时间复杂度 $O(nk\log k)$.
Edu Round #131 (Div. 2)
A
答案只可能是 0, 1 或者 2, 就是样例里的情况.
B
$d$ 取 2 的时候答案最优, 按照 $d=2$ 贪心构造排列就好了.
C
先假定所有工人都只做对应的任务, 然后调整. 把一项任务从对应的工人转移给另一个人, 就是一人工作时间减 1, 一人工作时间加 2. 反复调整让工作时间最大值最小就好了.
D
处理出每个位置可能取值的范围 $\left[\lfloor \frac{i}{b_i + 1} \rfloor + 1, \lfloor \frac{i}{b_i} \rfloor \right]$, 问题转化为给每个区间依次填数, 要求填的数包含在对应区间中且组成一个排列. 从小到大枚举要填的数, 在包含这个数的所有区间中, 显然要先满足右端点小的区间, 取右端点最小的区间填进去就好了.
注意直接按左右端点为一二关键字排序是错的, WA 了好多发都没反应过来 (
E
首先 home 键至多被按一次, 枚举 $s$ 中按 home 键的位置 $i$, 已经利用 $s_{i+1\ldots n}$ 得到了 $t_{j+1\ldots m}$, 这一段只使用 left 和 backspace, 操作数是 $m - j$. 然后按 home 键, 不断按 right, 遇到不匹配的字符就再按一次 backspace, 直到 $s_{1\ldots i}$ 和 $t_{1\ldots j}$ 的最长公共后缀. 记这个后缀长为 $l$, 那么这一部分的操作数是 $(i - j) + (i - l)$.
最长公共后缀反转 $s$ 和 $t$ 利用 z 函数求出, 时间复杂度 $O(n^2)$.
F
对每个加入的点 $x$ 维护一个 $f(x)$ 表示在区间 $[x + 1, x + d]$ 内点的个数, 那么最后的答案为 $\sum \binom{f(x)}{2}$.
考虑用线段树维护这个东西. 加入一个点 $x$ 之后需要算 $f(x)$, 维护区间内点的个数就好了. 此外 $x$ 还影响了 $[x-d, x-1]$ 内的 $f$, 打一个加法标记就好了, 具体维护过程可以通过比较 $\sum \binom{f(x)}{2}$ 和 $\sum \binom{f(x) + t}{2}$ 得到, 需要额外维护出 $\sum f(x)$. 删除一个点类似, 所有操作取反就好了.
时间复杂度 $O(q \log a)$.
Round #796 (Div. 2)
A
取 $x$ 二进制下最小的那一位. 如果 xor 起来是 0, 就再添上前面一位就好了.
B
如果有奇数, 直接把所有偶数全部合并到奇数上就好了.
如果没有奇数, 把所有偶数合并, 然后再对得到的和执行 Reduction 操作. 容易发现这样是最优的.
C
十分神秘的一道题.
在所有的 $t_i$ 和 $s$ 中, 初始的字符出现次数为奇数次, 其余字符出现次数为偶数次, 直接判断就好了.
Round #796 (Div. 1)
A
先考虑 $k \ge n$ 的情况. 为了尽可能利用每分钟生长的蘑菇和原有的蘑菇, 每个位置都要去到, 且最后的 n 分钟内一定正好采到 n 个位置上的蘑菇. 那么在位置 1 逗留 $k - n$ 分钟, 然后一直采到位置 n 就好了.
对于 $k < n$ 的情况, 每分钟生长的蘑菇对答案的总贡献是形如 0, 1, …, k - 1 的等差数列, 和开始位置无关. 那么选择一个长度为 k, 其中 $a_i$ 和最大的区间就好了.
B
首先通过 $m$ 次只标记一条边的询问得到每条边的权值 $l_i$, 按边权从小到大的顺序加入边 $i$, 询问加入 $i$ 之后的结果. 如果加入前后相差不等于 $l_i$, 那么加入 $i$ 之后图的连通性不变, $i$ 就不出现在最后的答案中. 这样的询问有 $m-1$ 次, 总共询问 $2m-1$ 次.
C
记 $s_i = \sum_{j = 1}^i a_j - b_j$, 那么对于区间 $[l, r]$, 能操作的条件为 $s_{l-1} = s_r$, 操作后的效果是区间内的所有数都替换为 $s_r$, 同时也是 $s_{l-1}$. 最后的目的是把所有 $s_i$ 都替换成 0.
直接从 $s_i= 0$ 的位置开始 BFS, 在对应区间上替换 $s_i \neq 0$ 的位置. 可能会重复使用同一个位置, 用 set 记录未覆盖的位置就好了. 时间复杂度 $O(n \log n)$.
Round #785 (Div. 2)
A
Alice 在 n 为偶数的时候肯定全取走, 在 n 为奇数的时候给 Bob 剩一个最小的. 之后 Bob 就没得选了. 之后计算得分作比较就好了.
可能要特判 n 为 1 的情况.
B
检查两个相同的字符之间时候是否都出现了 t 中的其余字符就好了.
C
打表发现 n 的范围之内最多有 498 个满足条件的数可以用, 然后就是普通的无穷背包计算方案数的问题了.
D
记 B 中的最小值为 b1, 最大值为 b2, C 中的最小值为 c1, 最大值为 c2. 核心的思路是在 C 的基础上增加一部分元素来得到 A.
首先要保证 C 中元素全部出现在 B 中, 否则答案一定为 0. 具体而言, 就是保证 c1, c2 都在 B 的范围之内, B 和 C 的公差也能对上. 然后考虑无解的情况, 无解就是 C 往两边无限延伸, 新增的元素也没有和 B 中相同的. 也就是 $c_1 - r < b_1$ 或是 $c_2 + r > b_2$.
其余情况下, A 的公差一定是 $r$ 的约数, 枚举 $r$ 的约数 $d$, 从 $c_2$ 往后下一个与 B 有重叠的位置就在 $c_2 + \mathrm{lcm}(d, q)$, 显然有 $\mathrm{lcm}(d, q) \leq r$, 但其实是不希望有小于的情况的, 因为此时 $c_1$ 和 $c_2$ 之间 A 和 B 又有除 C 以外的重合. 其余情况对答案就有 ${(\frac{r}{d})}^2$ 的贡献.
时间复杂度 $O(\sqrt{r} \log r)$. 细节和可能写挂的地方可能有点多… 还是 Think twice, code once 说得有道理.
Round #781 (Div. 2)
A
构造. 输出 1, n - 3, 1, 1.
system testing 的时候 A FST 一大片, 还好是假的
B
模拟. 首先最后数组里的所有数都会是原先出现次数最多的那个数, 一直重复替换其他数值, 然后复制替换后的数组这个过程就好了.
C
首先 spreading 只会发生在某个节点的孩子节点中, 那么 infection 就可以依次选择所有节点的孩子集合, 如果选择完之后还存在没有被感染的节点, 选择未感染节点数最多的孩子集合, 感染一个就好了.
D
看到这个数据范围先猜一个二进制.
考虑计算 $x \bmod 2^k$ 的值, 这个可以递推得到. 假定已经知道了 $x \bmod 2^{k - 1} = r$, 现在来计算 $x \bmod 2^k$. 考虑 $r$ 的意义, $r$ 就是 $x$ 二进制下前 $k$ 位组成的数, 如果 $x$ 的第 $k + 1$ 位是 1, 那么 $\gcd(x + 2^{k-1} - r, 2^k) = 2^k$, 否则就是 0. 这个 gcd 可以体现为 $\gcd(x + 2^{k-1} - r, x + 2^{k-1} - r + 2^k)$, 然后询问就好了.
最终的答案就是 $x \bmod 2^{30}$, 总共询问次数就是 30 次.
E
对于小于 $2^k$ 的数, 只需要维护 $a_i$ 前 $k + 1$ 小的位置. 可以利用归纳法证明, 使 $a_i | a_j$ 最小的 $i$ 和 $j$ 一定出现在这 $k + 1$ 个位置中. 用线段树大力维护就好了.
赛时维护了前 2 小的位置, 写着写着发现假了. 官方题解里看到有莫队写法了, 莫队已经走向国际化了 (
Edu Round #125 (Div. 2)
A
$O(n^4)$ 暴力 DP.
进一步思考, 答案不会超过 2. 因为可以先从 $(0, 0)$ 到 $(x, 0)$, 然后再到 $(x, y)$. 此外再额外讨论答案是 0 和是 1 情况就好了.
B
贪心. 能 +x 就加, 不行就 -y.
C
模拟. 括号匹配和回文串判定都是经典问题, 这就是个缝合题 (
然后就写了个栈又写了个哈希… 其实没有必要, 首先依次枚举每一个字符, 讨论一下遇到的是 ( 还是 ) 然后计算答案就好了.
D
调和级数复杂度 (枚举倍数) 与二分. 注意读题, 关键在于一次 battle 只能选择一种 unit. 维护一个花费 $c$ 能买到的 unit 的最大 $h_i d_i$, 记作 $g(c)$, 然后用 $g(c)$ 计算预算小于等于 $c$ 时的 $x h_i d_i$ 最大值 $f(c)$, 其中 $x$ 表示 unit 的数量. 时间复杂度可以做到 $O(C \log C + C)$.
对于每个询问, 在 $f(c)$ 上二分就好了. 总体时间复杂度 $O(n + (C + m)\log C)$.
Edu Round #124 (Div. 2)
A
第一轮之后就只剩奇数了, 所以答案是 $2 ^ n - 1$.
B
假定 $a_i$ 升序, 对于 $i > j$, 反例就是 $2 |a_i - a_j| \geq a_i + a_j$ 即 $a_i \geq 3 a_j$. 所以依次输出 3 的幂就好了.
C
两行中的每个端点向另一行连边就好了, 但是需要分类讨论. 直接讨论具体的连边情况是比较复杂的, 但最后的答案只关心数值, 列出所以情况下最少花费并取最小值就好了.
D
答案只会是给定点上下左右的点, 当然不包括给定的点. 然后建图跑最短路就好了.
虽然, 事实上只需要从外围向里 BFS 就结束了…
Round #761 (Div. 2)
A
首先直接对 $S$ 排序, 此时只有 $S$ 中同时存在 a, b, c 且 $T$ 为 "abc" 时 $T$ 对排序后的 $S$ 有影响, 这个时候把所有的 c 放在所有的 b 前面就好了.
B
令 $c = 1$, 然后直接暴力找 $a$, $b$ 就好了.
C
对于一个数 $a_i$, 经过一次操作后可以得到从 $1$ 到 $\lfloor \frac{a_i - 1}{2} \rfloor$ 的任一整数. 然后从小到大构造排列, 如果原先就存在需要的数, 就用原来的, 否则选择一个最小的满足条件的 $a_i$ 进行一次操作.
D
记 $f(i)$ 表示 ? i i+1 i+2 得到的结果.
首先每三个位置分作一组询问, 得到 $f(i), f(i + 3), \cdots$, 由于 $k$ 范围的限制, 一定会存在一个 $i$, 使得 $f(i) \neq f(i+3)$. 然后查询 $f(i + 1)$, $f(i + 2)$. 从 $i$ 到 $i + 5$ 之间一定会有一个位置 $p$, 满足 $f(p) \neq f(p - 1)$ 且 $p$ 和 $p+1$ 一定一个是 imposter, 一个是 crewmate. 此时根据 ? p p+1 i 就可以知道 $i$ 的成分, 这样再来 $4$ 次就可以知道从 $i$ 到 $i+5$ 中除去 $p$ 和 $p+1$ 的答案, 额外查询 $1$ 个 ? imposter crewmate p 就可以得到 $p$ 和 $p+1$ 的答案.
对于剩下的 $\frac n3 - 2$ 个三元组, 借助于一个确定的 imposter 和一个确定的 crewmate 并根据 $f(i)$ 的值讨论就好了, 每个三元组用 $2$ 次询问.
总询问次数是 $n + 3$.
Edu Round #118 (Div. 2)
A
注意读题. 当 $x + y$ 是奇数时无解, 否则给出答案 $(\lfloor \frac x2 \rfloor, \lceil \frac y2 \rceil)$.
B
贪心. 尽可能把较大的数放在左边, 较小的数放在右边. 如果按照该原则无法构造出符合限制的答案, 那么一定无解.
C
学二分, 拿红名. 发送出去的表情数量是随行数单调增加的, 直接二分就好了.
D
和求 GCD 思路差不多的一道题. 首先考虑 $a = b$ 的情况, 直接判断 $a$ 和 $x$ 是否相等. 再令 $a < b$, 并记答案为 $f(a, b)$, 枚举一些后继情况之后可以发现
E
对于信息 $j$, 如果学生 $i$ 满足 $m_i = j$, 那么对答案有贡献 $\frac{\min\{ k_i, t \}}{t}$. 注意到一个重要条件 $k_i \leq 20$. 首先考虑 $t > 20$ 的情况, 容易发现该条件下 $t+1$ 时的答案一定小于 $t$ 时的答案. 于是从 $1$ 到 $20$ 枚举 $t$, 对于每一个 $t$ 选择对答案贡献最多的 $t$ 个信息就好了.
时间复杂度 $O(n + km\log m)$.
Round #736 (Div. 2)
A
注意到 $P \geq 5$, 那么 $P - 1$ 一定是个偶数, 直接输出 $(P - 1) / 2$ 和 $P - 1$ 就好了.
B
贪心, 让每个棋子的最终位置尽可能往一边靠就好了.
Round #736 (Div. 1)
A
注意读题, 查询操作并不会改变图的结构, 所以不是模拟, 是分类讨论 = =
首先, 孤立的点, 以及编号大于所有相邻结点的点一定不会被删去. 其次, 对于一个结点 $u$, 如果存在相邻的点 $v$ 满足 $v > u$, 那么 $u$ 最终一定被删去. 那么对一个结点 $u$ 记录相邻且编号大于 $u$ 的结点个数, 并依此维护答案就好了.
时间复杂度 $O(m + q)$.
B
记 $d_i = a_i - a_{i - 1}$, 那么 $a_{L\ldots R}$ 是 friends group 的条件就是 $\gcd(d_{L + 1}, \ldots, d_{R}) \geq 2$. 此时二分区间长度, 并维护区间 GCD 就好了. 可以用 ST 表或是线段树来实现.
如果用 ST 表, 那么时间复杂度为 $O(n \log n)$.