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

原题链接

• 洛谷 P9278 [AGM 2023 资格赛] 另一个游戏

解题思路

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

• 在只剩 $2$ 堆时获得先手，就能把第 $n-1$ 堆全部移完，把第 $n$ 堆留给对手，即可赢得比赛。

• 为了在只剩 $2$ 堆时获得先手，要在只剩 $3$ 堆的时候获得先手，并移走第 $n-2$ 堆中的 $v_{n-2}-1$ 个，使对手只能移走最后 $1$ 个。

• 不难发现，获得第 $k$ 堆的先手，就可以获得 $k+1$ 堆的先手。所以只要获得第 $2$ 堆的先手即可获胜。

• 因为题目是将第 $1$ 堆移到第 $2$ 堆，且每一堆都是正整数，所以从第 $2$ 堆开始，后面不会出现只有 $1$ 个石子的情况。

• Charlie 开局是先手，只要第 $1$ 堆不只 $1$ 个，都可以移走 $v_1-1$ 个，使 Dan 只能移走最后 $1$ 个。

2. 综上所述：只要开局 $v_1\not=1$，Charlie 都有必胜策略。特别地，当 $n=2$ 时，只有两堆石子，Charlie 将第 $1$ 堆全部移完即可获胜。

3. 最后整理得：当 $v_1\not=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;
}