璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


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 由 温婕莺