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

DepletedPrism · 2020-04-27 00:18:01 · 个人记录

今天的 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, 直接输出 sk; 否则考虑 $s{k + 1},\ sn. 若 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.