专栏文章

题解：P11593 [NordicOI 2024] Thin Ice

FFstAutoMaton
P11593题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minm6vdw
此快照首次捕获于
2025/12/02 04:41
3 个月前
此快照最后确认于
2025/12/02 04:41
3 个月前
查看原文

[NordicOI 2024] Thin Ice

感觉还是比较难的题，想了很久才看懂题解。
考虑如何刻画一个捡金币的过程。正着走要考虑的限制很多，不如从边界位置倒序推回去，将捡金币变成放金币。
考虑这个时候的策略，对于一个可以到达且没有放置金币的位置我们一定会选择放金币，因为这样可以让之后的限制更加宽松。
考虑一个格子在当前的金币数量下能否抵达。假设从一个格子移动到了另外一个格子，那么限制就只需要满足小的那一个格子。于是我们可以在任意相邻的格子之间连边，并将边权设为这两个格子中限制更加严格的那一个（即如果这两个格子为 (x,y)(x,y) 和 (x′,y′)(x^{'},y^{'})，就将边权设为 min⁡(ax,y,ax′,y′)\min(a_{x,y},a_{x^{'},y^{'}})）。
现在是一个图上问题，依旧非常不好做。但我们可以发现对于这张图上的一个环的权值最小的边，我们可以围着环绕一圈，即可以将这条边从图中删去。重复这个过程可以发现，我们实际上只需要保留这个图路径上最小边权最大的重构树。
于是问题从图上转化为了树上。由于现在我们需要模拟放置金币的过程，所以可以先二分答案，然后进行 check。
考虑 dp，设 fif_i 表示 ii 的子树内任意走能留下来的金币数量的最小值。转移的时候枚举每一个儿子，如果其最少留下的金币数符合当前节点的限制就说明可以向那边走，而其余子树的可放置金币数直接减去即可，最终的合法条件就是 frt≤0f_{rt}\le 0，时间复杂度 O⁡(nmlog⁡nm)\operatorname{O}(nm\log nm)，可以通过。
代码放一下主要的 dp 函数（aa 是原题面中的 dd）：
CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...