题解：CF917B MADMAX

CF917B

题意

有一个

n

个点

m

条边的 DAG，每条边上有一个小写字母

c

表示这条边的权值。

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

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

思路

我们考虑设计状态

(x, y, c)

表示当前 Alice 的棋子在结点

x

上，Bob 的棋子在结点

y

上，走过的最后一条边为

c

时，是否先手必胜。

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

代码

CPP

#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;
}

文章操作

CF917B

题意

思路

代码

相关推荐

评论

题解：CF917B MADMAX