P8271 [USACO22OPEN] COW Operations S 奶牛操作
目录[P8271 USACO22OPEN] COW Operations S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
[USACO22OPEN] COW Operations S
题目描述
Bessie 找到了一个长度不超过 \(2 \cdot 10^5\) 且仅包含字符 'C'，'O' 和 'W' 的字符串 \(s\)。她想知道是否可以使用以下操作将该字符串变为单个字母 'C'（她最喜欢的字母）：
-
选择两个相邻相等的字母并将其删除。
-
选择一个字母，将其替换为另外两个字母的任一排列。
求出这个字符串本身的答案对 Bessie 而言并不足够，所以她想要知道 \(s\) 的 \(Q\)（\(1\le Q\le 2\cdot 10^5\)）个子串的答案。
输入格式
输入的第一行包含 \(s\)。
第二行包含 \(Q\)。
以下 \(Q\) 行每行包含两个整数 \(l\) 和 \(r\)（\(1\le l\le r\le |s|\)，其中 \(|s|\) 表示 \(s\) 的长度）。
输出格式
输出一个长为 \(Q\) 的字符串，如果第 \(i\) 个子串可以被转变则第 \(i\) 个字符为 'Y'，否则为 'N'。
样例 #1
样例输入 #1
COW
6
1 1
1 2
1 3
2 2
2 3
3 3
样例输出 #1
YNNNYN
提示
【样例解释】
第一个询问的答案是「是」，因为 s 的第一个字符已经等于 'C'。
第五个询问的答案是「是」，因为 s 的第二到第三个字符组成的子串 OW 可以通过两步操作变为 'C'：
OW
-> CWW
-> C
这个样例字符串 COW 的其他子串均不能被转变为 'C'。
【测试点性质】
- 测试点 2-4 满足 \(|s|\le 5000\) 以及 \(Q\le 5000\)。
- 测试点 5-11 没有额外限制。
分析
因为一个字符可以转化成两个字符串，一个字符串也可以转化成另外的一个字母，所以原来的字符串的顺序对答案没有影响。
所以我们对于一个字符串，把它转化成 \(C 0/1\ \ O 0/1 \ \ W 0/1\) 的形式，再判断枚举就好了。
实现时可以用一个前缀和。
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 2e5 + 5;
int n , ans , ans1[N] , slen , l , r , flg , mp[N][4] , a[4];
char s[N] , s1[N];
int main () {
int tot;
scanf ("%s" , s + 1);
slen = strlen (s + 1);
fu (i , 1 , slen) {
fu (j , 1 , 3) mp[i][j] = mp[i - 1][j];
if (s[i] == 'C') mp[i][1] ++;
else if (s[i] == 'O') mp[i][2] ++;
else mp[i][3] ++;
}
int T;
scanf ("%d" , &T);
while (T --) {
scanf ("%d%d" , &l , &r);
fu (i , 1 , 3) a[i] = mp[r][i] - mp[l - 1][i];
fu (i , 1 , 3) a[i] %= 2;
if (a[1]) {
if (!a[2] && !a[3]) printf ("Y");
else printf ("N");
}
else {
if (a[2] && a[3]) printf ("Y");
else printf ("N");
}
}
return 0;
}