CF1777A题解

• 分析

  发现操作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;
}