AT2395 [ARC071C] TrBBnsformBBtion 题解

题目大意

有两个只包含 \(A\) 和 \(B\) 的字符串，给出两种操作

• A 可以变为 BB , B 可以变为 A ；
• AAA 可以消去， BBB 也可以消去。

思路

找规律。

这里我们以 A 为主，将 B 全部变为 A 。因为可以无限次操作，那么就代表如果两个字符串可以相等，那么他们就一定能够经过转化后变成同一个字符串，不会因为操作的限制导致不相等。

那么我们假设有一个串是 AABB ,那么他就可以转化成 AAAAAA 或者是 AAA ；相同的， BBB 可以转化成 AAAAAA 或者是 AAA :由此我们可以发现，在全部转化为一个字母后,如果两个串转化后可以相等，那么两个串全部转化为 A 后模 \(3\) 同余。

既然 A 和 B 的个数已经固定，并且题目让你求的是大串中的字串是否相等，那么我们就把 A 的值设为 \(1\) , B 的值设为 \(2\)，给一个前缀和数组来记录即可，这样我们就可以实现 \(\mathcal{O(1)}\) 的查询了。

代码实现

#include<bits/stdc++.h>
const int L=1e5+5;
using namespace std;

string a,b;
int A[L],B[L],oriA[L],oriB[L];/*ori数组记录原A和B代表的值，A B数组是前缀和数组*/
int q,Al,Ar,Bl,Br;

int main()
{
	ios::sync_with_stdio(false);
	cin >> a >> b;
	for(int i=0;i<a.size();i++)
	{
		if(a[i] == 'A') oriA[i+1]=1;/*A为1，B为2*/
		else oriA[i+1]=2;
	}
	for(int i=0;i<b.size();i++)/*同理*/
	{
		if(b[i] == 'A') oriB[i+1]=1;
		else oriB[i+1]=2;
	}
	for(int i=1;i<=a.size();i++) A[i]=A[i-1]+oriA[i];
	for(int i=1;i<=b.size();i++) B[i]=B[i-1]+oriB[i];/*记录前缀和*/
	cin >> q;
	for(int i=1;i<=q;i++)
	{
		cin >> Al >> Ar >> Bl >> Br;
		if((A[Ar]-A[Al-1]) % 3 == (B[Br]-B[Bl-1]) % 3) cout << "YES" << endl;/*查询*/
		else cout <<"NO"<<endl;
	}
}