Codeforces Round 1044

A

注意到 \(v_i = \frac{x_{i - 1}}{x_i} \times v_{i - 1} = 1\)，一直写下去就剩下 \(\frac{x_1}{x_i} = 1\)，判断是否存在两个相等的数即可。

B

进行一次操作后一个就变成 \(0\) 了，然后要连通至少要是个树，即要搞 \(n - 1\) 次，那我们肯定希望多用 \(0\) 和 \(0\) 去连。

所以直接贪心，先每次让两个最大值操作，消出一个 \(0\)。然后将 \(0\) 与 \(0\) 连边即可。

C

\(2n\) 次查询限制，所以我们不妨先对每个点求从这个点出发能走的最长距离 \(f_i\)。

然后你会发现对于 \(f_i = k\)，那么在所有 \(f_j = k - 1\) 中一定存在一个点 \(j\) 和 \(i\) 有连边。

于是就再最多查询 \(n - 1\) 次即可。

D

好牛的题。

贪心是不对的，比如说按照干掉每个怪物的性价比之类的。

考虑 DP，区间 DP 是可行的但是显然没前途。由于只支持 \(\Theta(n)\) 或者带几个 \(\log\) 不妨设 \(f_i\) 为干掉 \(1 \sim i\) 的最小代价。

先值考虑 \([1, i]\)，分析一下 \(i\) 会怎么死。一个显然的事情是每个怪只会坠落一次。进一步，怪 \(i\) 受到坠落伤害只有两种情况，一种是干掉 \(i - 1\) 对 \(i\) 造成 \(i - 1\) 的伤害，一种是前面的怪连环死，对 \(i\) 造成 \(1\) 点伤害。

于是有转移 \(f_i = \min(f_{i - 1} + h_i - 1, f_{i - 2} + h_{i - 1} + h_i - (i - 1))\)。直接就做完了。

E

还有高手。

最开始想的是类似点分治的思路选中心，但操作次数多了。但发现了一个性质是对于一条链可以从链的一端点一直访问到另一个端点，这一定能够找到答案或者排除一条链。于是考虑用不超过 \(\lfloor \frac{n}{4} \rfloor\) 个二操作将树划分成几条链。

不妨设要操作的点为 \(0\)，作为链端点的点为 \(1\)，作为链上点的为 \(2\)。考虑以下染色方式：

• 若当前点 \(u\) 有大于等于三个 \(1\) 儿子后有一个 \(2\) 儿子，则染成 \(0\)。
• 若当前 \(u\) 有正好两个 \(1\) 儿子，则染成 \(2\)。
• 否则染成 \(1\)。

会发现这样做完后对于每个 \(0\)，如果它是因为 \(1\) 儿子数量被染的，则将 \(0\) 与所有 \(1\) 分组；否则将 \(0\) 与 \(2\) 和 \(2\) 的两个 \(1\) 儿子分组。这样每组大小都大于等于 \(4\)，能够满足条件。

F

感觉比 E 简单。

将操作记成 \((l_i, r_i, x_i)\)，其中 \(x_i\) 为操作中点。则两个操作要同时选的条件是两个区间不能互相攻击中点。

将区间按照 \(l\) 排序，则 \(r\) 一定要递增，否则 \(l_i \leq l_j \leq r_j \leq r_i\)，\(j\) 没有用了。

DP，令 \(f_i\) 为考虑到第 \(k\) 个线段，其中 \(r_k = i\)。则 \(j\) 区间能转移到 \(i\) 的条件是：

• \(r_j \geq l_i - 1\)
• \(x_j < l_i \vee x_i > r_j\)

然后将限制拆成两个区间就可以使用线段树优化了。