![](https://csdnimg.cn/release/download_crawler_static/3797304/bg4.jpg)
果。 xor 的运算率有结合率,交换率。除此以外,若 a xor b = c 则 a xor d = c 当且仅当 b = c
;
a
xor a = 0 ; a xor 0 = a ;
令 b =G
1
(X
1
) xor … … G
n
(X
n
) ,则只需证明 :
1)
于任意 a
a
a
a
∈ N 且 a
a
a
a
<
<
<
<
b
b
b
b
, 一定 存在 X
X
X
X
’ ∈ F
F
F
F
(
(
(
(
X
X
X
X
)
)
)
)
使 G(X
G(X
G(X
G(X
’ )
)
)
)
=
=
=
=
a
a
a
a
。
2) 对于任意 X
X
X
X
’ ∈ F
F
F
F
(
(
(
(
X
X
X
X
)
)
)
)
, 那么有 G
G
G
G
(
(
(
(
X
X
X
X
’ )
)
)
)
≠
≠
≠
≠
b
b
b
b
。
证明1 ) :
令 d = a xor b ,令 d 的 2 二进制位数为 k 。必然存在 i 使 G
i
(X
i
) 的二进制第k位为1。 显
然 G
i
(X
i
) xor d < G
i
(X
i
) , 因此存在 X
i
’ ∈ F
i
( X
i
) 使 G
i
(X
i
’ ) =G
i
(X
i
) xor d 。
b * d = a => a = G
1
(X
1
) xor … … G
i
(X
i
) xor d … … G
n
(X
n
)= G(X
1
… … X
i
’
,
… …
,
X
n
)
因为 (X
1
… … X
i
' … … X
n
) ∈ F(X) 。 所以 1 ) 得证。
证明2 ) :
假设2 ) 不成立,即对于一个任意的 X 存在 X
'
∈ F(X) 使 G(X
'
)= b。那么令 X ’ =(X
1
,
…
…
,
X
i
’ , … …
,
X
n
)
,
G(X ’ )=G
1
(X
1
) xor … … G
i
(X
i
’ ) … … G
n
(X
n
)= b
。 因此
G
i
(X
i
’ )=G
i
(X
i
)
与 SG 函数的定义矛盾,2 ) 得证。
由于在证明中用到了自身,因此需要用数学归纳法。
看,并不是所有的时候 SG 函数都比必败状态难求吧。 将一个游戏分解,就是将它看 作
数个游戏的和, 利用对每一个单独游戏分析的结果来研究整个游戏。 几乎所有的子游戏都 比
游戏的和要简单,因此在面对大多数复杂的游戏之和时,用分解的方法,所有问题都能迎 刃
而解。
用分解的方法来分析组合游戏
例题1 :
ACM ICPC 2006 Asia Regional Contest,Beijing
A Funny Stone Game
David 玩一个石子游戏。游戏中,有 n 堆石子 , 被编号为 0..n-1 。两名玩家轮流取石子
。
每一轮游戏, 每名玩家选取 3 堆石子 i,j,k(i<j,j<=k, 且至少有一枚石子在第 i 堆石子中 )
,
从 i 中取出一枚石子,并向 j , k 中各放入一枚石子 ( 如果 j=k 则向 k 中放入 2 颗石子 ) 。最
先不能取石子的人输。
请编程帮助 David 。
石子堆的个数不会超过 23 ,每一堆石子不超过 1000 个。
输入:
输入包含多组数据,每组数据由 2 行构成,第一行为一个整数 n ,第二行包含 n 个整
数 S0..Sn-1 表示每一堆石子的个数。输入以包含一个 0 的一行结束。
输出:
每组数据的输出依次各占一行。输出格式为 “ Game t: i j k
”
,t 为数据的序号, i,j, k
表示一个保证 David 能获胜的开局。如果有多种方案,输出字典顺序最小的一组,如果没 有
这样的方案, i 、 j 、 k 、均为 -1 。
分析: