题解：P8271 [USACO22OPEN] COW Operations S

yr409892525 · 2025-08-18 11:52:22 · 题解

题解：P8271 [USACO22OPEN] COW Operations S

发现 CO -> W -> OC，这说明相邻两个字符可以交换。

也就可以推广到任意两个字符可以交换。

利用第一条消除规则，任意两个相同都可以消除。

再根据可以交换这个原则，最后只剩下 8 种情况。

经过枚举只有 C 和 OW 这两种情况满足条件。

消除，可以直接使用异或。

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2e5 + 5;

string s;
int q, a[kMaxN];

int main() {
  cin >> s;
  for (int i = 1; i <= s.size(); i++) {
    a[i] = a[i - 1] ^ (s[i - 1] == 'C' ? 1 : (s[i - 1] == 'O' ? 2 : 4));
  }
  cin >> q;
  for (int l, r; q--;) {
    cin >> l >> r;
    cout << ((a[r] ^ a[l - 1]) == 1 || (a[r] ^ a[l - 1]) == 6 ? "Y" : "N");
  }
  return 0;
}