【一道经常出现解答却不详细的题...】
2014-02-27 19:22:51| 分类：
数学
| 标签：
|举报
|字号大中小 订阅
一开始在noip吧看到的，貌似以前看博弈的时候也看过，可是却没有仔细想了...发现那个分析的确不是很详细，所以自己想想然后把想法写下来。
翻棋子游戏：
题意：一个棋盘上每个格子有一个棋子，每次操作可以随便选一个朝上的棋子(x,y)，代表第x行第y列的棋子，选择一个形
如(x,b)或(a,y)(其中b < y，a < x)的棋子，然后把它和(x,y)一起翻转，无法操作的人输。
实际上最后的结局就是只剩下（1,1）有个正面朝上的棋子或者没有棋子正面朝上了....
先来考虑NIM游戏，假设NIM和是必胜态，那么就取些石子让异或和为0进入必败态即可，如果是必败态，得保证无论如何都会取到必胜态。
我们把每一个朝上的坐标（x,y）看做两堆石子，一堆x个，一堆y个，每一次选择一个坐标（x,y）翻下去，再新选一个坐标（a,y）或者（x,b）翻过来。这里有两种情况：
1）新选的坐标 之前是背面朝上的，这个实际上就是 把 x的石子堆 或 y的石子堆拿去一些，比如 (a,y)就是把 X个石子的石子堆变成a个石子的石子堆。
2）新选的坐标 之前是正面朝上的，设之为 (a,y) （（x,b）的情况类似）那么我们实际上就失去了石子数为 a 的 石子数为 x 的，石子数为 y 的，石子数为 y 的石子堆，后面两个同时去掉对nim游戏的xor和无影响，相当于没去掉，关键在于前面两个，它们去掉在NIM的计算中实际上就相当于 乘以 a xor x 的石子，由于 a<x ，所以 a xor x<x，实际上这也就相当于将x个石子的石子堆变成a个石子的石子堆（X个石子的石子堆变成a个石子的石子堆，异或和的变化为 a xor x)
所以以上两种情况下都满足NIM游戏，所以就OK了。
评论这张
转发至微博
转发至微博
关闭
玩LOFTER，免费冲印20张照片，人人有奖！
我要抢>
<#--最新日志，群博日志-->
<#--推荐日志-->
<#--引用记录-->
<#--博主推荐-->
<#--随机阅读-->
<#--首页推荐-->
<#--历史上的今天-->
<#--被推荐日志-->
<#--上一篇，下一篇-->
<#-- 热度 -->
<#-- 网易新闻广告 -->
<#--右边模块结构-->
<#--评论模块结构-->
<#--引用模块结构-->
<#--博主发起的投票-->
评论