【每日一题】补档 ABC308E - MEX | 遍历保存 |简单

题目内容

原题链接

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

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

数据范围

$1\le n\le 2\cdot 10^5$
$0\le a_i\le 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)$

代码

#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51