题解 P3185 【[HNOI2007]分裂游戏】

· · 题解

题意

有n个格子,标号为0 ~ n-1,每个格子上有若干石子,每次操作可以选一个0 ~ n-2的格子上的一颗石子,分裂为两颗,然后任意放在后面的两个格子内,这两个格子可以相同.求使先手必胜的第一步的方案数以及最小字典序的方案.

分析

每一个石子都是独立的,所以考虑某一位上的一颗石子的SG函数,再异或起来就行了.实际上只用异或石子数为奇数的,因为偶数个石子异或两次相当于没有异或.

我们先把位置反向并从1~n标号,也就是最后边是1,最左边是n.这样就能对不同的n用同样的SG函数

那么对于位置i,它的SG函数如下:

SG[i]=mex\{\ \cup_{i>j>=k}SG[j]\ xor\ SG[k] \ \}

所以说直接预处理就行了

求方案的时候,注意字典序最小反序后就是字典序最大,所以要从大到小枚举

CODE

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>void read(T &num) {
    char ch; int flg=1;
    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
    num*=flg;
}
const int MAXN = 22;
int SG[MAXN], n, A[MAXN], vis[50]; //vis要开大点,SG函数会超过n
inline void Pre() {
    SG[1] = 0;
    for(int i = 2; i < MAXN; ++i) {
        for(int j = 1; j < i; ++j)
            for(int k = j; k < i; ++k)
                vis[SG[j]^SG[k]] = i;
        for(SG[i] = 0; vis[SG[i]] == i; ++SG[i]);
    }
}
inline void solve(int ans) {
    int res = 0, ans1 = -1, ans2, ans3;
    for(int i = n; i > 1; --i)
        for(int j = i-1; j > 0; --j)
            for(int k = j; k > 0; --k)
                if((ans^SG[i]^SG[j]^SG[k]) == 0) {
                    ++res;
                    if(!(~ans1))
                        ans1 = n-i, ans2 = n-j, ans3 = n-k;
                }
    printf("%d %d %d\n%d\n", ans1, ans2, ans3, res);
}
int main() {
    int T; read(T); Pre();
    while(T--) {
        read(n);
        int ans = 0;
        for(int i = n; i > 0; --i) {
            read(A[i]);
            if(A[i]&1) ans ^= SG[i];
        }
        if(!ans) printf("-1 -1 -1\n0\n");
        else solve(ans);
    }
}