-
分析
发现操作2不会改变数的奇偶性，故无视。
那么操作就是单纯删一个数。
对于一个连续出现 \(x\) 个奇偶性相同的数的序列，需要删 \(x - 1\) 个数（因为只剩下一个数就不会和相邻的数奇偶性相同了）。
觉得找序列太麻烦，观察到连续出现 \(x\) 个奇偶性相同的数的序列有 \(x - 1\) 个不合法对（即相邻的两个数奇偶性相同的数对）。
于是题面变成了统计不合法对的个数，\(\mathcal{O(n)}\) 扫一遍即可。 -
代码
#include <iostream>
using namespace std;
constexpr int MAXN(1000007);
int a[MAXN];
int T, n;
inline void read(int &temp) { cin >> temp; }
inline void work() {
read(n);
int res(0);
for (int i(1); i <= n; ++i) read(a[i]);
for (int i(1); i < n; ++i) if ((a[i] + a[i + 1]) % 2 == 0) ++res;
cout << res << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
read(T);
while (T--) work();
return 0;
}