题解：P11593 [NordicOI 2024] Thin Ice

· · 题解

[NordicOI 2024] Thin Ice

感觉还是比较难的题，想了很久才看懂题解。

考虑如何刻画一个捡金币的过程。正着走要考虑的限制很多，不如从边界位置倒序推回去，将捡金币变成放金币。

考虑这个时候的策略，对于一个可以到达且没有放置金币的位置我们一定会选择放金币，因为这样可以让之后的限制更加宽松。

考虑一个格子在当前的金币数量下能否抵达。假设从一个格子移动到了另外一个格子，那么限制就只需要满足小的那一个格子。于是我们可以在任意相邻的格子之间连边，并将边权设为这两个格子中限制更加严格的那一个（即如果这两个格子为 (x,y) 和 (x^{'},y^{'})，就将边权设为 \min(a_{x,y},a_{x^{'},y^{'}})）。

现在是一个图上问题，依旧非常不好做。但我们可以发现对于这张图上的一个环的权值最小的边，我们可以围着环绕一圈，即可以将这条边从图中删去。重复这个过程可以发现，我们实际上只需要保留这个图路径上最小边权最大的重构树。

于是问题从图上转化为了树上。由于现在我们需要模拟放置金币的过程，所以可以先二分答案，然后进行 check。

考虑 dp，设 f_i 表示 i 的子树内任意走能留下来的金币数量的最小值。转移的时候枚举每一个儿子，如果其最少留下的金币数符合当前节点的限制就说明可以向那边走，而其余子树的可放置金币数直接减去即可，最终的合法条件就是 f_{rt}\le 0，时间复杂度 \operatorname{O}(nm\log nm)，可以通过。

代码放一下主要的 dp 函数（a 是原题面中的 d）：

int Id(int i, int j) {
  return (i - 1) * m + j;
}

void InitDfs(int u) {
  for (int i : g[u]) {
    InitDfs(i);
    s[u] += s[i];
  }
  s[u]++;
}

void Dfs(int u) {
  for (int i : g[u]) {
    Dfs(i);
    if (f[i] <= a[u]) {
      f[u] = min(f[u], f[i] - s[u] + s[i]);
    }
  }
}

bool Check(int x) {
  for (int i = 1; i <= n * m; i++) {
    f[i] = kInf;
  }
  for (int i = 1; i <= m; i++) {
    (x <= a[Id(1, i)]) && (f[Id(1, i)] = x - s[Id(1, i)]);
    (x <= a[Id(n, i)]) && (f[Id(n, i)] = x - s[Id(n, i)]);
  }
  for (int i = 1; i <= n; i++) {
    (x <= a[Id(i, 1)]) && (f[Id(i, 1)] = x - s[Id(i, 1)]);
    (x <= a[Id(i, m)]) && (f[Id(i, m)] = x - s[Id(i, m)]);
  }
  Dfs(rt);
  return f[rt] <= 0;
}