| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:详细的算法与解题报告:In Reply To:详细的算法与解题报告: Posted by:IceKingdom at 2009-07-15 18:43:45 > 这是一个 Anti-SG 问题,可以用 2009 年中国信息学竞赛国家集训队队员 贾志豪 神牛的 SJ (Sprague Grundy - Jia Zhihao) 定理来求解。
> 首先 Anti-SG 游戏是:
> 1 决策集合为空的游戏者获胜
> 2 其他规则与 SG 游戏相同。
> SJ 定理是:
> 对于任意的一个 Anti-SG 游戏,如果我们规定当局面中所有单一游戏的 SG 值为 0 时游戏结束,则先手必胜当且仅当以下两个条件满足任意一个:
> (1)游戏的 SG 函数不为 0,且游戏中某个单一游戏的 SG 函数大于 1
> (2)游戏的 SG 函数为 0,且游戏中没有单一游戏的 SG 函数大于 1。
>
> 我应用 SJ 定理解出了此题,下面是我的 Pascal 代码:
> program John ;
> var n , i , j , testi , ans , max
> : longint ;
>
> begin
> readln (testi) ;
> for testi := 1 to testi do begin
> readln (n) ; ans := 0 ; max := 0 ;
> for i := 1 to n do begin
> read (j) ; if (j > max) then max := j ;
> ans := ans xor j ;
> end ;
> if (ans <> 0) and (max > 1) or
> (ans = 0) and (max <= 1) then
> writeln ('John')
> else
> writeln ('Brother') ;
> end ;
> end .
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator