HDU_5724_状态压缩的sg函数
2024-08-31 03:15:32
题目链接: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 ;
}
最新文章
- 2016-08-05:samba服务器配置
- CPU informition
- sqlserver 常用sql语句
- Android 动画深入解析
- Python之类型转换
- 录制游戏视频——fraps
- JavaEE基本了解
- 设置contentType
- UrlDownloadFile, 线程下载文件, 带进度条
- Python之登陆接口设计
- 华硕 F1A55-M LX3系列跳线图
- JSON.parse()——Uncaught SyntaxError: Unexpected token \ in JSON at position 1
- linux硬件数据
- Ajax和Json实现自动补全
- Linux之通配符实验
- A Plug for UNIX POJ - 1087(模板题 没啥好说的。。就用了一个map)
- php并发
- 八大排序算法的Java代码实现
- 【转载】gdi+ 内存泄漏
- 微信小程序 发送模版消息
热门文章
- Industrial Nim
- Divisible Group Sums
- hdu 4786 最小生成树与最大生成树
- EXt js 学习笔记总结
- [bzoj3295][Cqoi2011]动态逆序对_主席树
- [RxJS] exhaustMap vs switchMap vs concatMap
- Wscript对象具体解释
- Corona 不同设备分辨率适应
- Java:深入自定义注解(Annotation)
- It&;#39;s not a Bug, It&;#39;s a Feature! (poj 1482 最短路SPFA+隐式图+位运算)