欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

83-取石子-尼姆博弈

程序员文章站 2022-06-29 21:11:28
...

 

C时间限制:3000 毫秒 |  C内存限制:3000 Kb
题目内容:
 m堆石子,甲乙两人轮流取,每次需先选择1堆,并取任意数目的石子. 最后取完者的获胜.
规定甲先取。
输入描述
可能有多组测试数据。每组的第一行是m, 第二行是m个整数,表示每堆石子的数目。
输出描述
每个测试用例,甲失败则输出“No”。
否则输出"Yes", 并在下面的行输出取法。
    按堆号顺序输出各种甲能取胜的首次取法a,b,表示在第a堆石子中取完石子后剩下b个,甲可以获胜。
输入样例
2
45 45
3
3 6 9
5
5 7 8 9 10
输出样例
No
Yes
9 5
Yes
8 1
9 0
10 3

83-取石子-尼姆博弈

83-取石子-尼姆博弈

83-取石子-尼姆博弈

其实就是看你能不能保证让异或后为零,可以理解为异或为零了,就可以保证别人怎么取,你就怎么取,让别人输。

如果开始异或不为零,你就可以赢,同时取走k个保证之后异或为零,取走多少呢,就是保证之后异或为零,既可以找一个 ni 使其和 k 异或,得到 n,(保证ni大于n)

这样,相当于从ni中取走了ni - n 个石子。

#include <iostream>
using namespace std;
int a[100005];

int main(){
	int n;
	while(cin >> n){
		int ans;
		cin >> ans;
		for(int i = 0; i < n - 1; i++){
			cin >> a[i];
			ans = ans ^ a[i];    
		}
		if(ans == 0){
			cout << "No" << endl;
		}	
		else{
			cout << "Yes" << endl;
			for(int i = 0; i < n; i++){
				int ni = a[i] ^ ans;  //剩余Ni个 
				if(ni <= a[i]){       //保证ni小于等于原有的个数 
					cout << a[i] << " " << ni << endl;
				}
			}
		}
	}
	return 0;
}