取数游戏II-洛谷 _结论

题目描述
解题思路问题简化
由题目知，这个环里至少有一条边为0，而为0的边是无法经过的，所以起点两边的两个第一个为0的边之间的边是不可能到达的，因此可以把问题简化为只有1个边为0的环，即把那些不可能到达的边删除并把两个为0的边仅保留1个，如下图
之后再更新一下n，如上图即n由7更新为5 。
存在必胜策略反推

文章插图
当轮到对手时硬币两边的边上都是0，那我们就赢了。
则如果轮到我们的时候硬币与长度为0的边中间恰好隔着1条非0边，就有必胜策略。（结论1）
当硬币的一条临边为0时，则在往另一临边移动后必须把该临边减为0，否则对手就可以直接往回走并把该临边减为0，那我们就输定了。
所以，当硬币的一条临边为0时，则最优策略为往另一临边移动并把该临边减为0 。（结论2）
由结论1和结论2可以推出，
【取数游戏II-洛谷】只要起点往顺时针方向或逆时针方向与长度为0的边之间的边数为奇数，则存在必胜策略。（结论3）
当更新后的n为偶数时，即非0边数为奇数，则必有一个方向满足与长度为0的边之间的边数为奇数，再由结论3可以推出，
若更新后的n为偶数，则存在必胜策略。（结论4）
当更新后的n为奇数时，即非0边数为偶数，则两个方向均与长度为0的边之间的边数为奇数或两个方向均与长度为0的边之间的边数为偶数，则只需要考虑其中一个方向即可，再由结论3可以推出，
若0边对应存储的数组下标为奇数，则存在必胜策略，反之则不存在。（结论5）
代码

#include 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边为0if (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;}