POJ1740 A New Stone Game

首先隔空15年orz一波教主。自认为此题的是本蒟蒻做过的博弈题中，除了定理以外，解法及证法最巧妙的一道。题意：对于n堆石子，每堆若干个，两人轮流操作，每次操作分两步，第一步从某堆中去掉至少一个，第二步（可省略）把该堆剩余石子的一部分分给其它的某些堆。最后谁无子可取即输。对于所有的情况，从小到大排序后，都可以归纳为下面3类：#include <iostream>#inclu...

Love_xyh

173人浏览 · 2020-03-16 13:44:17

Love_xyh · 2020-03-16 13:44:17 发布

题意：

对于n堆石子，每堆若干个，两人轮流操作，每次操作分两步，第一步从某堆中去掉至少一个，第二步（可省略）把该堆剩余石子的一部分分给其它的某些堆。最后谁无子可取即输。

思路：

我们发现对于任意一个排列，排序后，如果个数是偶数，且a[1]=a[2]，a[3]=a[4]，…，a[n-1]=a[n]，由于此时，无论先手如何选择，后手均可以做和先手一样的选择，所以这是一个失败状态，而别的情况，均可以转变为这个失败状态，所以都是成功状态。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
int n,ans;
int a[20];
int main(){
	while (true)
	{
		scanf("%d",&n);
		if (!n) break;
		for (register int i=1; i<=n; ++i) scanf("%d",&a[i]);
		if (n&1) {printf("%d\n",1); continue;}
		sort(a+1,a+n+1);
		bool jay=false;
		for (register int i=1; i<n; i+=2) if (a[i]!=a[i+1]) {jay=true; break;}
		if (jay) printf("%d\n",1); else printf("%d\n",0);
	}
return 0;	
}