「置顶」一些 Codeforces 简单题的一句话题解

今天的 Codeforces 有在下饭吗? -------- 新的在前头, 老的在后面. 当然只有我写过的 = = *xjb 乱写的, ~~懒到不怎么想用 LaTeX~~. 不配打 Div. 1, 有些 Div. 1 的题只是因为出现在了 Div. 2 里, 所以有写.* ## Round #638 (Div. 2) #### A 将所有值排序, 取最大值和前 n - 1 小的值为一组, 其余为另外一组. 求和计算差即可. 时间复杂度 $O(n \log n)$. #### B 构造. 出现数值大于 k 即无解. 构造一个序列 C, 在其中依次填入出过的值各一次, 并补齐到 k 位. 考虑到题目限制, 答案序列 B 满足 $B_i = B_{i - k + 1}$, 利用 C 构造 B 即可. 时间复杂度 $O(nk)$. #### C 构造. 将 s 中各字符按字典序排序. 若 $s_i \neq s_k$, 直接输出 s_k; 否则考虑 $s_{k + 1},\ s_n$. 若 $s_{k + 1} = s_n$, 则 k + 1 到 n 各字符相同, 平均分配即可. 否则直接将 k + 1 后的字符拼接到第 k 个字符后作为答案. 时间复杂度 $O(n)$. #### D 贪心. 从小到大枚举 2 的幂, 将 n 依次减去这些幂直到 n 小于 0. 同时记录每次减去的值 (其中最后一个数同 n 取 min). 排序, 差分后即为答案. 时间复杂度 $O(\log n \log \log n)$ #### E 答案上界为 $\lfloor \dfrac{\sum a_i + \sum b_i}{k} \rfloor$, 下界为 $\lfloor \dfrac{\sum a_i}{k}\rfloor + \lfloor \dfrac{\sum b_i}{k} \rfloor$, 且两者至多相差 1. 设 $f(i, j)$ 表示选择完第 i 个灌木, 是否存在共选择 a 的和模 k 为 j 的方案. 那么答案达到上界当且仅当区间 $[k - \sum b_i \bmod k,\ \sum a_i \bmod k]$ 可被凑出, 即存在一个篮子装同一个灌木中的浆果. $O(n k ^ 2)$ 转移即可算出 f. #### F 本质在求是否存在二分图完美匹配是否唯一. 首先可以贪心求出一组方案. 以网络流求解二分图匹配类比, 在残量网络上出现环即有多解, 沿着环位移即可得到其他方案. 实现时用 `set` 记录当前所有可用 friends, 遍历完一个位置之后把当前位置上经过的 friends 删去. 考虑到每个点只被经过一次, 时间复杂度 $O(n \log n)$. ## Edu Round #86 (Div. 2) #### A 记 m = min(x, y), 那么答案为 $\min \{ax + ay,\ bm + a (x - m) + a (y - m)\}$. #### B 注意到一定能构造出周期为 1 的串 S. 直接构造即可, 必要时加入一些字符. 注意特判全为 1 和全为 0 的情况. 单组数据时间复杂度 $O(n)$. #### C 记 l = lcm(a, b), $f_n = \sum\limits_{i = 1} ^ n [(i \bmod a) \bmod b \neq (i \bmod b) \bmod a]$. 预处理 f(1) ~ f(l), 那么 $f_n = \lfloor \frac{n}{l} \rfloor f(l) + f(n \bmod l)$. 取 l-1, r 的值相减即可. 单组数据时间复杂度 $O(ab + q)$. #### D 记 cnt(i) 为大于等于 i 的数组个数. 那么数据组数 $t = \max\{ \lceil\frac{cnt(i)}{c_i}\rceil \}$. 将 m 排序, 按大小顺序依次分别填入 1, 2, ..., t, 1, 2, ..., t, ... 时间复杂度 $O(n \log n + k)$. #### E 考虑边界. k = 0 时答案为 n!, k 大于等于 n 时答案为 0. 其他情况套二项式反演. 假设每行各有 1 个 rock, 那么所有 rock 占去 n-k 列. 设 f(k) 表示恰好 k 对, g(k) 表示钦定 k 对. 有 $f(k) = \sum\limits_{i=k}^{n-1}(-1)^{i-k}\binom{i}{k}g(k)$, $g(k) = \binom{n}{k}(n-k)^n$. ~~NTT 即可~~. 答案为 2f(k). #### F 状压 DP. 每次选择一个子集和子集中的一个位置, 将子集中元素合并到该位置上. 记 f(i, p, S) 为选择完第 i 个集合, 最后一次合并位置为 p, 以选择元素集合为 S 时, 得到的最小末位元素. 转移时枚举 S 补集, 满足新增子集元素和大于前一状态的值即可. 输出方案记录决策点即可. 时间复杂度 $O(n ^ 2 3 ^ n)$. ## Round #637 (Div. 1 + Div. 2) ### Div. 2 #### A 两个区间, 判定是否相交. $O(1)$ 判定即可. #### B 处理每个 peaks 位置. 枚举每个位置, 利用前缀和 $O(1)$ 计算 peaks 个数, 取 max. 时间复杂度 $O(n)$. ### Div.1 #### A 手玩, 发现确定两端之后整体就确定了. 进一步找规律, 生成的排列从左向右一定满足: 由多个公差为 1 的等差数列组成, 末项为未出现过的数中的最大值. 依此 $O(n)$ 判定. #### B 预处理每个位置, 修改为另一个数字的花费. 从后往前 DP 判定是否存在合法方案. 时间复杂度 $O(10nk)$. #### C 设 $f(i, j)$ 表示在 $d_i$, 当前周期内绿灯过了 j 秒, 的最小红绿灯变化周期个数. 利用 $f(i, j)$ 更新 $f(i \plusmn 1, j')$ 即可. 每次距离只会 +1 / +0, 利用 0-1 BFS 计算 f(i, j), 时间复杂度 $O(mg)$. ## Round #635 (Div.1 + Div. 2) ### Div. 2 #### A 输出 b, c, c. #### B 贪心. 能使用操作 1 且操作一能使血量减少就用. 判定使用完之后能否使用操作 2 击杀即可. 单次时间复杂度 $O(\log x)$. ### Div. 1 #### A 贪心. 从叶子开始选, 那么每次选点对答案的贡献为 depth[u] - size[u] (1 为根且 depth[1] = 1), 选点后将其从树上删去, 并更新可选叶子. 选择前 k 个对答案贡献最大的点即可. #### B 将 A, B, C, 排序, 去重. 分别对 A, B, C, 进行如下操作: 枚举每个位置, 选择另外两个序列中的前驱后继, 更新答案. 时间复杂度 $O(n \log n)$. #### C 考虑区间 DP. 记 f(L, R) 为 S 匹配出 T[L...R] 的方案数. 转移显然, 注意预处理和统计答案部分. 时间复杂度 $O(n^2)$. #### D 从 2 到 n-2 依次问一遍, 然后询问 n, n-1, n. 考虑到刻子只是不能区分 0 / 1, 而 n 询问两次, 因而可以确定 n, 从后向前推即可. ## Round #633 (Div.1 + Div. 2) ### Div. 2 #### A 手玩, 输出 n. #### B 排序, 将最大值 - 最小值交替排列. ### Div. 1 #### A 如果答案为 k, 那么 $2^k - 1$ 的差值都可在 k 次操作内补齐. 维护每个位置值最小的满足单调不升的 a, 根据差值计算 k. #### B 考虑最小值, 取值只可能为 3 或 1. 根据是否存在两叶子间距为奇数判定. 考虑最大值. 统计每个节点的儿子中叶子节点, 将这些叶子节点分别合并为一个节点, 挂在父亲节点上. 合并后树边个数即为最大值. #### C 打表 + 找规律. 序列每 3 个分一组, 每组记作 a, b, c. a 规律显然, b 从低位向高位每两位按 `00 10 11 01` 循环, 循环节为 2 的幂次. c 通过 a, b 计算. ## Edu Round 85 (Div. 2) #### A p, c 一定单调不降, 且 p 的增量一定大于等于 c. 注意 p_1 和 c_1 不要遗漏. 时间复杂度 $O(n)$. #### B 从大到小排序, 在平均值大于等于 x 时一直选. 时间复杂度 $O(n \log n)$. #### C 假定爆炸伤害 B 一点不浪费, 求出最小花费 s. 枚举每个位置, 在 s 的基础上计算从该位置开始击杀的花费, 取 min. 时间复杂度 $O(n)$. #### D 找规律. 将路径分组, 一定形同 1, 2, 1, 3, 1, ..., 1, n; 2, 3, 2, 4, 2, ..., 2, n; ...; n - 1, n; 1. 模拟即可. 时间复杂度 $O(R - L + 1)$. #### E 数论题. 最优的路径一定形同 $u \rightarrow \gcd(u, v) \rightarrow v$. $u \rightarrow \gcd(u, v)$ 的因数个数一定不断减小, 对 $u / \gcd(u, v)$ 质因数分解同时计算方案数即可, 本质是可重集排列数. 提前对 D 质因数分解, 那么单次时间复杂度 $O(\log D)$. #### F 考虑 DP. 做一步转化, 删去代价最小即保留最大权值. 容易得出一个二维 DP, 记录匹配到 a, b 中的位置. 不妨强制 a_i 一定选, 那么 b_j 唯一, 省去一维状态. 转移为单点修改, 后缀加, 单点取 max, 可用 BIT 维护差分后的值简单实现. 时间复杂度 $O(n \log n)$. #### G 套路题. 考虑用 FFT 加速字符串匹配, 没了. 如果使用 NTT, 可随机模数 / 给每个字符赋上随机的不同权值避免被卡. 时间复杂度 $O(n \log n)$. *再往前写过的都忘了, 或者是压根没做 = =* --------