题目描述
中文题目描述
每个字符串的长度为N,由A, B和C组成。
通过对X执行以下三种操作任意次数(可能为零),确定是否有可能使X与y重合。
操作(1):选择X中的字符C替换为字符A。
操作(2):在X中选择字符C替换为字符B。
操作(3):选择X中的子字符串AB,替换为BA。更正式地说,选择一个使x的第i和(i+1)个字符分别为A和B,并将前者替换为B,后者替换为A。
你有T个测试用例需要解决。
思路解析
最开始想的爆搜,过了1/5的数据。。。分数爆零。。。
1.先考虑没有C的情况,对于一个X串中的A,可以往后任意滑动(重点)
例如:ABB -> BAB ->BBA
ABAB -> BAAB -> BABA -> BBAA
那么对于没有C的情况只需比较X中每一个A的位置是否比Y中的A小即可
2.如果有C
先考虑Y中出现C,若Y中有C,则X对应位置必须有C,且X中的A遇到C时将无法向后滑动 ( 以Y中的C为分割点进行分割 )
再考虑X中不与Y中C对应的C,当X中的A不够时,可以用C来填补A(将C变成A,使X与Y中的A数量一致),其余C全部变成B,然后考虑X中所有A滑动对齐Y(贪心处理,将最前面的C变成A )
X串 : ACA C BAACB
Y串 : BAA C BAABA
合并考虑,将Y中的C作为分割点切割X,在分割X的每一个块中检查的A的数量(不够C来补),检查所有A能否滑动对齐
代码实现
敲代码时出现了vector使用中的经典错误。。。
Ax.size()会变化!!!
//A - Replace C or Swap AB /*每个字符串的长度为N,由A, B和C组成。 通过对X执行以下三种操作任意次数(可能为零),确定是否有可能使X与y重合。 操作(1):选择X中的字符C替换为字符A。 操作(2):在X中选择字符C替换为字符B。 操作(3):选择X中的子字符串AB,替换为BA。更正式地说,选择一个使x的第i和(i+1)个字符分别为A和B,并将前者替换为B,后者替换为A。 你有T个测试用例需要解决。 约束 1≤T≤2×10 5 1≤N≤2×10 5 */ #include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<algorithm> #define MAXN 200009 using namespace std ; int N , T ; vector<int> Ax , Ay , Cx ;//记录X,Y每个块中的A和C出现位置 string x , y ; bool flag ;//判断是否不可实现 void Clear() {//处理完一个块后清空 while( !Ax.empty() ) Ax.pop_back() ; while( !Ay.empty() ) Ay.pop_back() ; while( !Cx.empty() ) Cx.pop_back() ; } void check() { if( Ax.size()+Cx.size() < Ay.size() || Ax.size() > Ay.size() ) {//块中出现X的A加C不够,或者X中的A过多 flag = 1 ; return ; } int cnt = 0 ; while(Ax.size()<Ay.size()) {//贪心处理,将位置最小的C变成A Ax.push_back(Cx[cnt]) ; cnt ++ ; } /*for( int i = 0 ; i < Ay.size()-Ax.size() ; ++ i )//经典错误,错误原因在于Ax push_back后长度增加 Ax.push_back(Cx[i]) ; */ sort(Ax.begin(),Ax.end()); for( int i = 0 ; i < Ay.size() ; ++ i ) { if( Ax[i] > Ay[i] ) {//比较X中每个A是否都小于Y中的A,如果有不小于的,说明这个A无法滑动至与Y中的A对齐 flag = 1 ; return ; } } return ; } void Solve() { for( int i = 0 ; i < N ; ++ i ) { if( y[i] == 'C' ) { if( x[i] != 'C' ) { flag = 1 ; break ; } check() ; x[i] = 'D' ;//防止切割点C被纳入用于填充的C if( flag ) break; Clear() ; } if( y[i] == 'A' )//记录A的位置 Ay.push_back(i) ; if( x[i] == 'A' ) Ax.push_back(i) ; if( x[i] == 'C' )//记录C的位置 Cx.push_back(i) ; } check(); return ; } int main() { scanf("%d", &T ); for( int t = 1 ; t <= T ; ++ t ) { Clear() ; flag = 0 ; scanf("%d", &N ); cin >> x >> y ; Solve() ; if( flag == 1 ) printf("No\n"); else printf("Yes\n"); } }
标签:AtCoder,AB,Contest,back,flag,Ay,Ax,替换,size From: https://www.cnblogs.com/Nomad-Joe-violet/p/17754819.html