Edu-179-E. Changing the String

思路讲解

感觉每次选择都可能有后效性怎么办？

// 碰到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

这个题解告诉我们，我们是不可能在线处理的，这个难度是比较大的，但是我前面一直在想这个（QAQ）。

AC代码

https://codeforces.com/contest/2111/submission/322930903

源代码

// 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……）

那么我们发现，匹配应该是这样匹配，而不是用最大的匹配最小的。

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';
}