Codeforces Round 1044 (Div. 2)

Codeforces Round 1044 (Div. 2)

E. I Yearned For The Mines

D. Chicken Jockey

我们先做几点观察：

1. 如果一个怪物受到摔落伤害，它会被摔到栈的最底部。这样它就不可能再次受到摔落伤害，因为下面已经没有怪物可以再让它掉落。
2. 如果一个怪物受到的摔落伤害大于 1，那么它下面的那个怪物一定是直接被攻击杀死的，而不是摔落死亡；否则它下面的怪物会先掉到地面，那么该怪物上方就只剩 1 个怪物，它最多只能受到 1 点摔落伤害。
   因此下面的怪物必须用 $h_i$ 次攻击杀掉，不管它是否原本就在初始栈中，或者它下面的怪物摔落死亡了。
   这意味着，如果某个怪物要受到超过 1 点的摔落伤害，最好在原始栈中达成，这样可以在不额外消耗攻击次数的情况下使摔落伤害最大化。

这看起来是一个很局部化的选择：
对每个怪物 $i$，我们有三种处理方式：

• 直接用攻击杀死它；
• 直接杀死它下面的怪物，让它受到 $i-1$ 点摔落伤害；
• 杀死它下面的怪物，让它受到 1 点摔落伤害。

于是定义 $dp[i]$ 为杀死前 $i$ 个怪物所需的最少攻击次数。
显然 $dp[0] = 0$，$dp[1] = h_1$。
对于 $i \ge 2$：

• 如果让怪物 $i$ 受到 1 点摔落伤害，代价是：

  $$
  dp[i - 1] + h_i - 1
  $$

• 如果让怪物 $i$ 受到最大摔落伤害，代价是：

  $$
  dp[i - 2] + h_{i - 1} + \max(0,, h_i - (i - 1))
  $$

取两者中的较小值作为 $dp[i]$。

最终答案为 $dp[n]$。

C. The Nether

先用 $n$ 次查询得到从每个位置出发的最长路径长度，选择结果最大的点作为起点。

在最长路径中，若当前点查询结果为 $k$，下一个点的结果必为 $k-1$。

在所有结果为 $k-1$ 的点 $y$ 里面查询和上一个点连通的，作为下一步，以此类推

除起点外每个点只查一次，总查询次数 $\le 2n-1$。

B. Villagers

每次操作都会让至少一名参与的村民烦躁值变为 0。

当每个村民都至少参与过一次操作后，要么他的烦躁值为 0，要么已与烦躁值为 0 的人相连，其余人可用 0 成本互通。

因此，答案等于“让每人至少参与一次操作”的最小花费。

将 $g$ 升序排序，最优方法是依次配对：

$$
(n, n-1),\ (n-2, n-3),\ (n-4, n-5),\dots
$$

若剩一人，就与次小者配对。

总花费为：

$$
g_n + g_{n-2} + g_{n-4} + \dots
$$

用反证交换可以证明一定是最优策略。

A. Redstone?

递推：

$$
v_{i} = \frac{b_{i-1}}{b_i} \cdot v_{i-1}
$$

展开：

$$
v_n = \frac{b_1}{b_2} \cdot \frac{b_2}{b_3} \cdot \dots \cdot \frac{b_{n-1}}{b_n} = \frac{b_1}{b_n}
$$

要满足 $v_n = 1$ 必须 $b_1 = b_n$。