Educational Codeforces Round 179 (Rated for Div. 2)

ABCD 略

E

以字符串的每个位置为对象来看。处理肯定是从低位到高位，我们从低位开始遍历，遇到a不用管，b我们看能不能到a，如果不能看能不能先到c再到a，c看能不能到a，如果不能看能不能到b，如果可以看还能不能到a。当执行两个操作时，要保证后一个操作存在一个位置再第一个操作之后，位置用set存。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int T,n,q;
string s;
char x,y;
void init()
{
}
void solve()
{set<int> ba,ca,bc,cb;cin>>n>>q;init();cin>>s;s=" "+s;for(int i=1;i<=q;i++){cin>>x>>y;if(x=='a') continue;if(x=='b'&&y=='a') ba.insert(i);if(x=='c'&&y=='a') ca.insert(i);if(x=='b'&&y=='c') bc.insert(i);if(x=='c'&&y=='b') cb.insert(i);}for(int i=1;i<=n;i++){if(s[i]=='a') continue;if(s[i]=='b'){if(ba.size()){s[i]='a';ba.erase(ba.begin());continue;}if(bc.size()&&ca.size()){set<int>::iterator it=ca.lower_bound(*bc.begin());if(it==ca.end()) continue;s[i]='a';bc.erase(bc.begin());ca.erase(it);}}if(s[i]=='c'){if(ca.size()){s[i]='a';ca.erase(ca.begin());continue;}if(cb.size()){if(ba.size()){set<int>::iterator it=ba.lower_bound(*cb.begin());if(it!=ba.end()){s[i]='a';cb.erase(cb.begin());ba.erase(it);continue;}}s[i]='b';cb.erase(cb.begin());}}}for(int i=1;i<s.length();i++)cout<<s[i];cout<<endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--) solve();
}