首页 > 其他 > 详细

BZOJ 1022

时间:2018-03-06 12:19:56      阅读:194      评论:0      收藏:0      [点我收藏+]

Anti-Nim

首先要看清楚题,最后一个拿到的人算输,所以本题是 Anti - Nim

Anti - Nim 有如下规律:
1.当每堆石子都只有一个的时候, SG = 0 先手必胜
2.当存在不只有一个的石子的时候, SG != 0 时 先手必胜

证明:

第一条显然

第二条,当只有一堆石子多于一个的时候,先手总可以选择把这一堆拿成 1 个或 0 个,从而变成 1
当有多堆石子的时候, 等价于两堆多于一个,剩下的只有一个的石子堆如果是奇数 ,等价为一个,偶数等价为 0 个
如果SG值不为 0 ,先手总可以操控使对方拿到最后一个:
分别考虑有没有多出的一个石子

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int T, n, num[1000];
int main() {
    cin>>T;
    while(T--) {
        cin>>n;
        int ans = 0;
        bool f = 0;
        for(int i = 1; i <= n ; i++) {
            cin>>num[i];
            if(num[i] != 1) {
                f = 1;
            }
            ans ^= num[i];
        }
        if(!f){
            if(n & 1) printf("Brother\n");
            else printf("John\n");
        }else {
            if(ans) printf("John\n");
            else printf("Brother\n");
        }
    }
    return 0;
}

BZOJ 1022

原文:https://www.cnblogs.com/Mr-WolframsMgcBox/p/8513637.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!