bzoj1022: [SHOI2008]小约翰的游戏John

Description

小约翰经常和他的哥哥玩一个非常有趣的游戏: 桌子上有 n 堆石子, 小约翰和他的哥哥轮流取石子, 每个人取的时候, 可以随意选择一堆石子, 在这堆石子中取走任意多的石子, 但不能一粒石子也不取, 我们规定取到最后一粒石子的人算输. 小约翰相当固执, 他坚持认为先取的人有很大的优势, 所以他总是先取石子, 而他的哥哥就聪明多了, 他从来没有在游戏中犯过错误. 小约翰一怒之前请你来做他的参谋. 自然, 你应该先写一个程序, 预测一下谁将获得游戏的胜利.

Input

本题的输入由多组数据组成第一行包括一个整数 T, 表示输入总共有 T 组数据 (T≤500). 每组数据的第一行包括一个整数 N (N≤50), 表示共有 N 堆石子, 接下来有 N 个不超过 5000 的整数, 分别表示每堆石子的数目.

Output

每组数据的输出占一行, 每行输出一个单词. 如果约翰能赢得比赛, 则输出 “John”, 否则输出 “Brother”, 请注意单词的大小写.

Sample Input

2
3
3 5 1
1
1

Sample Output

John
Brother

HINT

Source

Seerc2007

原文地址:http://dzy493941464.is-programmer.com/posts/39629.html

题目 1: 有 n 堆石子, 第 i 堆有 A (i) 颗石子. 两人依次从中拿取, 规定每次只能从一堆中取若干根, 可将一堆全取走, 但不可不取, 最后取完者为胜, 求必胜的方法. 令 C=A (1) xor A (2) xor A (3) xor...... xor A (n), 若 C>0, 则记为利己态, 用 S 表示, 若 C=0, 则记为利他态, 用 T 表示.

【定理 1】对于一个 S 态, 一定能从一堆石子中取出若干个, 使其成为 T 态.

【证明】既然是 S 态, 则此时 C>0, 我们要使得 C 变为 0.

设 C 转化为二进制后, 最高位的 1 是第 p 位. 那么一定存在一个 A (t) 的二进制最高位的 1 是第 p 位. (显然, 不然 C 的第 p 位不可能是 1)

然后, 把第 t 堆石子的个数变为 x=A (t) xor C. 因为 A (t) 和 C 的二进制最高位的 1 是同一位. 那么异或之后这一位就变成了 0. 那么 x 一定小于 A (t).

此时的 C ‘=A (1) xor A (2) xor...... xor A (t) xor C xor A (t+1) xor...... xor A (n). 把 C 带进去, 得到

C’=A (1) xor A (2) xor...... xor A (n) xor A (1) xor A (2) xor...... xor A (n). 显然 C ‘=0.

所以, 只要在第 t 堆石子中取出 A (t)-x 颗石子, 就把 S 态变为了 T 态.

【定理 2】对于一个 T 态, 从任意一堆取任意个石子出来, 都会变为 S 态.

【证明】用反证法. 设此时第 i 堆的石子数变成了 A (i’) . 此时 C=0. 如果 C ‘>0, 那么命题就成立了.

假设 C’=0. 则 C ‘=A (1) xor A (2) xor...... xor A (i’) xor...... xor A (n)=0.

因为 C=0. 所以 C xor C ‘=0. 则 A (1) xor A (2) xor...... xor A (i) xor...... xor A (n) xor A (1) xor A (2) xor...... xor A (i’) xor...... xor A (n)=0.

A (i) xor A (i ‘)=0. A (i)=A (i’) 明显不对了. 所以命题得证.

得到了这两个定理之后, 我们可以发现, 任何一个 S 态, 我们都可以通过自己的控制将它转化成 T 态. 而对方怎么做都是将 T 态再转回 S 态, 很被动. 所以只要先手是 S 态, 总是可以根据定理 1 得到的策略获胜.

题目 2: 有 n 堆石子, 第 i 堆有 A (i) 颗石子. 两人依次从中拿取, 规定每次只能从一堆中取若干根, 可将一堆全取走, 但不可不取, 最后取完者为负, 求必胜的方法.

再来定义几个状态. 一堆石子里只有一个石子, 记为孤单堆. 否则记为充裕堆.

在 T 态中, 如果充裕堆的个数大于等于 2, 记为 T2 态, 1 个充裕堆, 记为 T1 态, 没有充裕堆, 记为 T0 态. S0、S1、S2 同理.

【定理 3】在 S0 态中, 若孤单堆的个数为奇数. 那必输. T0 态必赢.

【证明】也就是奇数个石子, 每次取一个. 很明显先去的人必输.

【定理 4】在 S1 态中, 方法正确就必胜.

【证明】如果孤单堆的个数是奇数, 那么就把充裕堆取完; 如果是偶数, 就把充裕堆取的只剩 1 根. 这样留下的就是奇数个孤单堆, 对方先手. 由定理 3 得, 对方必输, 己方必胜.

【定理 5】S2 态不可一次变为 T0 态.

【证明】显然, 充裕堆不可能一次从 2 堆以上变为 0.

【定理 6】S2 态可一次变为 T2 态.

【证明】由定理 1 得 S 态可以一次变为 T 态, 而且不会一次取完整堆, 那么充裕堆的个数是不会变的, 由定理 5 得 S2 态不能一次变为 T0 态, 那么转化的 T 态是 T2 态.

【定理 7】T2 态只能转变为 S1 或 S2 态.

【证明】由定理 2 得, T 态一次只能变为 S 态. 由于充裕堆数不会变为 0. 所以是 S1 或 S2 态.

【定理 8】在 S2 态中, 只要方法正确, 就必胜.

【证明】由定理 6 得, 先转化为 T2 态. 由定理 7, 对方只能再转化回 S1 或 S2 态. 由定理 4, 己方必胜.

【定理 9】T2 态必输.

【证明】同证明 8.

我们得到了几个必胜态: S2, S1, T0. 必输态: T2, T1, S0.

比较一下两题:

第一题的过程: S2-T2-S2-T2-...... -T2-S1-T0-S0-T0-...... -S0-T0 (全 0)

第二题的过程: S2-T2-S2-T2-...... -T2-S1-S0-T0-S0-...... -S0-T0 (全 0)

我们可以发现前面的过程是一样的. 关键在于得到了 S1 态之后, 怎样抉择使自己获胜. 而这个是自己可以掌握的.

因此, 我们只需要把 T2 态留给对方, 迟早他会转化成 S1 态. 己方就必胜.

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int t, n;
int main(int argc, char** argv)
{
    scanf("%d", &t);
    do {
        scanf("%d", &n);
        int xor_sum = 0, non_single_piles = 0;
        int tmp = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &tmp);
            xor_sum ^= tmp;
            if (tmp > 1) non_single_piles++;
        }
        if ((xor_sum > 0 && non_single_piles > 0)
                || (xor_sum == 0 && non_single_piles == 0))
            printf("John\n");
        else
            printf("Brother\n");
    } while (--t);
    return 0;
}

from pydatagen import *
t = randrange(100, 500)
printf('%d\n' % t)
for i in range(1, t):
    n = randrange(30, 50)
    printf('%d\n' % n)
    l = randlist(n, range(0, 5000))
    print_oi(l)
fclose()