题解 | 小A取石子

一个Nim的游戏变种题

Nim游戏的一个种类是：有n堆石子，每个人可以拿其中一堆石子的任意数量，不能不拿，而且每一步都是最优考虑，则有一下结论；

• 如果所有石子的异或和为0，则后手必赢
• 如果所有石子的异或和不为0，则先手必赢

那么知道这这个结论之后，本题就是多加了一步（小A可以先拿k个//注意，是必须拿k个或者不拿）穷举判断每一堆石子减去k个之后，是否还为0；

但是纯暴力穷举有可能超时，时间复杂度是O(N²)，所以我就用了psum1[]（前缀异或和），psum2[]（后缀异或和），来记录（因为异或运算符合交换律）；

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	#define int long long
	int n,k;
	cin>>n>>k;
	vector<int> v(n);
	for (auto &i:v)cin>>i;
	
	int ans = v[0];
	for (int i = 1 ; i<n ; i++)ans ^= v[i];
	sort(v.begin(),v.end());//没啥用的排序
	if(ans != 0){
		cout<<"YES"<<endl;
		return 0;
	}//计算异或和，如果符合第一条结论直接输出yes
	
	vector<int> psum1(n,v[0]);
	vector<int> psum2(n,v[n-1]);
	
	for(int i = 1 ; i<n ; i++)psum1[i] ^= psum1[i-1];//前缀和
	for(int i = n-2 ; i>=0 ; i--)psum2[i] ^= psum2[i+1];//后缀和
	
	for (int i = 1 ; i<n-1 ; i++){
		if(v[i] < k)continue;//k要小于等于石子的数量才可以拿
		int res;
		res = psum1[i-1] ^ psum2[i+1] ^ (v[i] - k);//计算减去k之后的和
		if(res != 0){
			cout<<"YES"<<endl;
			return 0;
		}
	}
	
	cout<<"NO"<<endl;//其余情况小B赢
	
	
	return 0;
}
//本蒟蒻是第一次写题解，求dalao放过