【bzoj3576】 Hnoi2014

http://www.lydsy.com/JudgeOnline/problem.php?id=3576 (题目链接)

题意

　　给出一个数$F$，然后$n$堆石子，每次操作可以把一堆不少于$F$的石子分成$m$堆，$m$是玩家任选的不少于$2$的正整数，这$m$堆石子中最多的一堆与最少的一堆之差不超过$1$，问是否存在先手必胜。

Solution

　　对每一个子游戏考虑如何求解$SG$函数。

　　假设当前一堆中有$i$石子，我们想把它分成$j$堆，那么石子数为$k=\lfloor{i/j}\rfloor+1$的有$x=i-j*k$堆，石子数为$k$的有$y=i-x$堆。而此时的$SG[i]=[(x\&1)*SG[k+1]]~XOR~[(y\&1)*SG[k]]$。考虑到$k$的取值只有$\sqrt{i}$种，我们可以枚举$j$，那么怎么确定$x,y$的奇偶性呢。$x$的奇偶性只与$j$有关，而一旦$x$确定，$y$就确定了。所以$x,y$的奇偶性只有$2$种情况，分开讨论一下就好了。

代码

// bzoj3576

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<queue>

#define LL long long

#define inf (1ll<<60)

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010;

int T,F,n,SG[maxn],v[maxn];

int main() {

	scanf("%d%d",&T,&F);

	for (int i=0;i<F;i++) SG[i]=0;

	for (int i=F;i<=100000;i++) {

		for (int k,pos,j=2;j<=i;j=pos+1) {

			k=i/j;pos=i/k;

			int x=i-k*j,y=j-x;

			v[((x&1)*SG[k+1])^((y&1)*SG[k])]=i;

			if (j+1<=min(pos,i)) {

				x=i-k*(j+1),y=j+1-x;

				v[((x&1)*SG[k+1])^((y&1)*SG[k])]=i;

			}

		}

		for (int j=0;;j++) if (v[j]!=i) {SG[i]=j;break;}

		//printf("%d ",SG[i]);

	}

	while (T--) {

		scanf("%d",&n);

		int ans=0;

		for (int x,i=1;i<=n;i++) {

			scanf("%d",&x);

			ans^=SG[x];

		}

		printf(ans ? "1" : "0");

		if (T) printf(" ");

	}

	return 0;

}

巴特西

【bzoj3576】 Hnoi2014—江南乐

题意

Solution

代码

最新文章

热门文章