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

· · 题解

题意理解

一道有趣而简单的博弈论题目。

给出一个正整数 n，接下来一行给出 n 个正整数，表示这 n 堆石子每堆石子的数量，两人可以不断从最左端有石子的一堆中拿石子到右边一堆，如果当前轮只剩下最后一堆石子，则这个人输。

思路阐述

将最后一堆留给对手，即将倒数第二堆的主动权在自己手中，想要倒数第二堆的主动权，让倒数第三堆必须被对手挪完，即倒数第三堆只剩下一个石子，从后往前推，直至第一个，所以除非第一堆只有一个石子，否则主动权将永远在先手手中，即先手胜利。

但是注意 n=2 的情况，此时策略不同，先手不管第一堆有多少个，直接全部放到下一堆即可。

策略：当 n=2 时，先手直接把第一堆挪完，这样就只剩下一堆了；当 n>2 时，重复将当前堆只剩下一个石子，以实现当 n=2 时移动权在手中。

举个例子：

\text{3 8 1 1 6 先手轮} \text{1 10 1 1 6 后手轮} \text{0 11 1 1 6 先手轮} \text{0 1 11 1 6 后手轮} \text{0 0 12 1 6 先手轮} \text{0 0 1 12 6 后手轮} \text{0 0 0 13 6 先手轮} \text{0 0 0 0 19 后手轮}

综上得出：当 n=2 时，先手必胜；当 n>2 时，如果第一个数 v\ne 1，先手必胜，否则后手必胜。

代码呈现

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

int n,v;

signed main(){

    scanf("%d",&n);
    scanf("%d",&v);//只需要第一堆的数量就可以判断了
    if (n==2){//只有两堆，特判先手必胜
        printf("Charlie");
        return 0;
    }
    if (v==1) printf("Dan");//第一堆只有一个
    else printf("Charlie");
    return 0;

}

希望可以帮到各位大佬。