| ||||||||||
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 |
对称博弈写点感想吧, 记得刚进高中的时候, 物理老师就举了一个例子,大概是这样的: 有个棋盘,两个棋手交错走棋,没有其他规则,就只是占领棋格,请问谁会赢(占的格子多)? 答案是先手赢。 如何证明? 先手一来就占领棋盘的正中, 然后不管后手如何走, 他都走与之呈点对称的位置,最后一定是先手多一个格。 直观来讲,也是先手赢,但并不严谨。通过对称这一思路,在这里就起作用了。 回到此题,说说大概的思路:当n>=3时,无论A如何选择,B选择一个特殊的位置(1个或者连续2个)正好把剩下的环路分成两个链路,大小相同。 接下来,无论A选择两个链路中哪一个,进行何种操作,B只需要选择另一个链路中,进行相同的操作。剩下的系统,仍是对称的。 直到最后,B肯定是最后一个进行操作的。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator