CF1418C题解

· · 题解

思路：

考虑贪心。

对于11这种请况，因为第一个是 1 且第二个也是 1，又因为要让先手尽可能的小，所以先手只选一个 1，而后手选的话就选两个。\ 对于10这种情况，第一个是 1 第二个是 0，0选跟没选一样，这里先手选，后手不选，为什么后面再说。\ 对于0000...01，我们发现只要 0 的个数 \ge 2 那么不管是先手先去还是后手先取都能让后手先取到 1，证明如下：

当有两个的时候，此时，若后手取，就只取一个 0，然后再让先手取一个，那么就能让后手先取 1，而先手先取就直接把两个 0 去掉就可以了。 当有 >2 个 0 时，那么我们可以取掉一些转化为两个的（大不了就先手取一个，后手取一个，一直到 2）。

那么我们发现若101这种请况后手取了10那么先手就只能把最后一个 1 给拿了，但其实它可以不拿，所以10这种情况就后手不取 0，先手取 0。

Code:

#include <bits/stdc++.h>
using namespace std;
int T;
int n;
int a[200010];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        int i = 1, ans = 0;
        bool is_ = false;
        while (i <= n) {
            if (a[i] == 0) {
                int cnt = 1;
                int j = i;
                while (j < n && a[j + 1] == 0) ++j, ++cnt;
                if (cnt >= 2) {
                    i = j + 1;
                    is_ = true;//一段长度>=2的0之后一定是后手先取，所以设成这轮先手不取
                    continue;
                }
            }
            if (!is_) {//先手取
                if (a[i] == 1) {
                    ++ans;
                    if (i < n && a[i + 1] == 0 && a[i + 2] == 1) i = i + 2;
                    else ++i;
                } else {
                    if (i < n && a[i + 1] == 0) i = i + 2;
                    else ++i;
                }
            } else is_ = false;
            if (i > n) break;
            if (a[i] == 1) {//后手取
                if (i < n && a[i + 1] == 1) i = i + 2;
                else ++i;
            } else {
                if (i < n && a[i + 1] == 1) i = i + 2;
                else ++i;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}