hdu_1536_S-Nim(DFS_SG博弈)
2024-08-27 02:47:37
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=1536
题意:首先输入K ,表示一个集合的大小 , 之后输入集合, 表示对于这对石子只能去这个集合中的元素的个数,之后输入 一个m, 表示接下来对于这个集合要进行m次询问, 之后m行 ,每行输入一个n ,表示有n个堆 , 每堆有n1个石子, 问这一行所表示的状态是赢还是输, 如果赢输入W否则L。
题解:sg打表会超时,只有在线算sg了,就是DFS_SG
#include<cstdio>
#include<algorithm>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std; const int N=;
int sg[N],f[],m,nn,ans,tp; int dfs_SG(int x,int *s){
if(sg[x]!=-)return sg[x];
bool v[];
F(i,,)v[i]=;
F(i,,s[])if(x>=s[i])v[dfs_SG(x-s[i],f)]=;
F(i,,N)if(!v[i]){sg[x]=i;break;}
return sg[x];
} int main(){
while(~scanf("%d",f),f[]){
F(i,,f[])scanf("%d",f+i);
sort(f+,f++f[]);
F(i,,N-)sg[i]=-;
scanf("%d",&m);
while(m--){
scanf("%d",&nn),ans=;
while(nn--)scanf("%d",&tp),ans^=dfs_SG(tp,f);
if(ans)printf("W");
else printf("L");
}
puts("");
}
return ;
}
最新文章
- 洛谷 P1074 靶形数独 Label:search 不会
- C# 中Datetime类用法总结
- 转:java.sql.SQLException: [Microsoft][ODBC 驱动程序管理器] 未发现数据源名称并且未指定默认驱动程序
- Looksery Cup 2015 B. Looksery Party 暴力
- 【Android 界面效果30】Android中ImageSwitcher结合Gallery展示SD卡中的资源图片
- JavaScript高级程序设计(八):基本概念--操作符
- SQL server聚合函数、数学函数、字符串函数
- 面向对象15.3String类-常见功能-判断
- 【BZOJ2242】【SDOI2011】计算器
- 多线程深入:乐观锁与悲观锁以及乐观锁的一种实现方式-CAS(转)
- ffmpeg笔记
- ObjectArx2013新建工程出错的解决办法
- llinux其他权限
- 《Effective Modern C++》翻译--条款2: 理解auto自己主动类型推导
- Java中mongodb使用and和or的复合查询
- linux svn配置与使用
- c# winform 中DataGridView绑定List<;T>; 不能显示数据
- mybatis 的动态SQL
- docker学习-docker镜像
- Centos7.4下安装JDK1.8