5. 游戏与必胜策略

5.1. 硬币游戏

描述 :有 \(x\) 枚硬币,A 和 B 两个人轮流取,每次所取的硬币数量要在 \(a_1, a_2,...,a_k\) 当中(其中包含 \(1\) )。 A 先取,取走最后一枚硬币的一方获胜。当双方都采取最优策略,谁会获胜?

策略 :动态规划。考虑轮到 A 时,还剩下 \(j\) 枚硬币。当 \(j=0\) ,A 必败;如果存在 \(a_i\) ,使得 \(j - a_i\) 是必败态,则 \(j\) 就是必胜态; 如果对于所有的 \(a_i\)\(1 \leqslant i \leqslant k\) ,使得 \(j - a_i\) 都是必胜态,则 \(j\) 是必败态。

 1int X, K, A[MAX_K];
 2
 3bool win[MAX_X + 1];
 4
 5void solve()
 6{
 7  win[0] = false;
 8  for(int j = 1; j <= X; ++j)
 9  {
10    win[j] = false;
11    for(int i = 0; i < K; ++i)
12    {
13      win[j] = win[j] | (A[i]<=j && !win[j-A[i]]);
14    }
15  }
16}

5.2. Nim 游戏

描述 :有 \(n\) 堆石子,每堆 \(a_i\) 颗石子。A 和 B 两个人轮流取,每次从石子堆中至少取走一颗。A 先取,最后取光所有石子的一方获胜。当双方都采取最优策略,谁会获胜?

策略\(a_1\ \oplus\ a_2\ \oplus\ ...\ \oplus\ a_n \ne 0\) (异或运算),则 A 必胜; \(a_1\ \oplus\ a_2\ \oplus\ ...\ \oplus\ a_n = 0\) ,则 A 必败。

5.3. Grundy 数

描述 :有 \(n\) 堆硬币,每堆 \(x_i\) 枚硬币。A 和 B 两个人轮流取,每次所取的硬币数量要在 \(a_1, a_2,...,a_k\) 当中(其中包含 \(1\) )。 A 先取,取走最后一枚硬币的一方获胜。当双方都采取最优策略,谁会获胜?

策略 :转换成 Nim, \(grundy(x_1)\ \oplus\ grundy(x_2)\ \oplus\ ...\ \oplus\ grundy(x_n) \ne 0\) 则 A 必胜,否则必败。 当前状态的 grundy 值表示:从该状态出发,一步可达状态的 grundy 值的集合之外的最小非负整数。

 1int N, K, X[MAX_N], A[MAX_K];
 2
 3int grundy[MAX_X + 1]; // 全局数组,初始化为 0
 4
 5void solve()
 6{
 7  grundy[0] = 0;
 8
 9  int max_x = *max_element(X, X+N);
10  for(int j = 1; j <= max_x; ++j)
11  {
12    set<int> s;
13    for(int i = 0; i < K; ++i)
14    {
15      if(A[i] <= j) s.insert(grundy[j - A[i]]); // 一步可达状态的 grundy 值
16    }
17    int g = 0; // 集合之外的最小非负整数
18    while(s.count(g) != 0) g++;
19    grundy[j] = g;
20  }
21
22  int res = 0;
23  for(int n = 0; n < N; ++n) res ^= grundy[X[n]];
24  if(res != 0) cout << "A wins." << endl;
25  else cout << "B wins." << endl;
26}

5.4. 两端取数

描述 :有一串数字,A 和 B 两人轮流从两端取任意个数(至少取 1 个),直到取完所有的数。A 先取,两个人都采取最优策略,求 A 所取数的和比 B 所取数的和大多少?

策略 :动态规划。\(dp[i][j]\) 表示从闭区间 \([i,j]\) 取完所有数字之后,先取的那个人所取数的和与后取的那个人所取数的和的差值。 假设第一个人先从区间 \([i,j]\)\(k\ (1 \leqslant k \leqslant j-i+1)\) 个数,可以从左端取,也可以从右端取。 如果从左端取,先取的人得到的和为 \(sum[i+k] - sum[i]\) ,后取的人得到的和为 \(dp[i+k][j]\) ;如果从右端取,先取的人得到的和为 \(sum[j+1] - sum[j-k+1]\) ,后取的人得到的和为 \(dp[i][j-k]\) 。 因此,

\[dp[i][j] = max\{ sum[i+k] - sum[i] - dp[i+k][j], sum[j+1] - sum[j-k+1] - dp[i][j-k] \},\ 1 \leqslant k \leqslant j-i+1.\]

其中 \(sum[i]\) 表示数列区间 \([0,i-1]\) 的和(前 \(i\) 项和)。

 1int maxSum(vector<int> num)
 2{
 3  int n = num.size();
 4  assert(n > 0);
 5
 6  vector<vector<int>> dp(n, vector<int>(n, 0));
 7  for (int i = 0; i < n; ++i) dp[i][i] = num[i]; // 初始化
 8
 9  vector<int> sum(n + 1, 0);
10  partial_sum(num.begin(), num.end(), sum.begin()+1);
11
12  for (int gap = 1; gap < n; ++gap)
13  {
14    for (int i = 0; i + gap < n; ++i)
15    {
16      int j = i + gap;
17      dp[i][j] = sum[j+1] - sum[i]; // 第一个人一次取完区间内所有的数,则第二个人取的数和为 0
18      for (int k = 1; k < j-i+1; ++k)
19      {
20        dp[i][j] = max(dp[i][j], max(sum[i+k] - sum[i] - dp[i+k][j], sum[j+1] - sum[j-k+1] - dp[i][j-k])); // 第一个人取 k 个数
21      }
22    }
23  }
24
25  int res = dp[0][n - 1];
26  dp.clear(); dp.shrink_to_fit();
27  sum.clear(); sum.shrink_to_fit();
28  return res;
29}