【每日一题】补档 ABC308E - MEX

题目内容

原题链接

给定一个长度为 n n n 的数组 a a a ，一个长度为 n n n 的只包括 M,E,X 的字符串。

统计满足 i < j < k i<j<k i<j<k，且 s[i]='M',s[j]='E',s[k]='X' 对应的 mex(a[i],a[j],a[k]) 之和。

数据范围

1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 1≤n≤2⋅105
0 ≤ a i ≤ 2 0\leq a_i \leq 2 0≤ai​≤2
s i ∈ { ′ M ′ , ′ E ′ , ′ X ′ } s_i\in \{'M', 'E', 'X'\} si​∈{′M′,′E′,′X′}

题解

从后往前做或者从后往前均可。

以从后往前为例，

• 遇到 M ，增加 0/1/2 的次数
• 遇到 E ，增加对应的 00,01,02,10,11,12,20,21,22 的次数
• 遇到 X ，统计所有可能，只需要枚举 00,01,02,10,11,12,20,21,22 的次数 ，然后计算乘上 mex 即可。

时间复杂度： O ( n ) O(n) O(n)

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int h[3];
int get(int x, int y, int z) {
    memset(h, 0, sizeof h);
    h[x] += 1;
    h[y] += 1;
    h[z] += 1;
    int res = 0;
    while (res < 3 && h[res] > 0) res += 1;
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    string s;
    cin >> s;

    vector<ll> one(3);
    vector<ll> two(9);

    ll ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == 'X') {
            one[a[i]] += 1;
        } else if (s[i] == 'E') {
            for (int j = 0; j < 3; ++j)
                two[a[i] * 3 + j] += one[j];
        } else {
            for (int j = 0; j < 3; ++j)
                for (int k = 0; k < 3; ++k) {
                    ans += two[j * 3 + k] * get(a[i], j, k);
                }
        }
    }

    cout << ans << "\n";

    return 0;
}