CodeForces 768E(Game of Stones)[公平组合博弈，打表]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/problemset/problem/768/E

仍然枚举前几个sg[x]，找规律
sg[0] = 0、sg[1] = 1;
sg[2] = mex{sg[0], sg[1]’} = mex{0,0} = 1;
—— 这里的sg[1]’表示已经取了一个石子还剩一个石子的状态，很显然不能取！sg[1]’==0
sg[3] = mex{sg[0], sg[1]’, sg[2]’} = mex{0,1,1} = 2;
—— 同上，很好证明sg[2]’==1，sg[1]’==1，不过注意这里的sg[1]’表示已经取了两个石子还剩一个石子的状态，很显然是可以取的，这和上面的sg[1]’不一样，这里sg[1]’==1
sg[4] = mex{sg[0], sg[1]’, sg[2]’, sg[3]’} = mex{0,1,1,mex{0,sg[1]’}} = 2
—— 很显然这里的sg[1]’表示已经取过一个石子也取过两个石子还剩一个石子的状态，很显然不能取，sg[1]’==0
……
最后可得出sg[x] = {0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5……}中秩为x的元素
引用自https://blog.csdn.net/Jaihk662/article/details/56484066

这里复习了下每个结点的SG值是只由它的后继决定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <cstring>
using namespace std;
int sg[70];
int main() {
    int i=0;
    while(i<=62) {
        for(int j=1;j<=62&&i<=62;j++)
        for(int k=1;k<=j&&i<=62;k++)
            sg[i++]=j-1;
    }
    int n;
    scanf("%d",&n);
    int tmp=0,x;
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        tmp^=sg[x];
    }
    printf(tmp?"NO":"YES");
}