转载自 https://blog.csdn.net/Brian_Pan_/article/details/103860752
可以把环想象成两条路, 如果没有天生的 0, 那两条路就是一样的 (如果有的话, 就两个方向跑一遍, 奇数个非零 alice 必胜)
如果是偶数个的话, 就没有必胜的策略了, 只能根据 bob 所走的选择我们 Alice 最优的方案 (不是我们考虑的范围)
- #include<iostream>
- using namespace std;
- const int N=30;
- int a[N];
- int main(void)
- {
- int n;
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i];
- }
- int ans1=0;
- for(int i=1;i<=n;i++)
- {
- if(a[i])
- ans1++;
- }
- int ans2=0;
- for(int i=n;i>=1;i--)
- {
- if(a[i])
- ans2++;
- }
- if(ans1&1||ans2&1)
- cout<<"YES"<<endl;
- else
- cout<<"NO"<<endl;
- return 0;
- }
我们可以把这个环想象成两条路, 如果路的尽头没有边权为 0
0 的边, 那么两条路径就是一样的.
我们可以把这个环想象成两条路, 如果路的尽头没有边权为 0
0 的边, 那么两条路径就是一样的.
对于一条路径, 设 Alice
Alice 为先手, 那么她将她走过的路径边权变为 00. 轮到 BobBob 时, 他最多也只能有一条路可以走. 如果他选择不将该路边权变为 00, 下一步 AliceAlice 一折返他就输了. 如果他将边权变为 00, 那么就变成重复以上操作了
最后如果路径长度为奇数, AliceAlice 还是赢; 路径长为偶数的话 Alice
Alice 就没有必胜策略
这样这题就被转化成判断两条路径奇偶性了
来源: http://www.bubuko.com/infodetail-3393759.html