/*
CF786A - Berzerk
http://codeforces.com/contest/786/problem/A
博弈论
直接搜出NP状态图。记得要记忆化剪枝。
*
*/
#include <cstdio>
#include <cstring>
//#define tle
#ifdef tle
//#define test using namespace std;
const int Nmax=;
int now;
int is[][Nmax];
int n;
int s[][Nmax];
int tmp[][Nmax];
int k[];
#ifdef test
void watch()
{
for(int i=;i<=;i++)
{
printf("s[%d]:\n",i);
for(int j=;j<=n;j++)
printf("%d ",is[i][j]);
printf("\n");
}
}
#endif void work()
{
for(int j=;j<=;j++)
for(int i=;i<=k[j];i++)
{
int x=(n+-s[j][i])%n;
while(x<=)
x+=n;
is[j][x]=;
}
#ifdef test
watch();
#endif for(int t=;t<=;t++)
{
for(int ii=;ii<=;ii++)
for(int jj=;jj<=n;jj++)
tmp[ii][jj]=is[ii][jj];
for(int now=;now<=;now++)
for(int i=;i<=n;i++)
{
if(is[now][i]!=-)
continue;
int flag=;
for(int j=;j<=k[now];j++)
{
int x=(i+s[now][j])%n;
while(x<=)
x+=n;
if(is[now^][x]==)
{
is[now][i]=;
flag=;
break;
}
if(is[now^][x]==-)
flag=;//标记不是P态
}
if(!flag)
is[now][i]=;
#ifdef test
printf("is[%d][%d]:\n",now,i);
watch();
#endif }
int ff=;
for(int ii=;ii<=;ii++)
{
if(ff)
break;
for(int jj=;jj<=n;jj++)
if(tmp[ii][jj]!=is[ii][jj])
{
ff=;
break;
}
}
if(!ff)
break;
} } void init()
{
for(int i=;i<=n;i++)
is[][i]=is[][i]=-;
is[][]=is[][]=;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=;i++)
{
scanf("%d",&k[i]);
for(int j=;j<=k[i];j++)
scanf("%d",&s[i][j]);
}
init();
work();
for(int t=;t<=;t++)
{
for(int i=;i<=n;i++)
{
if(i!=)
printf(" ");
if(is[t][i]==-)
printf("Loop");
else if(is[t][i]==)
printf("Lose");
else
printf("Win");
}
printf("\n");
}
}
#endif using namespace std;
const int Nmax=;
int now;
int is[][Nmax];
int n;
int s[][Nmax];
int tmp[][Nmax];
int k[]; void dfs(int now,int x,int sstatus)
{
if(is[now][x]!=-)//如果已经有状态了,返回
return;
is[now][x]=sstatus;
if(sstatus==)//如果当前点为必败态,则让与其相接的点为必胜态
{
for(int i=;i<=k[now^];i++)
{
int next=(x-s[now^][i])%n;
while(next<=)
next+=n;
dfs(now^,next,);
}
}
if(sstatus==)//如果当前点为必胜态,则让与其相接的点的非必胜态边个数-1
{
for(int i=;i<=k[now^];i++)
{
int next=(x-s[now^][i])%n;
while(next<=)
next+=n;
tmp[now^][next]--;//利用tmp数组记录当前相接的点的非必胜态个数来剪枝,如果相邻点都是必胜态,则当前点为必败态
if(!tmp[now^][next])
dfs(now^,next,);
}
}
} void init()
{
for(int i=;i<=n;i++)
is[][i]=is[][i]=-;
is[][]=is[][]=;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=;i++)
{
scanf("%d",&k[i]);
for(int j=;j<=k[i];j++)
scanf("%d",&s[i][j]);
for(int j=;j<=n;j++)
tmp[i][j]=k[i];
}
init();
for(int j=;j<=;j++)
for(int i=;i<=k[j];i++)
{
int x=(n+-s[j][i])%n;
while(x<=)
x+=n;
dfs(j,x,);
}
for(int t=;t<=;t++)
{
for(int i=;i<=n;i++)
{
if(i!=)
printf(" ");
if(is[t][i]==-)
printf("Loop");
else if(is[t][i]==)
printf("Lose");
else
printf("Win");
}
printf("\n");
}
return ;
}

最新文章

  1. [LeetCode] Count Univalue Subtrees 计数相同值子树的个数
  2. setInterval() 方法可按照指定的周期(以毫秒计)来调用函数或计算表达式
  3. Nova相关命令收集
  4. geeksforgeeks@ Minimum Points To Reach Destination (Dynamic Programming)
  5. 【repost】如何学好编程 (精挑细选编程教程,帮助现在在校学生学好编程,让你门找到编程的方向)四个方法总有一个学好编程的方法适合你
  6. Oracle backgroup processes
  7. 转 C#String与string的区别
  8. iOS- 三步快速集成社交化分享工具ShareSDK
  9. JavaScript篇 深入理解JavaScript函数
  10. SQL SERVER 基本操作语句
  11. 站在Web3.0 理解IPFS是什么
  12. vue2.0 + element-ui 通过vue-cli 脚手架搭建的有关网络安全的项目源代码
  13. Python_迭代器-生成器-复习-习题_41
  14. 解决qt提示:qt.network.ssl: QSslSocket: cannot call unresolved function DH_free
  15. java基础-day20
  16. 【Android】Android如何对APK反编译
  17. 【转】什么是JavaScript
  18. 团队开发中,eclipse中安装jre
  19. cout的输出格式初探3
  20. ADFUtils

热门文章

  1. 读取url中某个值
  2. struts的工作流程
  3. 随时随地日志Debug
  4. Nginx实现负载均衡 + Keepalived实现Nginx的高可用
  5. AtCoder Regular Contest 069
  6. mybatis 高级映射和spring整合之逆向工程(7)
  7. 读《Android电视机(机顶盒)初次开发的一些经验分享》后的笔记
  8. (到8.1为止)Android版本名称与内容
  9. SQL数据库链接代码的解释
  10. SQLite Tips