POJ 2960 S-Nim (sg函数)

题目链接：http://poj.org/problem?id=2960

题目大意：给定数组S,接下来给出m个游戏局面。游戏局面是一些beads堆，先给出堆数，然后是每一堆中beads的数目。游戏规则是，两个人轮流取beads，每次可以选择一堆，从中取出k个beads，k ∈S，最后不能取的人输。

分析： 取每一堆石子都可以看成是一个单独的游戏，因此，n堆石子就是n个游戏，每个子游戏的状态是其beads的数目，胜负很好判定，求出sg函数即可。最后所有游戏局面的Nim和即为此题的解。

参考代码：（注意优化的那个地方）

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 105

#define M 10005

int s[N], sn;

int sg[M];

void getsg(int n)

{

    int mk[M];

    sg[] = ;//主要是让终止状态的sg为0

    memset(mk, -, sizeof(mk));

    for(int i = ; i < M; i++)

    {

        for(int j = ; j < n && s[j] <= i; j++)

            mk[sg[i-s[j]]]=i;//将所有后继的sg标记为i，然后找到后继的sg没有出现过的最小正整数

                             //优化：注意这儿是标记成了i，刚开始标记成了1，这样每次需初始化mk，而标记成i就不需要了

        int j = ;

        while(mk[j] == i) j++;

        sg[i] = j;

    }

}

int main()

{

    while(~scanf("%d", &sn), sn)

    {

        for(int i = ; i < sn; i++) scanf("%d", &s[i]);

        sort(s, s+sn);//排序算一个优化，求sg的时候会用到

        getsg(sn);

        int m;

        scanf("%d", &m);

        char ans[N];

        for(int c = ; c < m; c++)

        {

            int n, tm;

            scanf("%d", &n);

            int res = ;

            for(int i = ; i < n; i++)

            {

                scanf("%d", &tm);

                res ^= sg[tm];

            }

            if(res == ) ans[c] = 'L';

            else ans[c] = 'W';

        }

        ans[m]=;

        printf("%s\n", ans);

    }

    return ;

}