牛客小白月赛13 I题(博弈论)

题目：[链接]

题目描述：

小A也听说了取石子这个游戏，也决定和小B一起来玩这个游戏。总共有n堆石子，双方轮流取石子，每次都可以从任意一堆中取走任意数量的石子，但是不可以不取。规定谁先取完所有的石子就获胜。但是小A实在是太想赢了，所以在游戏开始之前，小A有一次机会，可以趁小B不注意的时候选择其中一堆石子拿走其中的k个，当然小A也可以选择不拿石子。小A先手。双方都会选择最优的策略，请问在这样的情况下小A有没有必胜的策略，如果有输出YES，否则就输出NO。

输入描述：

一行两个整数N,K，表示分别有N堆石子以及小A可以拿走的石子个数k。
接下来N个整数表示每一堆的石子个数 a[i].

输出描述：

一行一个结果表示小A是否有必胜策略，如果有则输出YES，否则输出NO。

输入：

3 2
1 1 1

输出：

YES

备注：

1≤N≤1e5，1≤a[i]≤1e5，0≤K≤1e5

经过分析很容易发现此题是Nim游戏，也是经典的博弈论，关于Nim游戏详解[点这里]，对于此题，先不考虑K，将所有的a[i]异或，如果a[i]的异或值非0，则小A有必胜的策略，否则小B有必胜的策略，此题在于怎样处理K，K的意思就是小A可以比小B多操作一次，可以从任意一堆拿走k个，或选择不拿，所以有两种情况，拿或不拿，对于所有a[i]进行遍历，就看这两种情况，哪一种情况异或值是非零，如果出现非零，则小A必胜，遍历结束，仍未出现非零，则小B必胜.

AC代码如下：

#include<bits/stdc++.h>
typedef long long ll;
const int mod=1e9+7;
using namespace std;
int a[100003];
int main() 
{
	int n,k;
	int sum=0,flag=0;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		sum^=a[i];
	}
	if(sum!=0)flag=1;
	for(int i=0;i<n;i++)
	{
		sum^=a[i];//例如a[0]^a[1]^a[2]=sum,则a[1]^a[2]=sum^a[0]
		if(a[i]>=k)//判断k能不能拿，能拿的话，是否能出现想要的结果
		{
			sum^=(a[i]-k);
			if(sum!=0)flag=1;
		}
	}
	if(flag) puts("YES");
	else puts("NO");
	return 0;
}