博弈论

Qiansui / 2023-05-07 / 原文

基础概念

相关参考资料：易老师整理（放个大佬的链接）

Nim Game

题目：有n堆石子，数量分别为\(a_1,a_2,...,a_n\)，两个玩家均足够聪明，轮流拿石子，每次仅可以从任意一堆中拿走任意数量的石子。
结论：当\(a_1⊕a_2⊕...⊕a_n≠0\)时，先手必胜；否则先手必败。
而且，令\(a_1⊕a_2⊕...⊕a_n=x\)，则定有一个数\(a_i\)，有\(a_i⊕x<a_i\)，则先手仅需将第i堆石子取走\(a_i-a_i⊕x\)个，第i堆留下\(a_i⊕x\)，则此时所有堆的异或为0，下一后手面对必败局面。

线上题目

暑假博弈论专题训练
Mingming's Nim
Nim游戏模板

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

const int maxm = 1e2+10;
typedef long long LL;
int n,s[maxm];

void out(int a,int b){
	cout<<a<<" "<<b<<endl;
	return ;
}

void solve(){
	cin>>n;
	int rr=0,c,a,b,t;
	for(int i=1;i<=n;++i){
		cin>>s[i];
		rr^=s[i];
	}
	if(rr==0){
		cout<<"2"<<endl;
		cin>>a>>b;
		rr^=s[a];
		s[a]-=b;
		rr^=s[a];
	}
	else{
		cout<<"1"<<endl;
	}
	while(1){
		for(int i=1;i<=n;++i){
			if((s[i]^rr)<s[i]){
				out(i,s[i]-(s[i]^rr));
				t=s[i];
				s[i]=s[i]^rr;
				rr^=t;
				rr^=s[i];
				break;
			}
		}
		cin>>c;
		if(c==0) return ;
		else if(c==-1){
			cout<<"0 0"<<endl;
			return ;
		}
		cin>>a>>b;
		rr^=s[a];
		s[a]-=b;
		rr^=s[a];
	}
	return ;
}

int main()
{
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}