题解:AT_bogosortcontest_div1_c Moving Silver

· · 题解

设 f_i(u) 表示剩余 i 步,棋子位于点 u,轮到 Alice 的最大得分。同理设 g_i(u) 表示剩余 i 步,Bob 位于点 u 的最小得分,枚举出边 u\to v 有如下转移

f_i(u)=\max_{u \to v} g_{i-1}(v)\\ g_i(u)=\min_{u \to v} f_{i-1}(v)

边界 f_0(u)=g_0(u)=a_u。代入一轮递推得 f_i(u)=\max\limits_{u \to v} \min\limits_{v \to w} f_{i-2}(w)。

令 k=\lfloor H/2\rfloor+1,我们断言

f_{2i}=f_{2k},\quad f_{2i+1}=f_{2k+1},\quad \forall i \ge k

:::::success[断言的证明]{open}

任取阈值 t,令 a_u \gets [a_u \ge t] 转 01 序列。只要对任意 t 说明结论成立。

引理 若 g_{2i-2}(x,y)=1 \land g_{2i}(x,y)=0,必有 x \ge 2i。

证明 设 u=(x,y),v 为 u 的斜向邻居。由于 u \leftrightarrow v 是双向边,必有 f_{2i-1}(v)=1。

所以让 g(u)=1 \to 0 的只能是 p=(x-1,y)。设 l=(x,y-1),r=(x,y+1),取 \min 都能选到 0,从而 g_{2i}(l)=g_{2i}(r)=0。

若 i \ge 2,第 2i-2 轮 g_{2i-2}(u)=1 传递给 u \to p,点 p 的 f 值突变

f_{2i-3}(p)=1 \longrightarrow f_{2i-1}(p)=0

必有 p 的后继 p \to w 发生了 g_{2i-4}(w)=1 \to g_{2i-2}(w)=0 的突变。

而 w=l \lor w=r 是不可能的,所以 w 只能位于 x-2 行。归纳下去就有 x\ge 2i。

将引理应用在 f 和 g 上:

令 k=\lfloor H/2 \rfloor+1,第 k 轮后 f,g 均无突变,命题得证。

:::::

只要做 2k+1 轮递推即可。

将询问离线后滚动数组,时间 O(H^2W) 空间 O(HW)。

const int N = 605, M = 2e5 + 5, inf = 2e9;
const int dirx[] = {-1, -1, -1, +1, +1};
const int diry[] = {-1, 0, +1, -1, +1};
int n, m, k, q, a[N][N], ans[M];
int f[2][N][N], g[2][N][N];
vector<tuple<int, int, int>> Q[N];

void _main() {
    cin >> n >> m; k = n/2+1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            f[0][i][j] = g[0][i][j] = a[i][j];
        }
    cin >> q;
    for (i64 i = 1, x, y, c; i <= q; i++) {
        cin >> x >> y >> c;
        c = min(c, 2*k+c%2);
        Q[c].pb(x, y, i);
    }
    for (int i = 1, st = 1; i <= 2*k+1; i++, st^=1) {
        for (int x = 1; x <= n; x++)
            for (int y = 1; y <= m; y++) {
                f[st][x][y] = -inf, g[st][x][y] = inf;
                for (int d = 0; d < 5; d++) {
                    int nx = x + dirx[d], ny = y + diry[d];
                    if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
                    chkmax(f[st][x][y], g[st^1][nx][ny]);
                    chkmin(g[st][x][y], f[st^1][nx][ny]);
                }
            }
        for (auto [x, y, id] : Q[i]) ans[id] = f[st][x][y];
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}