hdu 1536 sg (dfs实现)
S-Nim
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5637 Accepted Submission(s): 2414
The starting position has a number of heaps, all containing some, not necessarily equal, number of beads.
The players take turns chosing a heap and removing a positive number of beads from it.
The first player not able to make a move, loses.
Arthur
and Caroll really enjoyed playing this simple game until they recently
learned an easy way to always be able to find the best move:
Xor
the number of beads in the heaps in the current position (i.e. if we
have 2, 4 and 7 the xor-sum will be 1 as 2 xor 4 xor 7 = 1).
If the xor-sum is 0, too bad, you will lose.
Otherwise, move such that the xor-sum becomes 0. This is always possible.
It is quite easy to convince oneself that this works. Consider these facts:
The player that takes the last bead wins.
After the winning player's last move the xor-sum will be 0.
The xor-sum will change after every move.
Which
means that if you make sure that the xor-sum always is 0 when you have
made your move, your opponent will never be able to win, and, thus, you
will win.
Understandibly it is no fun to play a game when both
players know how to play perfectly (ignorance is bliss). Fourtunately,
Arthur and Caroll soon came up with a similar game, S-Nim, that seemed
to solve this problem. Each player is now only allowed to remove a
number of beads in some predefined set S, e.g. if we have S =(2, 5) each
player is only allowed to remove 2 or 5 beads. Now it is not always
possible to make the xor-sum 0 and, thus, the strategy above is useless.
Or is it?
your job is to write a program that determines if a
position of S-Nim is a losing or a winning position. A position is a
winning position if there is at least one move to a losing position. A
position is a losing position if there are no moves to a losing
position. This means, as expected, that a position with no legal moves
is a losing position.
consists of a number of test cases. For each test case: The first line
contains a number k (0 < k ≤ 100 describing the size of S, followed
by k numbers si (0 < si ≤ 10000) describing S. The second line
contains a number m (0 < m ≤ 100) describing the number of positions
to evaluate. The next m lines each contain a number l (0 < l ≤ 100)
describing the number of heaps and l numbers hi (0 ≤ hi ≤ 10000)
describing the number of beads in the heaps. The last test case is
followed by a 0 on a line of its own.
each position: If the described position is a winning position print a
'W'.If the described position is a losing position print an 'L'. Print a
newline after each test case.
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100+10
int knum,mnum,lnum;
int ans[N],si[N],hi[N],sg[];
int mex(int x)//求x的sg值(可作为模版应用)
{
if(sg[x]!=-) return sg[x];
bool vis[N];
memset(vis,false,sizeof(vis));
for(int i=;i<knum;i++) {
int temp=x-si[i];
if(temp<) break;
sg[temp]=mex(temp);
vis[sg[temp]]=true;
}
for(int i=;;i++) {
if(!vis[i]) {
sg[x]=i; break;
}
}
return sg[x];
}
int main() {
while(scanf("%d",&knum) && knum) {
for(int i=;i<knum;i++)
scanf("%d",&si[i]);
sort(si,si+knum);
memset(sg,-,sizeof(sg));
sg[]=;
memset(ans,,sizeof(ans));
scanf("%d",&mnum);
for(int i=;i<mnum;i++) {
scanf("%d",&lnum);
for(int j=;j<lnum;j++) {
scanf("%d",&hi[i]); ans[i]^=mex(hi[i]);//尼姆博弈
}
}
for(int i=;i<mnum;i++)
{
if(ans[i]==) printf("L");
else printf("W");
}
printf("\n");
}
return ;
}
#include"iostream"
#include"algorithm"
#include"string.h"
using namespace std;
int s[],sg[],k;
int getsg(int m)
{
int hash[]={};
int i;
for(i=;i<k;i++){
if(m-s[i]<)
break;
if(sg[m-s[i]]==-)
sg[m-s[i]]=getsg(m-s[i]);
hash[sg[m-s[i]]]=;
}
for(i=;;i++)
if(hash[i]==)
return i; }
int main()
{
//int k;
// freopen("game.in","r",stdin);
//freopen("game.out","w",stdout);
while(cin>>k,k)
{
int i;
for(i=;i<k;i++)
cin>>s[i];
sort(s,s+k);
memset(sg,-,sizeof(sg));
sg[]=;
int t;
cin>>t;
while(t--)
{ int n,m;
cin>>n;
int ans=;
while(n--)
{
cin>>m;
if(sg[m]==-)
sg[m]=getsg(m);
ans^=sg[m];
}
if(ans)
cout<<'W';
else cout<<'L';
}
cout<<endl;
}
return ;
}
最新文章
- RPC框架实现 - 通信协议篇
- marquee标签滚动效果
- Linux 网络编程详解五(TCP/IP协议粘包解决方案二)
- mvc-1
- IOS第14天(1,UITabBarController的基本的使用)
- Jedis 连接redis超时
- JOB的创建,定时,执行
- Btrace是一个实时监控工具
- thrift TNonblockingServer 使用
- 使用Web Application Stress Tool 进行压力测试
- 关于Hbase的cache配置
- 使用RGBa和Filter实现不影响子元素的CSS透明背景
- 理解FMS中的实例
- executssql 函数的每一句代码的意思
- C语言错题小本子
- nginx做80端口转发
- Flask 框架介绍
- Python爬虫爬取贴吧的帖子内容
- Spring Cloud Eureka 服务消费者
- soj1767.传纸条