Nim博弈&&POJ1704
2024-10-18 10:15:43
Nim博弈
题目
有n堆物品,两人轮流取,每次取某堆中不少于1个,先取完者胜。
分析
经典问题,该问题的策略也成为了许多问题的基础。
要判断游戏的胜负只需要异或运算就可以了,有以下结论:
- $a_1 \ xor \ a_2\ xor ... \ xor a_n \neq 0$,必胜态
- $a_1 \ xor \ a_2\ xor ... \ xor a_n = 0$,必败态
为什么是异或运算呢?
//下面这段话为口胡
异或运算能保证必败态只能转移到必胜态,也就是说,当异或和为0时,从某一堆中任取至少一颗石子,异或和就一定会变成非0;
另一方面,异或运算能保证从必胜态一定可转移到必败态,也就是说,当异或和不为0时,可从某一堆中选取合适的石子(至少一个),使得异或和变成0。
应用
问题:一个排成线的格子上放有 $n$ 个棋子,棋子 $i$ 放在左数第 $p_i$ 个格子上。两人轮流选择一个棋子向左移动,每次至少移动一格,但是不允许反超其他的格子,也不允许将两个棋子放在同一个格子内。无法进行操作的一方失败。若两人都采取最优策略,谁会赢?
分析:如果将棋子两两成对当作整体考虑,我们就可以把这个游戏转成Nim游戏。
首先,考虑棋子数为偶数,我们可以两两成对,石子堆中石子的个数就等于两个石子中的间隔。如果间隔们的异或和为0,则先手移动右边的石子,后手根据Nim的策略一定能通过移动右边的石子保持异或和为0;同理,如果异或和不为0,跟Nim异或和不为0一样。除此之外,可发现,移动左边的石子是没有意义的,因为对手会跟着移。
奇数时补充一个形成偶数个。
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn = + ;
int n, a[maxn]; int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = ;i < n;i++) scanf("%d", &a[i]);
if(n&) a[n++] = ;
sort(a, a+n);
int res = ;
for(int i = ;i < n-;i+=) res ^= (a[i+] - a[i] - );
if(res == ) printf("Bob will win\n");
else printf("Georgia will win\n");
}
}
最新文章
- 利用googleapis在日文系统中改善中文字
- 【转】c# 调用windows API(user32.dll)
- Linux基础--分类与合并命令
- C++类型转换总结 转
- 微软MSBI商业智能视频
- chrome谷歌浏览器-DevTool开发者工具-详细总结
- 【Java编程】Java中的大整数计算
- 原生JS封装 toast 弹层,自动关闭
- linx下对文件权限设置
- pythone函数基础(12)连接Redis,写数据,读数据,修改数据
- 缓存日志截取字段上传FTP
- 深入理解Java的堆内存和线程内存
- leetcode54
- [python]缓存函数结果进redis
- jvm 性能调优 经验总结---转
- HDU 1866 A + B forever!
- iOS开发之CocoaAsyncSocket学习
- 理解Call、Apply、bind
- flash8中利用遮罩制作图片切换效果
- springMVC从前端接受boolean类型的属性失败的问题