Luogu 1288 – 博弈论

PROBLEM

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

ANALYSIS

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

不考虑零权边，当链长度为 1 时，先手必胜；相应，为 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;
}

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.