首页 > ACM题库 > HDU-杭电 > hdu 1944 S-Nim-博弈论-[解题报告]C++
2013
12-26

hdu 1944 S-Nim-博弈论-[解题报告]C++

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

题意:多组测试数据 ,输入 k个集合S的元素,m种情况,m种(L堆,每堆hi个)。

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

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

思路:SG函数

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

SG函数

定义:

对于一个递增有界的图G(X, F)来说,SG函数g,是定义在X上的函数,函数值是非负整数,使得





用语言来描述就是:g(x)的值等于所有x的后继的SG函数中没有出现的最小非负整数。

对于递增有界的图,SG函数是唯一的、有界的。

所有的终止状态x,因为F(x)是空集,所以g(x)=0。



给出下图的SG函数。





例1

给出游戏1的SG函数,看看有什么规律,与P状态和N状态有什么关系。

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    …



例2

有一堆石子,设当前剩下n颗石子,这一步至少要取走n/2取上界颗。唯一的终止状态是剩0颗石子。给出SG函数,看看有什么规律。

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    …



根据例1的结果,我们猜测SG函数与P状态和N状态是有关的。如果g(x)=0,那么x就是P状态,否则x就是N状态。证明是很显然的,我们只要根据两者的定义,考虑以下三点:

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。

当然,SG函数还包含了其他的信息,这些信息在以后会用到。


代码:

#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必败点是指刚取过石头的人获胜,必败点无论怎么移动都只能到达必胜点。 
*/

解题转自:http://blog.csdn.net/liwen_7/article/details/7943258


  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
    不知道题目例子是怎么得出来的