A. 模拟

B. 贪心

C. 尝试都变成 l。

D. 贪心的寻找答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void solve() {
  int n;
  cin >> n;
  vi a(n);
  rep(i, n) cin >> a[i];
  ll ans = lnf;
  // rep(i, n) {
  //   ll res = a[i];
  //   rep(j, i) {
  //     cmax(res, a[j] + n - 1 - j);
  //   }
  //   rep(j, i + 1, n) {
  //     cmax(res, a[j] + j);
  //   }
  //   cmin(ans, res);
  // }
  vi b(n + 1);
  for (int i = n - 1; i >= 0; i--) b[i] = max(b[i + 1], a[i] + i);
  vi c(n + 1);
  for (int i = 0; i < n; i++) c[i + 1] = max(c[i], a[i] + n - 1 - i);
  rep(i, n) {
    ll x = max({b[i + 1], c[i], a[i]});
    cmin(ans, x);
  }
  cout << ans << "\n";
}

E. 每次可以删叶子，如果删除之后一些点存在只有两个邻居的时候，连接这两个邻居。

考虑一个点，连不连祖先，如果不连祖先，那么有几个方案是这样的:

  • 选一个儿子，直接连了。

  • 选两个儿子，这俩连起来。

  • 选三个以上儿子，全都可以连起来（但是一定要带上本身这个点）

要连祖先的话，我们在更新完上面的事情之后再求出连祖先的方案。

  • 选一个儿子，直接就是那个儿子的贡献，（因为这种情况本身这个点会被缩掉）
  • 选大于等于两个儿子，都可以要。