本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-18 21:39:28

思路：

考虑贪心。

对于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;
}