DDOSvoid's Blog

CF 786A Berzerk

发表于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/786/A

Solution

只能到必胜态的一定是必败态，能到必败态的一定是必胜态

在这道题中，如果能够到达的所有状态均为必胜态则为必败态，反之如果没有必败态则为平局

记搜即可，注意只有当一个点的状态确定才能从这个点开始 $dfs$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#define maxn 7010
using namespace std;

int n, k[2], a[maxn][2];

int ans[maxn][2], cnt[maxn][2];
void dfs(int u, int o) {
    for (int i = 1; i <= k[o ^ 1]; ++i) {
        int v = (u + n - a[i][o ^ 1]) % n;
        if (~ans[v][o ^ 1]) continue ;
        if (!ans[u][o]) ans[v][o ^ 1] = 1, dfs(v, o ^ 1);
        else if (++cnt[v][o ^ 1] == k[o ^ 1]) ans[v][o ^ 1] = 0, dfs(v, o ^ 1);
    }   
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; fill(ans[0], ans[0] + maxn * 2, -1);
    for (int o = 0; o <= 1; ++o) {
        cin >> k[o]; 
        for (int i = 1; i <= k[o]; ++i) cin >> a[i][o];
    }
    ans[0][0] = ans[0][1] = 0; dfs(0, 0); dfs(0, 1);
    string s[3] = { "Loop", "Lose", "Win" };
    for (int o = 0; o <= 1; ++o) 
        for (int i = 1; i < n; ++i)
            cout << s[ans[i][o] + 1] << " \n"[i == n - 1];
    return 0;
}