2013
12-26

# S-Nim

Arthur and his sister Caroll have been playing a game called Nim for some time now. Nim is played as follows:

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.

Input consists of a number of test cases.
For each test case: The rst 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.

Input consists of a number of test cases.
For each test case: The rst 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.

2 2 5
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

LWW
WWL

若存在移动某堆能到达一个必败点，则该点为必胜点，输出W

必败点指无论怎么移动都只能到达必胜点，输出L。

每堆看做一个子游戏，SG函数通过递归得到每种堆数的g();

SG函数

x    0    1    2    3    4    5    6    7    8    9    10    11    …

g(x)    0    1    2    3    0    1    2    3    0    1    2    3    …

x    0    1    2    3    4    5    6    7    8    9    10    11    12    …

g(x)    0    1    2    2    3    3    3    3    4    4    4    4    4    …

l    如果x是终止状态，那么g(x)=0。

l    一个状态x，如果g(x)≠0，那么一定存在一个x的后继y，使得g(y)=0。

l    一个状态x，如果g(x)=0，那么所有x的后继y，都有g(y)≠0。

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int  s[101];
int tt[10001];

int g(int x , int  k)
{
int mex[101];
memset(mex,0,sizeof(mex));
if(tt[x]!=-1) return tt[x]; //集合S一致，则每个数量的mex一样，所以可以重复利用
if(x-s[0]<0) return tt[x]=0; //s[0]为集合中最小值，x-s[0]<0,则x不可能到达其他状态，一定为P
for(int i=0;i<k && x-s[i]>=0;i++) //判断条件，因为s[]排了序，当x-s[i]<0就停止循环。
{
mex[g(x-s[i] , k)]=1; //x的后继SG函数中的没有出现的最小非负数
}
for(int i=0;;i++) //通过x的后继SG函数出现的非负数得x的结果
if(!mex[i])  return tt[x]=i;
}

int main()
{
int  k ;
int n, t ,a , ans;
while(scanf("%d",&k)!=EOF && k)
{
memset(tt,-1,sizeof(tt));
tt[0]=0;
for(int i=0;i<k;i++) scanf("%d",&s[i]);
sort(s,s+k);
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a);
ans^=g(a , k);
}
// for(int i=0;i<=12; i++) cout<<i<<"   ";cout<<endl;
//for(int i=0;i<=12;i++) cout<<tt[i]<<" ";cout<<endl;
if(!ans)  printf("L"); //异或sum！=0，说明该点为必败点，只能到达必胜点。
else printf("W");
}
printf("\n");
}
return 0;
}
/*
(0,1,1) 的异或sum=0，为必败点.
P必败点是指刚取过石头的人获胜，必败点无论怎么移动都只能到达必胜点。
*/

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

2. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的