题解：CF917B MADMAX

Yan719 · 2025-11-25 15:04:24 · 题解

CF917B

题意

有一个 n 个点 m 条边的 DAG，每条边上有一个小写字母 c 表示这条边的权值。

Alice 和 Bob 每人有一个棋子，每一轮游戏由对应的玩家沿着边移动他的棋子，要求：每次移动经过的边的 ASCII 码单调不降，不能走的人输掉这盘棋。

给定初始位置，两人都按照最优策略走，是否先手必胜。

思路

我们考虑设计状态 (x, y, c) 表示当前 Alice 的棋子在结点 x 上，Bob 的棋子在结点 y 上，走过的最后一条边为 c 时，是否先手必胜。

然后，我们直接记忆化搜索即可。

代码

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int N = 110;

int n, m, f[N][N][30];
vector<pii> g[N];

bool dfs(int x, int y, int k) {
    if (f[x][y][k] != -1) return f[x][y][k];
    f[x][y][k] = 0;
    for (auto [v, w] : g[x]) {
        if (k <= w) {
            if (!dfs(y, v, w)) f[x][y][k] = 1;
        }
    }
    return f[x][y][k];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    while (m--) {
        int u, v; char c;
        cin >> u >> v >> c;
        g[u].push_back({v, c - 'a'});
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            fill(f[i][j], f[i][j] + 26, -1);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dfs(i, j, 0), cout << (f[i][j][0] ? 'A' : 'B');
        }
        cout << '\n';
    }
    return 0;
}