P3185 [HNOI2007] 分裂游戏
题目描述
聪聪和睿睿最近迷上了一款叫做分裂的游戏。
该游戏的规则是： 共有 \(n\) 个瓶子， 标号为 \(0, 1, \ldots, n-1\)，第 \(i\) 个瓶子中装有 \(p_i\) 颗巧克力豆，两个人轮流取豆子，每一轮每人选择 \(3\) 个瓶子，标号为 \(i,j,k\), 并要保证 \(i \lt j, j \leq k\)，且第 \(i\) 个瓶子中至少要有 \(1\) 颗巧克力豆，随后这个人从第 \(i\) 个瓶子中拿走一颗豆子并在 \(j,k\) 中各放入一粒豆子（\(j\) 可能等于 \(k\)） 。如果轮到某人而他无法按规则取豆子，那么他将输掉比赛。胜利者可以拿走所有的巧克力豆！
两人最后决定由聪聪先取豆子，为了能够得到最终的巧克力豆，聪聪自然希望赢得比赛。他思考了一下，发现在有的情况下，先拿的人一定有办法取胜，但是他不知道对于其他情况是否有必胜策略，更不知道第一步该如何取。他决定偷偷请教聪明的你，希望你能告诉他，在给定每个瓶子中的最初豆子数后是否能让自己得到所有巧克力豆，他还希望你告诉他第一步该如何取，并且为了必胜，第一步有多少种取法？
\(1 \leq t \leq 10\)，\(2 \leq n \leq 21\)，\(0 \leq p_i \leq 10^4\)，
思路
首先，需要注意到，每颗巧克力豆互不相关。也就是说，可以将当前盘面分为每颗巧克力豆的子盘面。
对于每颗巧克力豆，其标志只有位置。因此，只需要算出每个位置的巧克力豆的sg值即可。
直接根据定义，枚举后继局面，即当前巧克力豆转移后的位置，暴力计算、预处理出sg值。
然后对于每次询问，暴力枚举所有可能的转移，转移后sg为零就是合法的操作。
复杂度 \(O(tn^3)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int N=25,inf=1e9;int read(){int ans=0;char c=getchar();bool f=0;for(;!isdigit(c);c=getchar())if(c=='-')f=1;for(;isdigit(c);c=getchar())ans=(ans<<=1)+(ans<<2)+(c^48);return f?-ans:ans;
}void print(int x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10|48);
}int n,sg[N],a[N];
bool vis[N];void init(){int n=21;sg[1]=0;for(int i=2;i<=n;++i){for(int j=1;j<i;++j){for(int k=j;k<i;++k){vis[sg[j]^sg[k]]=1;}}while(vis[sg[i]])++sg[i];for(int j=0;j<=n;++j)vis[j]=0;}
}signed main(){init();int T=read();while(T--){int n=read(),s=0;for(int i=1;i<=n;++i){a[i]=read();if(a[i]&1)s^=sg[n-i+1];}int cnt=0,ai,aj,ak;for(int i=1;i<n;++i){if(!a[i])continue;for(int j=i+1;j<=n;++j){for(int k=j;k<=n;++k){if((s^sg[n-i+1]^sg[n-j+1]^sg[n-k+1])==0){++cnt;if(cnt==1)ai=i,aj=j,ak=k;}}}}if(!cnt){puts("-1 -1 -1\n0");}else {printf("%d %d %d\n%d\n",ai-1,aj-1,ak-1,cnt);}}return 0;
}