【SG】分裂游戏

博弈

传送门：BZOJ1188

思路：考虑到每个豆子都是一个独立的游戏，只需求出每个瓶子中一颗豆子的SG值即可；输第一步方案只要取完以后余下的状态先手必败即可。

注意：ans每次要清0。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,ans,tot,cnt,a[30],sg[30],mex[30000];
int main(){
	scanf("%d",&t);
	while (t--){
		scanf("%d",&n);
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		sg[n]=0;
		for (int i=n-1;i>=1;i--){
			cnt++;
			for (int j=i+1;j<=n;j++)
				for (int k=j;k<=n;k++) mex[sg[j]^sg[k]]=cnt;
			for (int j=0;mex[j]==cnt;j++) sg[i]=j+1;
		}
		ans=0; for (int i=1;i<=n;i++) if (a[i]&1) ans^=sg[i];
		tot=0;
		for (int i=1;i<=n;i++)
			if (a[i])
				for (int j=i+1;j<=n;j++)
					for (int k=j;k<=n;k++){
						if (ans^sg[i]^sg[j]^sg[k]) continue;
						if (++tot==1) printf("%d %d %d\n",i-1,j-1,k-1);
					}
		if (!tot) puts("-1 -1 -1");
		printf("%d\n",tot);
	}
	
	return 0;
}