Educational Codeforces Round 179 (Rated for Div. 2)

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

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. const int N=2e5+10;
5. int T,n,q;
6. string s;
7. char x,y;
8. void init()
9. {
10. }
11. void solve()
12. {
13.         set<int> ba,ca,bc,cb;
14.         cin>>n>>q;
15.     init();
16.         cin>>s;
17.         s=" "+s;
18.         for(int i=1;i<=q;i++)
19.         {
20.                 cin>>x>>y;
21.                 if(x=='a') continue;
22.                 if(x=='b'&&y=='a') ba.insert(i);
23.                 if(x=='c'&&y=='a') ca.insert(i);
24.                 if(x=='b'&&y=='c') bc.insert(i);
25.                 if(x=='c'&&y=='b') cb.insert(i);
26.         }
27.         for(int i=1;i<=n;i++)
28.         {
29.                 if(s[i]=='a') continue;
30.                 if(s[i]=='b')
31.                 {
32.                         if(ba.size())
33.                         {
34.                                 s[i]='a';
35.                                 ba.erase(ba.begin());
36.                                 continue;
37.                         }
38.                         if(bc.size()&&ca.size())
39.                         {
40.                                 set<int>::iterator it=ca.lower_bound(*bc.begin());
41.                                 if(it==ca.end()) continue;
42.                                 s[i]='a';
43.                                 bc.erase(bc.begin());
44.                                 ca.erase(it);
45.                         }
46.                 }
47.                 if(s[i]=='c')
48.                 {
49.                         if(ca.size())
50.                         {
51.                                 s[i]='a';
52.                                 ca.erase(ca.begin());
53.                                 continue;
54.                         }
55.                         if(cb.size())
56.                         {
57.                                 if(ba.size())
58.                                 {
59.                                         set<int>::iterator it=ba.lower_bound(*cb.begin());
60.                                         if(it!=ba.end())
61.                                         {
62.                                                 s[i]='a';
63.                                             cb.erase(cb.begin());
64.                                             ba.erase(it);
65.                                             continue;
66.                                         }
67.                                 }
68.                                 s[i]='b';
69.                                 cb.erase(cb.begin());
70.                         }
71.                 }
72.         }
73.         for(int i=1;i<s.length();i++)
74.         cout<<s[i];
75.         cout<<endl;
76. }
77. signed main()
78. {
79.     ios::sync_with_stdio(false);
80.     cin.tie(0);cout.tie(0);
81.         cin>>T;
82.         while(T--) solve();
83. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告