PROBLEM

https://www.luogu.org/problemnew/show/P1288

ANALYSIS

因为一定有一个零权边,所以可以将环拉成链。

不考虑零权边,当链长度为 时,先手必胜;相应,为 2 时先手必败。

易证,若设起始点往左和往右走到零权边的距离为分别为x, y,则若x,y中有一个奇数,先手必胜。

这题的数据是真tm水

SOLUTION

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 30;
int n, u, z;
bool flag = 1;
int cnt;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> u;
        if (u == 0) {
            flag = 0;
            z = 0;
        }
        if (flag) {
            cnt++;
        } else {
            z++;
        }
    }
    cout << (cnt & 1 ? "YES" : "NO") << endl;
    return 0;
}

 

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注