题解 P8271 [USACO22OPEN] COW Operations S

本文主要是介绍题解 P8271 [USACO22OPEN] COW Operations S，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

面对这种题目要大胆赋值。

考虑序列肯定可以不停操作，最后剩下可能是：空、C、O、W。

我们把空赋值为 \(0\)，COW 三个字母分别是 \(1,2,3\)。

操作 \(1\) 对应的是两个相等的数运算后得 \(0\)。操作 \(2\) 则是两个不相等的数运算后得到第三个数。还有一点是 \(0\) 和任何数运算得 \(0\)。

容易发现这就是异或运算！XOR 是具有交换律和结合律的，因此操作结果与顺序无关，就是所有字母的异或值。

所以就一下 XOR 前缀和，每次询问回答就行了。

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
int n,m; 
char a[N];
int s[N];

inline int read()
{
    int F=1,ANS=0;
	char C=getchar();
    while (C<'0'||C>'9')
	{
		if (C=='-') F=-1;
		C=getchar();
	}
    while (C>='0'&&C<='9')
	{
		ANS=ANS*10+C-'0';
		C=getchar();
	}
    return F*ANS;
}

int main()
{
	cin >> (a+1);
	n=strlen(a+1);
	m=read();
	for (int i=1;i<=n;i++)
	{
		if (a[i]=='C') s[i]=(s[i-1]^1);
		else if (a[i]=='O') s[i]=(s[i-1]^2);
		else s[i]=(s[i-1]^3);
	}
	for (int i=1;i<=m;i++)
	{
		int l=read(),r=read(),ans=s[r]^s[l-1];
		if (ans==1) printf("Y");
		else printf("N");
	}
	return 0;
}

这篇关于题解 P8271 [USACO22OPEN] COW Operations S的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！