【CF#786A】Berzerk

  • 本文为博主原创,未经许可不得转载

题目翻译

有一个写着1~n的转盘,A和B各有一个数的集合a,b,他们分别可以将转盘的指针顺时针转动a[i]和b[j]格,先将指针转到1者胜。

对于每一个指针的初始位置以及先手情况,判断胜负。

题解

博弈论中有一个经典的结论:必胜态可以转移到必败态,必败态只能转移到必胜态。

我们知道1必败态,据此我们可以通过dfs或bfs来确定所有结点的状态,然后判断初始状态就行了。

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define FILE "read"
int n,cnt[2],a[2][7010],vis[2][7010],ans[2][7010];
queue<int>q;
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int main(){
//freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
n=read();
for(int i=0;i<=1;++i){
cnt[i]=read();
for(int j=1;j<=cnt[i];++j) a[i][j]=read();
}
q.push(1); q.push(-1); ans[0][1]=ans[1][1]=-1;
while(!q.empty()){
int x=q.front(),y=abs(x);q.pop();x=(x<0?0:1);
for(int i=1;i<=cnt[x^1];++i){
int z=y-a[x^1][i]; if(z<=0) z+=n;
if(ans[x][y]==-1) {if(ans[x^1][z]!=1)ans[x^1][z]=1,q.push(x?-z:z);}
else{
if(ans[x^1][z]!=0) continue;
vis[x^1][z]++;
if(vis[x^1][z]==cnt[x^1]) ans[x^1][z]=-1,q.push(x?-z:z);
}
}
}
for(int i=0;i<=1;++i){
for(int j=2;j<=n;++j){
if(ans[i][j]==-1) printf("Lose ");
else if(ans[i][j]==0) printf("Loop ");
else printf("Win ");
}
printf("\n");
}
return 0;
}
文章目录
  1. 1. 题目翻译
  2. 2. 题解
,