BZOJ1115 [POI2009]KAM-Pebbles

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

阶梯$Nim$

对于这种游戏，必胜策略就是只要你把x颗石子从偶数层拿到奇数层，那我就把这x颗石子拿到偶数层。

若我们从$i$处取走了$x$个石子，那么下一次及以后就可以在$i+1$处多取$x$个，相当于把$i$处的$x$个石子加到了$i+1$处 ，所以可以转化成阶梯$Nim$

不懂可以看一下https://blog.csdn.net/kk303/article/details/6692506

代码:

点击显示代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#define N 1000
int T, n, a[N+5];
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        int ans = 0;
        for(int i = n; i >= 1; i -= 2)
            ans ^= (a[i]-a[i-1]);
        if(ans)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}