P8271 [USACO22OPEN] COW Operations S （思维）

P8271 [USACO22OPEN] COW Operations S

思维题

遇到不明白的操作，尝试在纸上模拟操作过程，找到性质。

第一种操作目前没有什么特别的，有一个它不会改变字符的奇偶性。重点是第二个。我们容易发现 CO->W->OC 这样的过程，它实现了相邻位置的互换，这个性质正是冒泡排序的过程，所以字符的排列不再重要。

有了这个性质，操作一中的相邻也可以去掉。

现在可以考虑什么时候合法了。容易发现只有两种情况：

1. C 为奇数，O 和 W 都为偶数。
2. C 为偶数，O 和 W 都为奇数。

预处理每个字符的前缀和即可。复杂度 \(O(n)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int c[N], o[N], w[N];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::string s;
	std::cin >> s;

	s = "#" + s;
	int n = s.length();
	for (int i = 1; i <= n; i++) {
		c[i] = c[i - 1] + (s[i] == 'C');
		o[i] = o[i - 1] + (s[i] == 'O');
		w[i] = w[i - 1] + (s[i] == 'W'); 
	}	

	int q;
	std::cin >> q;
	while(q--) {
		int l, r;
		std::cin >> l >> r;

		int C = c[r] - c[l - 1], O = o[r] - o[l - 1], W = w[r] - w[l - 1];
		if(((C & 1) && !(O & 1) && !(W & 1)) || (!(C & 1) && (O & 1) && (W & 1))) std::cout << "Y";
		else std::cout << "N";
	}

	return 0;
}