CF786A Berzerk
博弈论
题解
OI
切着切着搜索水题就做到它了。鉴于我还没有正式的学过博弈论，就写篇题解纪念一下吧。
题意
有一个物品放在n个排成一圈的点上，初始放在第2到n号点，甲乙各有一个数集，每次操作时可以将这个物品向后移动s格(s是集合中的数)，判断物品位于每个起始位置时，二人的胜负情况。
分析
结论：能转移到必败态的状态就是必胜态，只能转移到必胜态的状态就是必败态。（思考一下）
因此就可以从1号点开始倒着dfs，记得判平局(从1号点出发不能到达的就是平局)
代码
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 7010;
const int INF = 0x3f3f3f3f;
vector<int> s[2];
bool ans[MAXN][2];
bool vis[MAXN][2];
int cnt[MAXN][2];
int n;
void dfs(int pos,int player){
if(vis[pos][player]){
return;
}
clog << pos << ' ' << player << endl;
vis[pos][player] = true;
int last = 1-player;
for(int i = 0;i<s[last].size();i++){
int v = (pos - s[last][i] + n - 1)%n + 1;
if(v == 1){
continue;
}
if(ans[pos][player]){
cnt[v][last]++;
if(cnt[v][last] == s[last].size()){
ans[v][last] = false;
dfs(v,last);
}
}else{
ans[v][last] = true;
dfs(v,last);
}
}
}
int main(){
cin >> n;
int k0;
cin >> k0;
for(int i = 1;i<=k0;i++){
int x;
cin >> x;
s[0].push_back(x);
}
int k1;
cin >> k1;
for(int i = 1;i<=k1;i++){
int x;
cin >> x;
s[1].push_back(x);
}
dfs(1,0);
dfs(1,1);
for(int i = 2;i<=n;i++){
if(vis[i][0]){
if(ans[i][0]){
cout << "Win ";
}else{
cout << "Lose ";
}
}else{
cout << "Loop ";
}
}
cout << endl;
for(int i = 2;i<=n;i++){
if(vis[i][1]){
if(ans[i][1]){
cout << "Win ";
}else{
cout << "Lose ";
}
}else{
cout << "Loop ";
}
}
cout << endl;
}
|
