526互联

AtCoder Beginner Contest 308 - E

发布时间 2023-07-04 19:46:50作者: Qiansui

题目链接：abc 308
前四题简单就不放了

E - MEX

阿巴阿巴，比赛的时候想复杂了，一直在想怎么快速的统计27种mex的情况，啊，前面对后面的影响等等等，反正就是想复杂了
现在再想想，看了官方题解，从'E'出发，统计其前后各3种数字的个数，再用mex函数判答案，\(O(n)\)即可！
剩下的见代码吧，做完之后发现，没太大难度其实，还得自己多练

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*

*/
const int maxm=2e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,a[maxm],ans;
string ss;

ll mex(int x,int y,int z){
	for(int i=0;i<=2;++i){
		if(x!=i&&y!=i&&z!=i) return i;
	}
	return 3;
}

void solve(){
	ans=0;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	cin>>ss;
	vector<vector<ll>> m(n+5,vector<ll>(3,0)),x(n+5,vector<ll>(3,0));
	for(int i=1;i<=ss.size();++i){
		m[i]=m[i-1];
		if(ss[i-1]=='M') ++m[i][a[i]];
	}
	for(int i=ss.size();i>0;--i){
		x[i]=x[i+1];
		if(ss[i-1]=='X') ++x[i][a[i]];
	}
	for(int i=1;i<=ss.size();++i){
		if(ss[i-1]=='E'){
			for(int j=0;j<3;++j){
				for(int k=0;k<3;++k){
					ans+=m[i][j]*x[i][k]*mex(j,a[i],k);
				}
			}
		}
	}
	cout<<ans<<'\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}