P3185 [HNOI2007]分裂游戏 题解
c20210623
·
·
题解
题目链接：P3185 [HNOI2007]分裂游戏
把每一颗豆子看作一个子游戏。显而易见，
另外几颗豆子的状态不影响该豆子的结果。
因此我们可以对每一颗豆子分别当成一个游戏求 \text{sg} 函数。
对于每一个瓶子的豆子而言，有n颗豆子等价于有\text{n+2} 颗豆子。
因为若此时对手从 \text{a} 瓶子取 \text{1} 颗到 \text{b} 瓶子和 \text{c} 瓶子，
对手只需模仿操作一次即可复原状态。
因此凡一个瓶子有偶数颗豆子，等价于有 \text{0} 颗豆子，
我们可以直接跳过不考虑。有奇数颗豆子，
我们就直接认为该瓶子只有 \text{1} 颗豆子。
此时我们就可以自然的定义 \text{sg} 数组了。
设 \text{sg[i]} 为考虑第 \text{n-i+1} 个瓶子有 \text{1} 颗豆子时的 \text{sg} 函数。
（为了使 \text{n} 不同时的 \text{sg} 函数边界相同，必须倒着定义。）
对于任何个 \text{sg[i]} 的下一个状态
下面就是模板了。代码如下：
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
int T,n,sg[25],a[25];
int init(int n){//预处理sg[n]
bool vis[105]={};
if(sg[n]!=-1) return sg[n];//记忆化
if(n==1) return sg[1]=0;//边界
for(int i=1;i<n;i++){
for(int j=1;j<=i;j++) vis[init(i)^init(j)]=1;//下一个状态：sg[i][j]
}
for(int i=0;;i++) if(!vis[i]) return sg[n]=i;
}
int main(){
scanf("%d",&T);
memset(sg,-1,sizeof(sg));
for(int i=1;i<=21;i++)
if(sg[i]==-1) init(i);//预处理sg函数。
while(T--){
scanf("%d",&n);
int ans=0,ans1=0,vi=0,vj=0,vk=0;//ans就是最终问题的sg值 ans1为满足情况的总数
//vi,vj,vk先都赋为0，-1即为最终答案，这样就可以不分类讨论。
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]&1) ans^=sg[n-i+1];//只有i%2==1的情况是一个子问题。
}
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
for(int k=j;k<=n;k++){
if(!(ans^sg[n-i+1]^sg[n-j+1]^sg[n-k+1])){
if(vi==0) vi=i,vj=j,vk=k;
ans1++;
}
}
}
}
printf("%d %d %d\n%d\n",vi-1,vj-1,vk-1,ans1);
}
return 0;
}
```