Nim博弈（博弈论）

106 阅读 0 评论 70 点赞

我是靠谱客的博主简单钢笔，最近开发中收集的这篇文章主要介绍Nim博弈（博弈论），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.https://www.acwing.com/problem/content/893/
题目：给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。
思路：
必胜状态(a1^ a2 …^an!=0)：可以走到某一个必败状态
必败状态(a1^ a2 …^an==0)：走不到任何一个必败状态
证明(参考算法进阶指南)：

(a1^ a2 …^an!=0)可以走到某一个必败状态
(a1^ a2 …^an==0)走不到任何一个必败状态

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		ans^=x;
	}
	if(ans) printf("Yesn");
	else printf("Non");
 }