题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5724

题目大意:n行20列的棋盘,对于每行,如果当前棋子右边没棋子,那可以直接放到右边,如果有就跳过放到其后面的第一个空位子,A先操作,最后谁无法操作则输,给定每行棋子状态,问先手是否必胜

题目分析:组合博弈问题,直接sg函数,因为列只有20,可以状压搞,枚举每个状态,找到该状态下可行的操作然后标记,sg函数结论可参考sg函数和sg定理

sg函数还需学习。

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<map>
using namespace std; int sg[(<<)+],vis[]; int getSg(int sta)
{
memset(vis,,sizeof(vis));
for(int i=; i>=; i--)
{
if(sta&(<<i))
{
int tmp=sta;
for(int j=i-; j>=; j--)
if(!(sta&(<<j)))
{
tmp^=(<<i)^(<<j);
vis[sg[tmp]]=;
break;
}
}
}
for(int i=; i<=; i++)
if(vis[i]==)
return i;
return ;
}
int main()
{
int t;
memset(sg,,sizeof(sg));
for(int i=; i<(<<); i++)
sg[i]=getSg(i);
scanf("%d",&t);
while(t--)
{
int n,ans=;
scanf("%d",&n);
for(int i=; i<n; i++)
{
int m,sta=;
scanf("%d",&m);
while(m--)
{
int pos;
scanf("%d",&pos);
sta|=(<<(-pos));
}
ans^=sg[sta];
}
if(ans)
printf("YES\n");
else
printf("NO\n");
}
return ;
}

最新文章

  1. 2016-08-05:samba服务器配置
  2. CPU informition
  3. sqlserver 常用sql语句
  4. Android 动画深入解析
  5. Python之类型转换
  6. 录制游戏视频——fraps
  7. JavaEE基本了解
  8. 设置contentType
  9. UrlDownloadFile, 线程下载文件, 带进度条
  10. Python之登陆接口设计
  11. 华硕 F1A55-M LX3系列跳线图
  12. JSON.parse()——Uncaught SyntaxError: Unexpected token \ in JSON at position 1
  13. linux硬件数据
  14. Ajax和Json实现自动补全
  15. Linux之通配符实验
  16. A Plug for UNIX POJ - 1087(模板题 没啥好说的。。就用了一个map)
  17. php并发
  18. 八大排序算法的Java代码实现
  19. 【转载】gdi+ 内存泄漏
  20. 微信小程序 发送模版消息

热门文章

  1. Industrial Nim
  2. Divisible Group Sums
  3. hdu 4786 最小生成树与最大生成树
  4. EXt js 学习笔记总结
  5. [bzoj3295][Cqoi2011]动态逆序对_主席树
  6. [RxJS] exhaustMap vs switchMap vs concatMap
  7. Wscript对象具体解释
  8. Corona 不同设备分辨率适应
  9. Java:深入自定义注解(Annotation)
  10. It&amp;#39;s not a Bug, It&amp;#39;s a Feature! (poj 1482 最短路SPFA+隐式图+位运算)