容易发现所有豆子相互独立, 只需要考虑每一个豆子的 sg 函数并异或起来即可, sg 函数从后往前暴力即可
- #include<bits/stdc++.h>
- using namespace std;
- int t,n,x,y,z,s,ans,a[105],sg[105],vis[105];
- int main(){
- scanf("%d",&t);
- while (t--){
- scanf("%d",&n);
- for(int i=1;i<=n;i++)scanf("%d",&a[i]);
- memset(sg,0,sizeof(sg));
- x=y=z=s=ans=0;
- for(int i=n;i;i--){
- memset(vis,0,sizeof(vis));
- for(int j=i+1;j<=n;j++)
- for(int k=j;k<=n;k++)vis[sg[j]^sg[k]]=1;
- while (vis[sg[i]])sg[i]++;
- if (a[i]&1)s^=sg[i];
- }
- 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 ((s==(sg[i]^sg[j]^sg[k]))&&(!ans++))printf("%d %d %d\n",i-1,j-1,k-1);
- if (!ans)printf("-1 -1 -1\n");
- printf("%d\n",ans);
- }
- }
- View Code
[bzoj1188] 分裂游戏
来源: http://www.bubuko.com/infodetail-3282601.html