Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:详细的算法与解题报告:

Posted by LittleWhiteMouse at 2010-04-09 18:08:14 on Problem 3480
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator