自动搬运

查看原文

来自洛谷，原作者为

	yr409892525 Sun is HOPE.

搬运于2025-08-24 22:37:32，当前版本为作者最后更新于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;
}