[agc010d] Decrementing - 博弈 结论题 -

这题真的不会，不知道正解是怎么想出的 (

首先容易想到当出现一个1的时候，以后的gcd就全是1了，所以后面的操作就只有减1，没有除法。

这个时候，如果轮到i走，还剩奇数轮，他就胜了，反之他就败了。

更具体地，还剩奇数轮等于说是还剩奇数个偶数，所以我们来关注一波奇偶性（偶数的个数记为cnt[0]，奇数的个数记为cnt[1]）。

由于题目保证一开始g=1，所以黑板上至少混入了一个奇数。

至于偶数的个数，我们分两类：

A.有奇数个偶数。

此时先手美滋滋啊，已经处于有利局面，他只要稳住，使得每次轮到他的时候依然还剩奇数个偶数那就稳赢了。

显然可以随手把一个偶数-1，变成奇数。

此时至少有两个奇数了，且cnt[0]由奇数变为了偶数（g此时不可能为偶数，因此(奇数/g)还是奇数，(偶数/g)还是偶数，除法不影响奇偶性）。

轮到后手，他不管怎么搞，

要么把偶数变成奇数，此时先手直接把其它某个偶数也变成奇数（因为cnt[0]>=2，所以肯定可以这样）。

要么把奇数变成偶数，此时先手直接把这个数再变回奇数（因为这个数>=2，所以肯定可以这样）。

这样，又符合了有利条件，一直操作到出现了一个1，先手就稳了。

B.有偶数个偶数。

似乎很容易想到这时是后手必胜。

先手把一个奇数变为偶数或者把一个偶数变为奇数，这样后手面临的局势和A情况一样，他就成了winner。

但是怎么WA了呢？？

仔细检查，原来此时先手把奇数变为偶数后g不一定为奇数了！！这样问题就复杂了，需要我们进一步分类讨论。

如果cnt[1]>=2，那么先手再怎么搞，顶多减掉一个奇数，但还是有奇数幸存下来了，这样g就还是奇数，后手稳赢。

所以只要看cnt[1]=1的情况就可以了。这个时候先手只能寄希望于这个唯一的奇数了，他肯定会怒改奇数，这样g就是偶数了，

局面就会重新变得生机盎然。不管他能不能赢，我们至少看到，这样一来，其实只是将所有数除以g，继续进行和原来类似的子问题，而且后手先手交换了身份，进行新一轮博弈。我们递归下去，直到分出胜负即可。

#include <cstdio>
#define rep(i,j,k) for (i=j;i<=k;i++)
using namespace std;
const int N=1e5+5;
int n,i,ans,a[N],cnt[2];
int gcd(int a,int b) {
	int c=a%b;
	while (c) { a=b; b=c; c=a%b; }
	return b;
}
int solve()
{
	int i,ret,g,pos=0;
	cnt[0]=cnt[1]=0;
	rep(i,1,n) {
		cnt[a[i]%2]++;
		if (a[i]%2 && a[i]>1) pos=i;
	}
	if (cnt[0]%2==0 && cnt[1]==1 && pos) {
		a[pos]--; g=a[1];
		rep(i,2,n) g=gcd(g,a[i]);
		rep(i,1,n) a[i]/=g;
		ret=solve()^1;
	}
	else ret=cnt[0]%2;
	return ret;
}
int main()
{
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]);
	ans=solve();
	if (ans) printf("Firstn");
	else printf("Secondn");
	return 0;
}

最后

以上就是优美飞鸟为你收集整理的[agc010d] Decrementing - 博弈 结论题 -的全部内容，希望文章能够帮你解决[agc010d] Decrementing - 博弈 结论题 -所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。