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.

巴特西

bzoj 1022 SJ定理

最新文章

热门文章