bzoj 1022 SJ定理

时间:2023-03-10 07:17:39
bzoj 1022 SJ定理

  与传统的SG游戏不同的是,完成最后一个状态的人是输的,我们把这一类问题称作Anti-SG,这类问题的解决我们需要引入一个定理—SJ定理:

  对于任意一个Anti-SG游戏,如果我们规定当局面中所有的单一游戏的SG值为0时,游戏结束,则先手必胜当且仅当:(1)游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1;(2)游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。         (引自2009年国家集训队论文贾志豪论文《组合游戏概述——浅谈SG游戏的若干拓展及变形》)

  这样对于这个问题我们就可以很好的解决了:

  1、所有堆的石子数都为1且游戏的SG值为0;

  2、有些堆的石子数大于1且游戏的SG值不为0。

  只有这两种请情况下是先手必胜状态,否则为先手必败状态。

/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ //By BLADEVIL
var
task :longint;
i :longint;
n :longint;
a :array[..] of longint; procedure main;
var
i :longint;
ans :longint;
f :boolean;
begin
read(n);
ans:=;
for i:= to n do read(a[i]);
for i:= to n do ans:=ans xor a[i];
f:=false;
if ans= then
begin
for i:= to n do if a[i]<> then f:=true;
end else
for i:= to n do if a[i]> then f:=true;
if (ans=) and (not f) or (ans<>) and (f) then writeln('John') else writeln('Brother');
end; begin
read(task);
for i:= to task do main;
end.