题目链接 https://www.luogu.org/problem/P1288
Solution 取数游戏
题目大意: 有一个环, 每条边有边权. 硬币一开始在 \(1\) 号点, 你可以走边权不为 \(0\) 的边, 将硬币移动到另一个端点, 同时将边权减至一个非负数, 不能走的情况判负. 问是否有先手必胜方案
博弈论
分析: 首先我们可以考虑一次性将边变成 \(0\), 这样就相当于堵死了下一个人一个方向, 所以方向是由先手的人决定的. 然后如果前面遇到了一条 \(0\) 边, 显然这人就 GG 了, 所以我们只需要枚举两个方向, 记录遇到 \(0\) 边走的位置的奇偶性即可
- #include <iostream>
- #include <cstdlib>
- using namespace std;
- int val[32],n;
- inline void AMDyes(){//AMD YES!!
- puts("YES");
- exit(0);
- }
- int main(){
- iOS::sync_with_stdio(false);
- cin>> n;
- for(int i = 1;i <= n;i++)cin>> val[i];
- for(int i = 1;i <= n;i++)
- if(!val[i])
- if(i & 1)break;
- else AMDyes();
- for(int i = n;i>= 1;i--)
- if(!val[i])
- if((n - i + 1) & 1)break;
- else AMDyes();
- puts("NO");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3255750.html