Codeforces 786 A. Berzerk

题目链接：http://codeforces.com/problemset/problem/786/A

这个题出做$DIV2$的$C$以及$DIV1$的A会不会难了一点啊...

做法和题解并不一样，只是很懂题解中记忆化搜索的时候怎么判断的$LOOP$

我们都知道组合游戏中一个状态所有的后继如果都是赢的那么这个状态是输的，一个状态只要有一个后继是输的那么这个状态就是赢的。

但是这个题目中有$LOOP$的情况，考虑将一个点拆为两个，分别表示第一个人和第二个人在这个点是必胜还是必败(也就是答案)，如果判断不出来就是$LOOP$

因为$LOOP$不好处理，所以考虑不是记忆化$DFS$,而是按照反向边逆向递推，这个递推过程满足拓扑序就可以了。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 #include<queue>
  9 using namespace std;
 10 #define maxn 7010
 11 #define llg long long 
 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 13 llg n,m,ans[2][maxn],N1,N2,a[maxn],b[maxn],se[2][maxn],du[2][maxn];
 14 
 15 struct node
 16 {
 17     llg v1,v2;
 18 }f[2][maxn];
 19 
 20 struct data
 21 {
 22     llg x,y;
 23 };
 24 
 25 queue<data>dl;
 26 
 27 inline int getint()
 28 {
 29     int w=0,q=0; char c=getchar();
 30     while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
 31     while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
 32 }
 33 void work()
 34 {
 35     ans[0][1]=ans[1][1]=2;
 36     data w;
 37     w.x=0,w.y=1;
 38     dl.push(w); w.x=1;
 39     dl.push(w);
 40     while (!dl.empty())
 41     {
 42         w=dl.front(); dl.pop();
 43         llg x=w.x,y=w.y;
 44         if (!x)
 45         {
 46             for (llg i=1;i<=N2;i++)
 47             {
 48                 llg wz=(y-b[i]+n-1)%n+1;
 49                 du[1][wz]--;
 50                 if (ans[1][wz]) continue;
 51                 if (ans[x][y]==2)
 52                 {
 53                     ans[1][wz]=1;
 54                     data nw; nw.x=1,nw.y=wz;
 55                     dl.push(nw);
 56                     du[1][wz]=-1;
 57                 }
 58                 if (du[1][wz]==0)
 59                 {
 60                     ans[1][wz]=2;                
 61                     data nw; nw.x=1,nw.y=wz;
 62                     dl.push(nw);
 63                     du[1][wz]=-1;
 64                 }
 65             }
 66         }
 67         else
 68         {
 69             for (llg i=1;i<=N1;i++)
 70             {
 71                 llg wz=(y-a[i]+n-1)%n+1;
 72                 du[0][wz]--;
 73                 if (ans[0][wz]) continue;
 74                 if (ans[x][y]==2)
 75                 {
 76                     ans[0][wz]=1;
 77                     data nw; nw.x=0,nw.y=wz;
 78                     dl.push(nw);
 79                     du[0][wz]=-1;
 80                 }
 81                 if (du[0][wz]==0)
 82                 {
 83                     ans[0][wz]=2;                
 84                     data nw; nw.x=0,nw.y=wz;
 85                     dl.push(nw);
 86                     du[0][wz]=-1;
 87                 }
 88             }
 89         }
 90     }
 91 }
 92 
 93 int main()
 94 {
 95     yyj("C");
 96     cin>>n;
 97     cin>>N1;
 98     for (llg i=1;i<=N1;i++) a[i]=getint();
 99     cin>>N2;
100     for (llg i=1;i<=N2;i++) b[i]=getint();
101     
102     for (llg i=1;i<=n;i++)
103     {
104         du[0][i]=N1,du[1][i]=N2;
105     }
106 
107     work();
108     for (llg i=2;i<=n;i++)
109     {
110         if (ans[0][i]==1) printf("Win ");
111         if (ans[0][i]==2) printf("Lose ");
112         if (ans[0][i]==0) printf("Loop ");
113     }
114     printf("
");
115     for (llg i=2;i<=n;i++)
116     {
117         if (ans[1][i]==1) printf("Win ");
118         if (ans[1][i]==2) printf("Lose ");
119         if (ans[1][i]==0) printf("Loop ");
120     }
121     return 0;
122 }