取数游戏II-洛谷

题目描述

解题思路

1. 问题简化

由题目知，这个环里至少有一条边为0，而为0的边是无法经过的，所以起点两边的两个第一个为0的边之间的边是不可能到达的，因此可以把问题简化为只有1个边为0的环，即把那些不可能到达的边删除并把两个为0的边仅保留1个，如下图

之后再更新一下n，如上图即n由7更新为5。

2. 存在必胜策略反推

当轮到对手时硬币两边的边上都是0，那我们就赢了。

则如果轮到我们的时候硬币与长度为0的边中间恰好隔着1条非0边，就有必胜策略。（结论1）

当硬币的一条临边为0时，则在往另一临边移动后必须把该临边减为0，否则对手就可以直接往回走并把该临边减为0，那我们就输定了。

所以，当硬币的一条临边为0时，则最优策略为往另一临边移动并把该临边减为0。（结论2）

由结论1和结论2可以推出，

只要起点往顺时针方向或逆时针方向与长度为0的边之间的边数为奇数，则存在必胜策略。（结论3）

当更新后的n为偶数时，即非0边数为奇数，则必有一个方向满足与长度为0的边之间的边数为奇数，再由结论3可以推出，

若更新后的n为偶数，则存在必胜策略。（结论4）

当更新后的n为奇数时，即非0边数为偶数，则 两个方向均与长度为0的边之间的边数为奇数 或 两个方向均与长度为0的边之间的边数为偶数 ，则只需要考虑其中一个方向即可，再由结论3可以推出，

若0边对应存储的数组下标为奇数，则存在必胜策略，反之则不存在。（结论5）

代码

#include <iostream>
using namespace std;
int a[20];
int main(){
    int n, first0ind, last0ind, m;
    cin >> n;
    // 输入同时标记首0元素下标
    for (int i = 0; i < n; i++){
        cin >> a[i];
        if (!a[i]){
            first0ind = last0ind = i;
            m = i + 1;
            break;
        }
    }
    // 输入同时标记末0元素下标
    for (int i = m; i < n; i++){
        cin >> a[i];
        if (!a[i])	last0ind = i;
    }
    // 简化问题为只有1边为0
    if (first0ind != last0ind)
        for (int i = 1; i + last0ind < n; i++)
            a[first0ind + i] = a[last0ind + i];
    // 新的长度
    n += first0ind - last0ind;
    // 解答
    if (n % 2 == 0){
        // n为偶数先手存在必胜策略
        cout << "YES" << endl;
    }
    else{
        // 唯一0元素的下标为奇数则先手存在必胜策略，为偶数则先手不存在必胜策略
        if (first0ind % 2)	cout << "YES" << endl;
        else	cout << "NO" << endl;
    }
    return 0;
}