Codeforces 786 A. Berzerk

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

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

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

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

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

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

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<queue>

 using namespace std;

 #define maxn 7010

 #define llg long long

 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

 llg n,m,ans[][maxn],N1,N2,a[maxn],b[maxn],se[][maxn],du[][maxn];

 struct node

 {

     llg v1,v2;

 }f[][maxn];

 struct data

 {

     llg x,y;

 };

 queue<data>dl;

 inline int getint()

 {

     int w=,q=; char c=getchar();

     while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();

     while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;

 }

 void work()

 {

     ans[][]=ans[][]=;

     data w;

     w.x=,w.y=;

     dl.push(w); w.x=;

     dl.push(w);

     while (!dl.empty())

     {

         w=dl.front(); dl.pop();

         llg x=w.x,y=w.y;

         if (!x)

         {

             for (llg i=;i<=N2;i++)

             {

                 llg wz=(y-b[i]+n-)%n+;

                 du[][wz]--;

                 if (ans[][wz]) continue;

                 if (ans[x][y]==)

                 {

                     ans[][wz]=;

                     data nw; nw.x=,nw.y=wz;

                     dl.push(nw);

                     du[][wz]=-;

                 }

                 if (du[][wz]==)

                 {

                     ans[][wz]=;

                     data nw; nw.x=,nw.y=wz;

                     dl.push(nw);

                     du[][wz]=-;

                 }

             }

         }

         else

         {

             for (llg i=;i<=N1;i++)

             {

                 llg wz=(y-a[i]+n-)%n+;

                 du[][wz]--;

                 if (ans[][wz]) continue;

                 if (ans[x][y]==)

                 {

                     ans[][wz]=;

                     data nw; nw.x=,nw.y=wz;

                     dl.push(nw);

                     du[][wz]=-;

                 }

                 if (du[][wz]==)

                 {

                     ans[][wz]=;

                     data nw; nw.x=,nw.y=wz;

                     dl.push(nw);

                     du[][wz]=-;

                 }

             }

         }

     }

 }

 int main()

 {

     yyj("C");

     cin>>n;

     cin>>N1;

     for (llg i=;i<=N1;i++) a[i]=getint();

     cin>>N2;

     for (llg i=;i<=N2;i++) b[i]=getint();

     for (llg i=;i<=n;i++)

     {

         du[][i]=N1,du[][i]=N2;

     }

     work();

     for (llg i=;i<=n;i++)

     {

         if (ans[][i]==) printf("Win ");

         if (ans[][i]==) printf("Lose ");

         if (ans[][i]==) printf("Loop ");

     }

     printf("\n");

     for (llg i=;i<=n;i++)

     {

         if (ans[][i]==) printf("Win ");

         if (ans[][i]==) printf("Lose ");

         if (ans[][i]==) printf("Loop ");

     }

     return ;

 }

巴特西

Codeforces 786 A. Berzerk

最新文章

热门文章