USACO22OPEN-Silver C

前言（Front talk)

比较简单。（甚至想把这个题的前言删掉）

网址（Website）

洛谷： USACO22OPEN COW Operations S

SPOJ：题目详情 - COW Operations - Super

SPOJ：题解 - COW Operations - Super

题目（Problem）

找到了一个长度不超过且仅包含字符 ‘C’，’O’ 和 ‘W’ 的字符串。她想知道是否可以使用以下操作将该字符串变为单个字母 ‘C’（她最喜欢的字母）：

选择两个相邻相等的字母并将其删除。
选择一个字母，将其替换为另外两个字母的任一排列。

求出这个字符串本身的答案对而言并不足够，所以她想要知道的（）个子串的答案。

输入格式（Input）

输入的第一行包含。

第二行包含。

以下行每行包含两个整数和（，其中表示的长度）。

输出格式（Output）

输出一个长为的字符串，如果第个子串可以被转变则第个字符为 ‘Y’，否则为 ‘N’。

样例（Example）

样例输入

样例输出

YNNNYN

提示（Notice）

【样例解释】

第一个询问的答案是「是」，因为 s 的第一个字符已经等于 ‘C’。

第五个询问的答案是「是」，因为 s 的第二到第三个字符组成的子串 OW 可以通过两步操作变为 ‘C’：

   OW
-> CWW
-> C

这个样例字符串 COW 的其他子串均不能被转变为 ‘C’。

【测试点性质】

测试点满足以及。
测试点没有额外限制。

题解（Solution）

容易得到几个性质：

任两个字母可以交换
任两个不同字母可以合成一个字母
任两个相等字母可以抵消

然后直接记录三个字母的前缀数量，到时候直接差分求字母数，后判断剩下的能不能组成字母即可。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
inline int input(){int x;return cin>>x,x;}
const int N = 201234;
char a[N];
int n,q;

int c[N],o[N],w[N];

inline bool check(int l,int r){
	int C=(c[r]-c[l-1])%2;
	int O=(o[r]-o[l-1])%2;
	int W=(w[r]-w[l-1])%2;
	if(C==1 && O==0 && W==0) return true;
	if(C==0 && O==1 && W==1) return true;
	return false;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("cowoper");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>(a+1)>>q;
	n=strlen(a+1);
	For(i,1,n){
		c[i]=c[i-1],o[i]=o[i-1],w[i]=w[i-1];
		if(a[i]=='C') c[i]++;
		if(a[i]=='O') o[i]++;
		if(a[i]=='W') w[i]++;
	}
	while(q--){
		int l=input(),r=input();
		cout<<(check(l,r)?'Y':'N');
	}return 0;
}