POJ2960 S-Nim

2015.01.14 15:13 Wed| 4 visits oi_2015| 2015_刷题日常| Text

Solution

SG 函数的简单应用。

Code

#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 10005

int n, m;
int s[N], sg[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void getsg()
{
    sg[0] = 0;
    for (int i = 1; i <= 10000; ++i)
    {
        bitset<N> bits;
        for (int j = 1; j <= n; ++j)
            if (i >= s[j]) bits[sg[i - s[j]]] = 1;
        for (int j = 0; j <= 10000; ++j)
            if (!bits[j])
            { sg[i] = j; break; }
    }
}

int main()
{
    while (cin >> n, n)
    {
        for (int j = 1; j <= n; ++j)
            s[j] = read();
        getsg();
        m = read();
        for (int j = 1; j <= m; ++j)
        {
            int ans = 0, l = read();
            for (int k = 1; k <= l; ++k)
                ans ^= sg[read()];
            putchar(ans ? 'W' : 'L');
        }
        puts("");
    }

    return 0;
}