搭建网站开发网站环境,书店网站建设人员分配,南宁网站推广营销,wordpress自动排版P8271 [USACO22OPEN] COW Operations S 奶牛操作 文章目录 P8271 [USACO22OPEN] COW Operations S 奶牛操作[USACO22OPEN] COW Operations S题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示分析code [P8271
USACO22OPEN] COW Operations S - 洛谷 | 计算机科学教…P8271 [USACO22OPEN] COW Operations S 奶牛操作 文章目录 P8271 [USACO22OPEN] COW Operations S 奶牛操作[USACO22OPEN] COW Operations S题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示分析code [P8271
USACO22OPEN] COW Operations S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) [USACO22OPEN] COW Operations S
题目描述
Bessie 找到了一个长度不超过 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105 且仅包含字符 ‘C’‘O’ 和 ‘W’ 的字符串 s s s。她想知道是否可以使用以下操作将该字符串变为单个字母 ‘C’她最喜欢的字母 选择两个相邻相等的字母并将其删除。 选择一个字母将其替换为另外两个字母的任一排列。
求出这个字符串本身的答案对 Bessie 而言并不足够所以她想要知道 s s s 的 Q Q Q 1 ≤ Q ≤ 2 ⋅ 1 0 5 1\le Q\le 2\cdot 10^5 1≤Q≤2⋅105个子串的答案。
输入格式
输入的第一行包含 s s s。
第二行包含 Q Q Q。
以下 Q Q Q 行每行包含两个整数 l l l 和 r r r 1 ≤ l ≤ r ≤ ∣ s ∣ 1\le l\le r\le |s| 1≤l≤r≤∣s∣其中 ∣ s ∣ |s| ∣s∣ 表示 s s s 的长度。
输出格式
输出一个长为 Q Q Q 的字符串如果第 i i i 个子串可以被转变则第 i 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 ∣ ≤ 5000 |s|\le 5000 ∣s∣≤5000 以及 Q ≤ 5000 Q\le 5000 Q≤5000。测试点 5-11 没有额外限制。
分析
因为一个字符可以转化成两个字符串一个字符串也可以转化成另外的一个字母所以原来的字符串的顺序对答案没有影响。
所以我们对于一个字符串把它转化成 C 0 / 1 O 0 / 1 W 0 / 1 C 0/1\ \ O 0/1 \ \ W 0/1 C0/1 O0/1 W0/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;
}
