icpc:problems:usaco22open_cow_operations_s
problems | |
---|---|
名称 | COW Operations S |
题目编号 | USACO22OPEN_S3 |
题目链接 | luogu.com.cn/… |
来源 | USACO |
算法分类 | 前缀和, 思维 |
难易程度 | 一般般 |
COW Operations S
想法
通过题目规则可知,o 可变为 wow 或 coc,则如果原串为 …ow… 通过 o → wow 操作,原串变为 …woww…,其中右侧的ww可合并,故原串变为 …wo…,可以发现通过操作可将任意两个字母交换位置且内容不变。所以可通过操作将所有字母均移动到一起,再消除。
统计o, w, c字母的出现次数,求 [l, r] 是否满足条件,检查 o 与 w 在区间中出现次数即可。
代码实现
#include<cstdio> #include<cstring> const int N = 2*1e5+10; int nc[N], no[N], nw[N]; char line[N]; int main() { scanf("%s", line+1); int len = (int)strlen(line+1); for(int i=1; i<=len; i++) { nc[i] = nc[i-1] + (line[i] == 'C' ? 1 : 0 ); no[i] = no[i-1] + (line[i] == 'O' ? 1 : 0 ); nw[i] = nw[i-1] + (line[i] == 'W' ? 1 : 0 ); } int q; scanf("%d", &q); while(q--) { int l, r; scanf("%d %d", &l, &r); int c, o, w; c = (nc[r] - nc[l-1])%2; o = (no[r] - no[l-1])%2; w = (nw[r] - nw[l-1])%2; if(c == 1 && o == 0 && w == 0) { printf("Y"); continue; } if(c == 0 && o == 1 && w == 1) { printf("Y"); continue; } printf("N"); } return 0; }
/app/www/public/data/pages/icpc/problems/usaco22open_cow_operations_s.txt · 最后更改: 2023/06/13 05:45 由 温婕莺