跳到主要内容

(xx)

· 阅读需 1 分钟

题意是对s1s1字符串操作最后得到s2s2，我们可以想到对s1s1的增加操作等价于对s2s2的减少操作

所以不断对两个字符串进行减少，比较减少后的字符串是否相同即可

AC代码
Details
#include<bits/stdc++.h>
using namespace std;
#define QAQ return 
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >

const int N=2e5+10;

inline string get( string s1 )
{
	string s2;
	for( auto &ch:s1 )
	{
		s2+=ch;
		if( s2.size() >= 4 && s2.substr( s2.size()-4,s2.size() ) == "(xx)" )
		{
			s2.erase( s2.size()-4,s2.size() );
			s2+="xx";
		}
	}
	QAQ s2;
}

inline void sovel()
{
	string s1, s2;
	cin>>s1>>s2;
	cout<<( get( s1 ) == get( s2 ) ? "Yes" : "No" )<<"\n";
}

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int t;
	for( cin>>t;t;t-- ) sovel();
	QWQ
}

时间复杂度：O(tn)O(tn)