P3185

· · 题解

今天刚学博弈论，在其他 OJ 遇到了这道题，调了一个多小时终于做出来了，发题解纪念一下。

题目大意

游戏的规则是： 共有 n 个瓶子， 标号为 0,1,2…..n-1, 第 i 个瓶子中装有 p_i 颗巧克力豆，两个人轮流取豆子，每一轮每人选择 3 个瓶子。标号为 i,j,k, 并要保证 i < j , j \le k 且第 i 个瓶子中至少要有 1 颗巧克力豆，随后这个人从第 i 个瓶子中拿走一颗豆子并在 j,k 中各放入一粒豆子（j 可能等于 k） 。如果轮到某人而他无法按规则取豆子，那么他将输掉比赛。

求先手是否有必胜策略，若有则输出第一步操作中字典序最小的方案，以及第一步的总方案数。

大体思路

有向图游戏的和：SG(G)=\bigoplus_{i=1}^n SG(G_i)。

本题需要注意的是，不要将瓶子作为子游戏，而是将豆子作为子游戏。首先明确终止状态：游戏中止，当且仅当所有的豆子均在最后一个瓶子。为了方便，我们不妨设编号为 n-1\sim 0，这样有 SG(0)=0。

然后，每次在 i 取出一个豆子，另外瓶子加入豆子，相当于在 j,k 增加了一个子游戏，因此有：SG(x)=mex\{SG(j)\oplus SG(k)|j\in [0,x-1],k\in [0,j]\}，其中 mex\{S\}=\min\{x|x\in\mathbb N,x\not\in S\}。

那么，我们可以在 O(n^3) 的复杂度下预处理出 SG。

    inline void getSG() {
    sg[0] = 0;
    rep(i, 1, 101){
        memset(s, 0, sizeof s);
        Rep(j, i - 1, 0)
            Rep(k, j, 0)
                s[sg[j] ^ sg[k]] = 1;
        rep(j, 0, 501)
            if(!s[j]){sg[i] = j; break;}
    }
}

然后在主函数中，令 sum=\bigoplus_{i\in [0,n),p_i\text{为奇数}} SG(i)，当且仅当 sum=0 时先手必败。

然后，我们暴力枚举 i,j,k，s.t.\ sum\oplus SG(i)\oplus SG(j)\oplus SG(k)=0，即此时先手创造出了一个对于他必胜的局面，因此 cnt+1。枚举按一定顺序，即可找到字典序最小的解。

完整代码

#include <bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e4 + 5;
namespace IO_ReadWrite {
    #define re register
    #define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
    char _buf[1<<21], *p1 = _buf, *p2 = _buf;
    template <typename T>
    inline void read(T &x){
        x = 0; re T f=1; re char c = gg;
        while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
        while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
        x *= f;return;
    }
    inline void ReadChar(char &c){
        c = gg;
        while(!isalpha(c)) c = gg;
    }
    template <typename T>
    inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x/10);
        putchar('0' + x % 10);
    }
    template <typename T>
    inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;//快读
int n, p, sg[maxn];
int a, b, c, ans;
bool s[maxn];
inline void getSG() {//预处理
    sg[0] = 0;
    rep(i, 1, 101){
        memset(s, 0, sizeof s);
        Rep(j, i - 1, 0)
            Rep(k, j, 0)
                s[sg[j] ^ sg[k]] = 1;
        rep(j, 0, 501)
            if(!s[j]){sg[i] = j; break;}
    }
} 
int T;
int main() {
    getSG();
    scanf("%d",&T);
    while(T--) {
        scanf("%d", &n);
        ans = 0;
        int sum = 0;
        Rep(i, n - 1, 0){
            scanf("%d", &p); 
            if(p & 1) sum ^= sg[i];
        //有 p 个游戏，异或值为 sg[i] ^sg[i] ^ ...，共 p 次
        //由异或的性质可得，这等价于上式
        }
        if(!sum){
            puts("-1 -1 -1");
            puts("0");
            continue;
        }//特判必败
        Rep(i, n-1, 0) { 
            Rep(j, i - 1,0){
                Rep(k, j, 0){//枚举
                    int now = sum ^ sg[i] ^ sg[j] ^ sg[k];
                    if(!now) {
                        if(!ans) a = n-1-i, b = n-1-j, c = n-1-k;
                        ans++;//记录
                    }
                }
            }
        }
        printf("%d %d %d\n%d\n",a,b,c,ans);
    }

    return 0;
}