【题解】博弈论的一些练习题 ——quhengyi11

传送门：CodeM2017 决赛 melon

题目大意：Alice 和 Bob 玩博弈玩累了于是开始吃瓜，Alice 手速永远比 Bob 快，同时刻拿瓜 Alice 先抢到，每人每次拿瓜 L 个，总共 n 个瓜，每人需要 k 个单位的时间吃掉 k 个瓜，而且 Alice 和 Bob 永远是互相知道对方是绝顶聪明的，问 Alice 最多能吃到多少瓜
这道题其实就是一个分析

情况一：$n \leq L$

这时候我们的 Alice 会凭借她的先手优势直接拿掉 n 个瓜。

情况二： $L < n \leq 2L$

容易知道Bob一定不可能比Alice吃的多（否则Alice在 $n > L$的状况下跟 Bob 取同样的就行），因此我们尝试最大化 Bob 吃掉的瓜，Alice 一定能至少先吃 $L$个瓜，因此 Bob 最多还能拿 $n-L$个瓜，显然这是可以拿到的，所以 Bob 最多吃 $n-L$个瓜，Alice 吃 $L$个

情况三 ： $n > 2L$

思路依旧是最大化Bob的瓜，显然每次拿一个瓜是不亏的，就算Alice手速快，但在剩余瓜数 $>2L$的时候Bob是跟Alice保持同步的，而且若出现一种情况，当Bob吃完某一个瓜的时候猛然发现只剩下 $2L$个瓜了，然后Alice手里还有 $k>=1$个瓜在苦苦地吃，Bob就能先拿 $k-1$个瓜吃完，然后再一次拿掉 $L$个瓜，这样他就不会比Alice吃的少了，但Alice辣么聪明她不会给他这样的机会的，因此Alice也每次拿一个瓜，因此他们在 $n>2L$时永远保持同步，一旦 $n<=2L$，Alice 就会拿 L 个瓜，Bob 会拿掉剩下的瓜，因此 Alice 最多能吃 $[\frac{n+1}{2}]$个瓜
代码就不用给了吧。

传送门：2017 ACM-ICPC ECL-FINAL L 题

题目大意：给一个空序列，两人（就 Alice 先手 Bob 后手吧）轮流每回合在任意一个位置填’S’ 或者’O’，填出’SOS’ 的人胜利，给出序列长度求是否有必胜策略，若有，输出谁必胜。

个人感觉挺毒瘤的 QwQ
首先，序列长度 $n < 7$的时候，显然是没有必胜策略的。
$n=7$的时候，Alice 可以这样做，她能取得胜利：
第一步 (Alice)：
$$—\;—\;—\;S\;—\;—\;—$$
第二步 (Bob)(由对称性，不妨放在左边):
$$—\;—\;S\;S\;—\;—\;—$$
第三步 (Alice):
$$—\;—\;S\;S\;—\;—\;S$$
容易发现后面的四个格子被 “封死” 了（谁下就必输），而且能下的格子只剩下两个，当前 Bob 下，所以最后下被’ 封死’ 格子的一定是 Bob。所以 Alice 获胜。
那如果 Bob 第二步这样下呢：
$$S\;—\;—\;S\;—\;—\;—$$
容易分析，还是 Alice 获胜。
我们发现，$S\;—\;—\;S$的阵型是弄出必胜策略的关键，但为什么即使对方也构造这种阵型依然是赢不了的呢？
容易知道，无论如何下，两个人一轮之后，接下来的可下位置（$n-$下过位置 $-$封死位置）的奇偶性是保持不变的（不变量），因此胜负性是始终保持不变的。
因此下最后一步的，n 是奇数的话肯定是 Alice，反之是 Bob。
n 为奇数的时候，Alice 肯定有优势，可能会赢，由上面的讨论，易知 $n \geq 7$的时候是一定能赢的，因为 Alice 能构造出不可能平局的阵型 $S\;—\;—\;S$
n 为偶数的时候，则是 Bob 有优势，这个时候 Alice 会尽力阻止 Bob 形成不可能平局阵型，因此 Alice 会在正中间下一个 O，
相当于把棋盘分成了 $n/2$和 $n/2-1$两份，Bob 当然会挑大的那一份继续下，这时候相当于 Bob 先手，由上面的讨论易知需要有 7 个空位才会赢，而且 O 相邻的那个位置是不能放 S 的，因此要 $n/2\geq 8$，也就是 $n\geq 16$的时候 Bob 是必胜的。
也就是这种状况 (一轮过后)：
$$—\;—\;—\;S\;—\;—\;—\;—\;O\;—\;—\;—\;—\;—\;—\;—$$
其它情况就是平局了。
代码也不给了（几个 if 真的太短了懒得找记录复制）

传送门：HNOI2007 分裂游戏

题目大意：有 n 个瓶子， 第 i 个瓶子中装有 $p[i]$颗巧克力豆，Alice 和 Bob 轮流取豆子，每一轮每人选择 3 个瓶子。标号为 i,j,k, 并要保证 i < j , j < = k 且第 i 个瓶子中至少要有 1 颗巧克力豆，随后这个人从第 i 个瓶子中拿走一颗豆 子并在 j,k 中各放入一粒豆子，无法取豆子的人输

显然这种游戏可以考虑 Nim
但是如果把每个游戏当成一个独立游戏的话，我们会发现并不好表示每个游戏的 SG 函数值，这里我们改变一下策略，我们把每一个豆子当成一个游戏，那样的话我们就可以找到准确的后继状态，设第 i 个瓶子里的豆子为 $SG(i)$，则有
$$SG(i)=mex \{SG(j)\;xor\; SG(k) | i \lt j \leq k = n \}$$

然后把所有豆子 $xor$起来就是答案了。
代码:

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
#define ll long long
#define N 105
int T, n, num[N], a, b, c, sg[N], now, fl[N], ans;
inline int mex (int x)
{
    int i = 0;
    while (fl[i] == x) ++i;
    return i;
}
int main ()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        fo (i, 1, n)
            scanf("%d", &num[i]);
        sg[n] = 0;
        fd (i, n - 1, 1)
        {
            ++now;
            fo (j, i + 1, n)
                fo (k, j, n)
                    fl[sg[j] ^ sg[k]] = now;
            sg[i] = mex(now);
//          printf("sg[%d] = %d\n", i, sg[i]);
        }
        ans = 0;
        fo (i, 1, n)
            if (num[i] & 1) ans ^= sg[i];
        if (!ans) printf("-1 -1 -1\n0\n");
        else
        {
            int cnt = 0;
            a = b = c = 0;
            fo (i, 1, n)
                if (num[i])
                {
                    fo (j, i + 1, n)
                        fo (k, j, n)
                            if ((ans ^ sg[i] ^ sg[j] ^ sg[k]) == 0)
                            {
                                if (!a)
                                {
                                    a = i; b = j; c = k;
                                }
                                ++cnt;
                            }
                }
            printf("%d %d %d\n%d\n", a - 1, b - 1, c - 1, cnt);
        }
    }
}

传送门：Daizhenyang's Coin

题目大意：桌面上有 n 个硬币，其中有一些正面朝上，而有一些背面朝上，两个人轮流游戏。当轮到一个人时，他需要选取一枚正面朝上的硬币，翻转该硬币，并且再选取它之前的 0 或 1 或 2 枚硬币（不一定正面朝上），并翻转它们。无法操作的人算输，问先手是否必胜。

其实还是类似的玩法，把每个硬币当成一个独立的游戏，然后把所有值 $xor$起来就行了，但是这次不同的是，算 $SG$函数的复杂度太大了 $a[i] <= 10^8$，因此我们需要先打个表（雾
打表代码：

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
#define ll long long
#define N 105
int T, n, num[N], a, b, c, sg[N], now, fl[N], ans;
inline int mex (int x)
{
    int i = 0;
    while (fl[i] == x) ++i;
    return i;
}
int main ()
{
    scanf("%d", &n);
    sg[0] = 0;
    fo (i, 1, n)
    {
        ++now;
        fl[0] = now; //choose zero
        fo (j, 1, i - 1)
            fl[sg[j]] = now;
        fo (j, 1, i - 1)
            fo (k, j + 1, i - 1)
                fl[sg[j] ^ sg[k]] = now;
        sg[i] = mex(now);
    }
    fo (i, 1, n)
        printf("%d %d %d\n", i, sg[i], i * 2 - sg[i]);
}

可以发现 $ i , sg[i] , i*2-sg[i] $十分有规律

有一个十分不显然的关系：

$$SG[i]=i*2- ( count ( a [ i ] -1 ) \& 1 ) -1$$

其中 $count(a[i]-1)$表示 $a[i]$二进制中 $1$的个数
然后我们就可以很开心的 A 掉这题啦～
（注意题目中的 $a[i]$可能重复，要去重）
代码：

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define lowbit(x) (x & -x)
int n, a[1005], ans, sg;
inline int count (int x)
{
    int ret = 0;
    while (x)
    {
        x -= lowbit(x);
        ++ret;
    }
    return ret;
}
int main ()
{
    while (~scanf("%d", &n))
    {
        ans = 0;
        fo (i, 1, n)
            scanf("%d", &a[i]);
        std::sort(a + 1, a + n + 1);
        n = std::unique(a + 1, a + n + 1) - a - 1;
        fo (i, 1, n)
        {
            ++a[i];
            if (a[i] == 1) sg = 1; else
            sg = a[i] * 2 - ((count(a[i] - 1) & 1) ? 2 : 1);
            ans ^= sg;
        }
        if (ans)
            printf("No\n");
        else
            printf("Yes\n");
    }
}