vp做四道
E. MEX
题意
给定一个字符串,其中每个字符都有一个权值,找到所有满足\(s_is_js_k=\)MEX
的三元组\((i,j,k)\),求所有三元组的mex之和。
思路
首先求出所有前缀的M字符的不同权值的数量,再求出所有后缀X字符的不同权值的数量,最后枚举字符串中所有的E,统计其mex之和。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = 505;
int mex(int x, int y, int z) {
for(int i = 0; i < 3; i++) {
if(x != i && y != i && z != i) return i;
}
return 3;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
string s;
cin >> s;
vector<vector<int>> l(n + 1, vector<int>(3));
vector<vector<int>> r(n + 1, vector<int>(3));
for(int i = 0; i < n; i++) {
l[i + 1] = l[i];
if(s[i] == 'M') l[i + 1][v[i]]++;
}
for(int i = n; i > 0; i--) {
r[i - 1] = r[i];
if(s[i] == 'X') r[i - 1][v[i]]++;
}
ll ans = 0;
for(int i = 0; i < n; i++) {
if(s[i] != 'E') continue;
for(int j = 0; j < 3; j++) {
for(int k = 0; k < 3; k++) {
ans += 1ll * mex(v[i], j, k) * l[i][j] * r[i][k];
}
}
}
cout << ans << "\n";
return 0;
}
- Beginner AtCoder Contest 308beginner atcoder contest 308 beginner atcoder 308e mex contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334