[bzoj] 1022: [SHOI2008]小约翰的游戏John

发表于   |   分类于   |  

题意

有N堆石子，每堆石子有num[i]个，两个人轮流取，可以取任意一堆的任意个，但不能不去，谁取到最后一个谁输，求最后的赢家。

传送门

分析

看到这道题很容易想到谁无法再取谁输的题，典型的Nim问题，而上述的题目是Anti-Nim问题。
在Anti-Nim问题中，先手必胜当且仅当：

  • 所有堆的石子数都为1且游戏的SG值为0；
  • 有些堆的石子数大于1且游戏的SG值不为0。

详见2009年国家集训队论文贾志豪论文
《组合游戏概述——浅谈SG游戏的若干拓展及变形》

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <cstdio>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

inline void reads(int& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

int main() {
int T , flag , SG , x , n ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(T) ;
truewhile (T -- ) {
truetrueread(n) ;
truetrueflag = SG = 0 ;
truetruewhile (n -- ) {
truetruetrueif (read(x) , x > 1) flag = 1 ;
truetruetrueSG ^= x ;
truetrue}
truetrueputs(((flag&&SG)||(!flag&&!SG)) ? "John" : "Brother") ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章