题解：P9278 [AGM 2023 资格赛] 另一个游戏

· · 题解

解题思路

这是一道博弈论题，可以倒推求解：

  1. 在只剩 2 堆时获得先手，就能把第 n-1 堆全部移完，把第 n 堆留给对手，即可赢得比赛。
  2. 为了在只剩 2 堆时获得先手，要在只剩 3 堆的时候获得先手，并移走第 n-2 堆中的 v_{n-2}-1 个，使对手只能移走最后 1 个。
  3. 不难发现，获得第 k 堆的先手，就可以获得 k+1 堆的先手。所以只要获得第 2 堆的先手即可获胜。
  4. 因为题目是将第 1 堆移到第 2 堆，且每一堆都是正整数，所以从第 2 堆开始，后面不会出现只有 1 个石子的情况。
  5. Charlie 开局是先手，只要第 1 堆不只 1 个，都可以移走 v_1-1 个，使 Dan 只能移走最后 1 个。

综上所述，只要开局 v_1\ne 1，Charlie 都有必胜策略。特别地，当 n=2 时只有两堆石子，Charlie 将第 1 堆全部移完即可获胜。即当 v_1\ne 1 或 n=2 时输出 Charlie，否则输出 Dan。

参考代码

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

const int N=1005;
int v[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>v[i];
    cout<<(v[1]!=1||n==2?"Charlie":"Dan")<<'\n';
    return 0;
}