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