打表手玩找规律

经典 Turning Turtles 游戏

VJwin14C - Game with Marbles (Hard Version)

两人各有 $n$ 堆石子，分别编号 $1\sim n$。两人轮流选择石子，选择其中一个编号，自己弃这个编号的石子堆的其中一颗石子，对方弃这个编号的石子堆的所有石子。最终得分为甲和乙的石子总数之差，甲希望得分最大化，乙希望得分最小化。求两人的获胜策略，并给出最终得分。

记每方的得分为他最终剩下的石子，实际双方都希望自己得分尽可能大。

设某一堆石子甲有 $a$ 颗，乙有 $b$ 颗，如果甲选择了，它的得分会增加 $a-1$，否则甲不选，乙的得分增加 $b-1$。对于两堆石子 $a_1,b_1$ 和 $a_2,b_2$，如果甲先选择编号为 $1$ 的，乙就只能选择编号为 $2$ 的，最终得分为 $W_1=(a_1-1)-(b_2-1)=a_1-b_2$，如果甲先选择编号为 $2$ 的，最终得分为 $W_2=(a_2-1)-(b_1-1)=a_2-b_1$，注意到 $W_1-W_2>0\iff a_1+b_1>a_2+b_2$，这表明，甲需要先选择 $a+b$ 较大的编号，乙也是同理，这即是获胜策略，得分易算得。

VJwin14D - 三国游戏

两人轮流选择武将，每两个武将有默契值，最终所选择的武将之间的最大默契值较大的获胜。已知对方的策略是：选择我方已经选择的所有武将的最大默契值对应的那名武将。求获胜策略，并给出我方最终的最大默契值。

对于每一名武将，如果我方将其选走，那么对方会选择最大默契值，于是这个最大默契值两个人都拿不到，可以推出，每个武将的最大默契值两个人都拿不到。因此我们将视线转向次大默契值，在对方选择后，我方可以继续选择次大默契值，这个次大默契值就归我方所有。为了获胜，我们首先选择次大默契值最大的那名武将，选择它，对方会选择最大默契值对应的那名武将，我方接着次大默契值对应的那名武将。由于最大默契值两个人都拿不到，而我方抢走了最大的次大默契值，因此我方必胜。我方最终的最大默契值即是最大的次大默契值。

B. 奶牛的数字游戏 洛谷 -P2953

对一个数字 $n$ 双方轮流减去其最大数码或者最小非零数码。

很板子的博弈，说是 $dp$ 也不是不行。数字 1-9 都是必胜，后续分别判断减去最大数码和最小数码的两个状态中是否有必败态。这里只需要计必胜必败态，不用 SG，开 bool 数组就可以了。

for (int n = 1; n < N; ++n) {
    int minn = 9, maxx = 0;
    for (char c : to_string(n)) {
        if (c == '0') continue;
        minn = min(minn, c - '0');
        maxx = max(maxx, c - '0');
    }
    sg[n] = 1 ^ (sg[n - maxx] & sg[n - minn]);
}
for (int t = (cin >> t, t); t--; ) {
    int n;
    cin >> n;
    cout << (sg[n] ? "YES" : "NO") << endl;
}

C. 高手们的石子游戏 洛谷 -P2575

对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛。

一眼就觉得很阶梯，每一行都是独立的不会互相影响，又一眼会觉得很 SG 函数，故写之。

把两个空格之间当作一堆石子，连续棋子当作石子数。

int res = 0;
while (n--) {
    array<bool, 25> a{};
    while (m--) {
        cin >> x;
        a[x] = 1;
    }
    vector<int> b;
    int tot = 0;
    for (int i = 1; i <= 20; i++) {
        if (!a[i]) {
            b.push_back(tot);
            tot = 0;
        } else {
            tot++;
        }
    }
    reverse(b.begin(), b.end());
    for (int i = 0; i < b.size(); i += 2) {
        res ^= b[i];
    }
}
if (res) cout << "YES" << endl;
else cout << "NO" << endl;

E. 真正的签到游戏 HDU-1730

游戏在一个 $n$ 行 $m$ 列的棋盘上进行，每行有一个黑子和一个白子。执黑的一方先行，每次玩家可以移动己方的任何一枚棋子到同一行的任何一个空格上，但不许越过该行的敌方棋子。双方轮流移动，直到某一方无法行动为止，不能操作者败。

对于每一行，最终态为黑白棋子距离为 0，中间若先手打破该状态，后手必有操作可以恢复到该状态，如此反复。因此只关心黑白棋子距离。依据 SG 定理，每行黑白棋子距离的 Nim 和不为 0 先手胜。

F. 海盗的金币游戏 HDU-1538

经典中的经典题，模拟即可。

题意：一群绝顶聪明的海盗分金币，按顺序提出方案，包括提出者在内的所有海盗都进行投票。若有 50% 及以上海盗赞成即通过，否则会把提议者扔进海里换下一个海盗继续提议。

海盗们的策略是保命 > 更多的钱 > 杀人。

你的任务是预测给定的海盗会得到多少金币。

如果分 100 枚金币的话，脑内迅速打个表：

• 1： 100
• 2： 0 100
• 3： 1 0 99
• 4： 0 1 0 99
• 5：1 0 1 0 98

不难看出只要给与自己编号奇偶相同的海盗各一枚金币即可，但是这种情况仅仅适用于金币够分的时候。

当海盗人数大于 200 人时：

• 201：所有奇数位各一枚，自己不能拿就可以活
• 202：所有偶数位各一枚，自己不能拿就可以活
• 203：至少需要 102 票，贿赂 100 人 + 自己只有 101 票，死
• 204：自己死了 203 必死，故会得到 102 票，活
• 205：拿不到 203 和 204 的票，死
• 206：得到 205 支持，但 102 < 103，死
• 207：得到 205 和 206 支持，103 < 104，死
• 208：得到 205，206，207 支持，刚好够 104 票，活

不难看出数量大于 $2\times100$ 时，1，2，4，8……刚好能活。

记 $n = 2 m+2 ^ k$ 为稳定状态。

int n, m, p;
cin >> n >> m >> p;
if (n <= 2 * m + 2) { // 够分 
    if (p != n) { // 不是分的 
        cout << (((p + n) % 2) ^ 1) << endl; // n 奇数时 p 奇数输出 1 p 偶数输出 0
    } else { // 是分的 
        cout << m - (n - 1) / 2 << endl; // 分走一半，剩下的私吞 
    }
} else {
    n -= (2 * m);
    p -= (2 * m);
    int ans = 1 << __lg(n);
    if (p <= ans) {
        cout << "0" << endl;
    } else {
        cout << "Thrown" << endl;
    }
}

G. 签到硬币游戏 POJ-2484

$N$ 个硬币摆成一圈，轮流将一枚正面朝上的硬币翻转，或者将相邻的两枚正面朝上的硬币翻转，无法操作者败。

• $N=1$ 或 $N=2$ 先手胜。
• $N \geqslant 3$ 后手胜，后手可以将环分成两个相等的对称段。

变式 ：$n$ 个硬币摆成一圈，轮流将相邻的 $[1,k]$ 枚正面朝上的硬币翻转，或者将相邻的两枚正面朝上的硬币翻转，无法操作者败。

• $k=1$ 时平凡，当且仅当 $n$ 为奇数时先手胜。
• 特判 $n=k$ 时先手胜。
• $k>1$ 时包含 $k=2$ 的情形，套用之前的结论。

H. 字符串游戏 51Nod-1490

有一个两人游戏，有 $n$ 个非空串，两个玩家轮流向一个字符串后面加字母，刚开始字符串是空的。每一次操作是向当前字符串后面添加字符，形成的新字符串一定要是这 $n$ 个串中某一个或几个的前缀，如果无法做到，就输了。

这样的游戏似乎过于简单了，现在对这个游戏进行一下改进，让玩家玩 $K$ 次这样的游戏，第 i 次的败者，将会作为第 $i+1$ 次的先手进行这个游戏。第 $k$ 次游戏的赢家就是整个游戏的赢家。
现在给定 $n$ 个字符串和 $k$，问是先手胜还是后手胜。

建一棵 Trie，将所有字符串插入树中，然后进行类似于树形 DP 的操作，和一般的博弈不同，因为要进行 $k$ 轮，并且失败者下一轮会变成先手，所以先手要保证自己最终必赢的情况下，当前轮他可能采取必赢策略也可能采取必输的策略（有可能他要故意输掉前 $k-1$ 轮，赢下最后一轮），故进行树形 DP 的时候要分别按照先手必赢、先手必输、可输可赢、无法控制四种状态 DP。

const int N = 1e6 + 8;
int trie[N][26];
int pcnt = 0;

void insert(string& s) {
    int p = 0;
    for (auto c : s) {
        if (trie[p][c - 'a'] == -1) trie[p][c - 'a'] = ++pcnt;
        p = trie[p][c - 'a'];
    }
}

int dfs(int n) {
    int sum = 0;
    int ans = 0;
    for (int i = 0; i < 26; i++) {
        if (trie[n][i] == -1) continue;
        else {
            sum++;
            int res = dfs(trie[n][i]);
            ans |= res ^ 3;
        }
    }
    if (sum == 0) return 2; // 叶子节点 
    else return ans;
}

//ans = 1 win
//ans = 2 lost
//ans = 3 win or lost
//ans = 0 do not know

int main() {
    int n, k;
    string s;
    cin >> n >> k;
    memset(trie, -1, sizeof trie);
    for (int i = 1; i <= n; i++) {
        cin >> s;
        insert(s);
    }
    int ans = dfs(0);
    if (ans == 1) {
        if (k & 1) {
            cout << "First" << endl;
        } else {
            cout << "Second" << endl;
        }
    } else if (ans == 2 || ans == 0) {
        cout << "Second" << endl;
    } else {
        cout << "First" << endl;
    }
    return 0;
}

I. 巧克力游戏 -HDU 3544

给 $n$ 块巧克力，第 i 块是 $n_i m_i$，Alice 只能垂直切，Bob 只能横切。

设 $HP(n, m)$ 表示 $n m$ 的矩形对 Alice 的可切割次数的贡献，负数代表 Bob 的贡献，如果所有 $\sum HP_i > 0$ ，Alice 必赢， $\sum HP_i \leqslant 0$ ，Bob 必赢。

对于 $HP(i,j)$ 的计算我们有如下法则

1. $n * 1$ 的矩形贡献为 $n-1$；
2. $1 * m$ 的矩形贡献为 $-(m-1)$；
3. $n \times n$ 的矩形对 HP 的贡献为零，因为如果你首先下手切，都会给对手更多的机会，如果你能赢，你不会切这个，如果你输，那么切了这个你还会输；
4. $n \times (n+1)$ 的矩形与 3 的情况相同，对答案的贡献都是 0，首先下手都会给对手更多的机会；
5. 贡献为零的有什么规律呢，我们发现原来是它们是 $2^k \leqslant n < 2^{k+1}$ 且 $2^k \leqslant m < 2^{k+1}$；
6. $n \times 2$ 的矩形对于 Alice 来说有贡献，我们每一次可以选择都切成 $2\times 2, 3 \times 2$ 的矩形，这样不会给对手机会，自己还可以增加一次切的机会，Bob 也不会傻到切这个矩形，这样会给 Alice 更多机会，所以 $n \times 2$ 的矩形，Alice 可以切 $\dfrac{n}{2} - 1$ 次

这个时候可以总结一下规律：每一次切都会切成 $HP(i, m) = 0, HP(n - i, m) \geqslant 0$ 的两块， $HP(n, m) = HP(n - i, m) + 1$ ，递归下去，我们知道 $HP(n, m) = 0$ 当且仅当 $2^k \leqslant n < 2^{k+1}$ 且 $2^k \leqslant m < 2^{k+1}$，那么就有 $HP(n, m) = \dfrac{n}{2^k} - 1$。

int n;
cin >> n;
ll a = 0, b = 0;
while (n--) {
    int x, y;
    cin >> x >> y;
    while (x > 1 && y > 1) {
        x >>= 1;
        y >>= 1;
    }
    if (y == 1) a += x - 1;
    if (x == 1) b += y - 1;
}
printf("Case %d: %s\n", Ti, a > b ? "Alice" : "Bob");