MENU

Sequential Nim

2022 年 04 月 03 日 • 阅读: 8589 • 算法

题目翻译

原题链接

有 $n$ 堆石子,第 $i$ 堆有 $a_i$ 个。两人轮流取石子,每次只能取编号最小且有石子的堆。每次可在一堆石子中取走若干个(至少取 $1$ 个),当一个人没有石子可取时,他就输了。

现在给出每堆石子的数量,假设两人都采取最优策略,问最后是先手 (First) 胜利还是后手 (Second) 胜利。

最优解

考虑几种特殊情形

  1. 只有一堆,先手直接取完获胜
  2. 只有两堆,并且第一堆石子数 $a_1 > 1$,先手可取 $a_1 - 1$ 个,后手只能取剩下一个,先手再把第二堆直接取完获胜。这种策略可应用于 $a_1,a_2,...,a_{n-1} > 1$
  3. 只有两堆,并且 $a_1 = 1$,先手只能取完第一堆,后手直接取完第二堆获胜。推广到 $a_1, a_2, ..., a_{n-1} = 1$,此时先手没有主动权,输赢由石子数为 $1$ 的前缀堆数决定,偶数个先手赢,奇数个后手赢
  4. 如果所有堆都只有一颗石子,输赢由石子堆数决定,偶数堆后手赢,奇数堆先手赢

考虑一般情形

$$ \underbrace{1, 1, ..., 1}_{k_0},\ \overbrace{a_{k_0+1},a_{k_0+2},...,a_{k_0+x_0}}^{x_0},\ \underbrace{ \underbrace{1, 1, ..., 1}_{k_1},\ \overbrace{a_{k_0+x_0+k_1+1},a_{k_0+x_0+k_1+2},...,a_{k_0+x_0+k_1+x_1}}^{x_1},\ ..., }_{repeat} a_n $$

其中未标 $1$ 的石子堆数大于 $1$

  1. 由特殊情形 $2, 3$ 的分析可知,如果中间没有 $1$,$k_0$ 决定输赢
  2. 如果中间有 $1$,不妨假设先手首先取 $a_{k_0+1}$,考虑他是否有策略保证自己先取 $a_{k_0+x_0+k_1+1}$。答案是肯定的,他只要根据 $k_1$ 的奇偶性决定是否取完 $a_{k_0+x_0}$

由此可见,$k_0$ 决定主动权归属,并且获得方可将主动权一直保持下去,直到自己一次性取完 $a_n$。所以可直接求前缀 $1$ 的个数

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e5 + 5;
int t, n, a[N];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0; i < n; i++) cin >> a[i];

        int k = 0;
        while(k < n && a[k] == 1) k++;
        cout << ((k == n) ^ (k & 1) ? "Second" : "First") << "\n";
    }

    return 0;
}

SG 函数做法

定义 $SG(i, j)$ 为前 $i - 1$ 堆已取完,第 $i$ 堆还剩 $j$ 颗的状态。该状态的后继状态为前 $i - 1$ 堆已取完,第 $i$ 堆还剩 $k$ 颗,$k \in [0, j)$,则

$$ SG(i,j) = mex\{SG(i, 0), SG(i, 1), ..., SG(i, j-1)\} $$

由于是从后往前递推,初始状态为 $SG(n, j) = j$

考虑对状态转移做优化

  1. $SG(i, 0) = SG(i+1, a_{i+1})$,因为它们都对应第 $i$ 堆已取完,第 $i+1$ 堆还未取,记 $x = SG(i, 0)$

    1. 若 $x >= a_i$,已知 $SG(i, 1), SG(i, 2),...,SG(i, a_i-1)$ 共 $a_i-1$ 项,根据 $mex$ 规则,$0,1,...,a_i-2$ 依次是它们的值,所以 $SG(i, a_i) = a_i - 1$
    2. 若 $x < a_i$,$SG(i, 0), SG(i, 1), SG(i, 2),...,SG(i, a_i-1)$ 共 $a_i$ 项,会不重不漏取完 $0,1,...,a_i-1$,所以 $SG(i, a_i) = a_i$

我们只需求 $SG(i, a_i)$,所以可以去掉第二维。由于是顺序取石子,能操作的有向图只有一张,所以必胜态是 $SG(1, a_1) \neq 0$

#include <bits/stdc++.h>
 
using namespace std;

const int N = 1e5 + 5;
int t, n, a[N], sg[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];

        sg[n] = a[n];
        for(int i = n - 1; i; i--)
            sg[i] = sg[i + 1] >= a[i] ? a[i] - 1 : a[i];
        
        cout << (sg[1] ? "First" : "Second") << "\n";
    }

    return 0;
}
TG 大佬群 QQ 大佬群

最后编辑于: 2022 年 04 月 05 日
返回文章列表 文章二维码
本页链接的二维码
打赏二维码
添加新评论

Loading captcha...