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}