Edu-179-E. Changing the String · znzryb
## 思路讲解
感觉每次选择都可能有后效性怎么办？
```
// 碰到b,a c,a operate 在最近的位置
// a,b a,c not operate
// b,c c,b operate or not?
```
仔细一想那，这道题目也没有那么复杂其实，其实只有b，c是需要考虑是否操作的。
只考虑那么一种情况的话，其实就看后面有没有c，a，而且b的前面c的数量啦。
[https://www.cnblogs.com/fwdzh/p/18909502](https://www.cnblogs.com/fwdzh/p/18909502)
这个题解告诉我们，我们是不可能在线处理的，这个难度是比较大的，但是我前面一直在想这个（QAQ）。
## AC代码
[https://codeforces.com/contest/2111/submission/322930903](https://codeforces.com/contest/2111/submission/322930903)
::: 源代码
```cpp
// Problem: E. Changing the String
// Contest: Codeforces - Educational Codeforces Round 179 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2111/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
// #define getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do { sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << " " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x)) // vec中大于x的数有几个
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
using arc2=array<char,2>;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT;
/*
*/
// arc2 opC[MAXN];
set<ll> g[50]; // 直接懒得上有序表了，直接用vector 吧 开摆
inline void solve(){
cin>>N>>Q;
FOR(i, 0, 50-1) g[i].clear();
// g[0].clear();g[1].clear();g[2].clear();
// set<arc2> opC;
string s;
cin>>s;
// FOR(i,0,SZ(s)-1){
// g[s[i]-'a'].pb(i);
// }
FOR(i,1,Q){
char x,y;
cin>>x>>y;
g[(x-'a')*5+y-'a'].insert(i);
}
// 碰到b,a c,a operate 在最近的位置
// a,b a,c not operate
// b,c c,b operate or not?
FOR(i,0,N-1){
if(s[i]=='a'){
continue;
}
// 2 'c' -> 'a' 'c'->'b'->'a' 'c'->'b'
if(s[i]=='c'){
char x='c',y='a';
ll idx=(x-'a')*5+y-'a';
if(!g[idx].empty()){
// g[idx].pop_front(); // 后面的操作是需要b->c->a组合，所以尽量删前面的
g[idx].erase(g[idx].begin());
s[i]='a';
}else{
ll idx2=('c'-'a')*5+'b'-'a',idx3=('b'-'a')*5;
if(g[idx2].empty()) continue;
if(g[idx3].empty()){
// g[idx2].pop_back();
g[idx2].erase(prev(g[idx2].end()));
s[i]='b';
}else{
if(*g[idx2].begin()<*g[idx3].rbegin()){
// g[idx2].pop_front();
auto it=g[idx3].lower_bound(*g[idx2].begin());
g[idx2].erase(g[idx2].begin());
g[idx3].erase(it);
s[i]='a';
}else{
// g[idx2].pop_back();
// s[i]='b';
g[idx2].erase(g[idx2].begin());
s[i]='b';
}
}
}
}else{ // 1'b'->'a' 'b'->'c'->'a'
char x='b',y='a';
ll idx=(x-'a')*5+y-'a';
// if(!g[idx].empty()){
// g[idx].pop_front(); // 后面的操作是需要'c'->'b'->'a'组合，所以尽量删前面的
// s[i]='a';
// }else{
// ll idx2=('b'-'a')*5+'c'-'a',idx3=('c'-'a')*5;
// if(g[idx2].empty()) continue;
// if(g[idx3].empty()){
// // g[idx2].pop_back();
// // s[i]='b';
// }else{
// if(g[idx2].front()<g[idx3].back()){
// g[idx2].pop_front();
// g[idx3].pop_back();
// s[i]='a';
// }else{
//
// }
// }
// }
if(!g[idx].empty()){
// g[idx].pop_front(); // 后面的操作是需要'c'->'b'->'a'组合，所以尽量删前面的
g[idx].erase(g[idx].begin());
s[i]='a';
}else{
ll idx2=('b'-'a')*5+'c'-'a',idx3=('c'-'a')*5;
if(g[idx2].empty()) continue;
if(g[idx3].empty()){
// g[idx2].pop_back();
g[idx2].erase(prev(g[idx2].end()));
s[i]='b';
}else{
if(*g[idx2].begin()<*g[idx3].rbegin()){
// g[idx2].pop_front();
auto it=g[idx3].lower_bound(*g[idx2].begin());
g[idx2].erase(g[idx2].begin());
g[idx3].erase(it);
s[i]='a';
}
}
}
}
}
cout<<s<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--){
solve();
}
// solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2111/submission/322930903
*/
```
:::
## 心路历程（WA，TLE，MLE……）
那么我们发现，匹配应该是这样匹配，而不是用最大的匹配最小的。
```cpp
if(*g[idx2].begin()<*g[idx3].rbegin()){
// g[idx2].pop_front();
auto it=g[idx3].lower_bound(*g[idx2].begin());
g[idx2].erase(g[idx2].begin());
g[idx3].erase(it);
s[i]='a';
}
```