CF1821 A Matching

代码实现

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
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const int pow10[] = {1, 10, 100, 1000, 10000, 100000};

    int T;
    cin >> T;
    while(T--){
        string s;
        cin >> s;
        if (s[0] == '0'){
            cout << 0 << '\n';
            continue;
        }
        int cnt = count(s.begin(), s.end(), '?');
        if (s[0] == '?') cout << 9 * pow10[cnt - 1] << '\n';
        else cout << pow10[cnt] << '\n';
    }

}

CF1821 B Sort the Subarray

代码实现

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
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 1), b(n + 1);
        vector<int> pre(n + 2), suf(n + 2);
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) cin >> b[i];
        pre[0] = suf[n + 1] = 1;
        for(int i = 1; i <= n; i++) 
            pre[i] = suf[i] = (a[i] == b[i]);
        for(int i = 1; i <= n; i++)
            pre[i] &= pre[i - 1];
        for(int i = n; i >= 1; i--) 
            suf[i] &= suf[i + 1];
        int l = 0, r = -1;
        for(int i = 1; i <= n; i++){
            int j = i;
            while(j + 1 <= n && b[j + 1] >= b[j]) j++;
            if (pre[i - 1] && suf[j + 1] && j - i + 1 > r - l + 1){
                l = i, r = j;
            }
            i = j;
        }
        cout << l << ' ' << r << '\n';
    }

}

CF12821C Tear It Apart

分析

先预处理出来所有长度的序列需要多少步才能清空,然后枚举最后剩的字母计算答案即可,显然操作的数量之和同字母之间的最长距离有关.

代码实现

代码实现

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
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const int N = 2e5;
    vector<int> f(N + 1);
    for(int i = 1; i <= N; i++)
        f[i] = f[i / 2] + 1;

    int T;
    cin >> T;
    while(T--){
        vector<vector<int> > pos(26, {-1});
        string s;
        cin >> s;
        for(int i = 0; i < s.size(); i++){
            int c = s[i] - 'a';
            pos[c].push_back(i);
        }
        int ans = s.size();
        for(auto &v : pos){
            v.push_back(s.size());
            int res = 0;
            for(int i = 1; i < v.size(); i++){
                int len = v[i] - v[i - 1] - 1;
                res = max(res, f[len]);
            }
            ans = min(ans, res);
        }
        cout << ans << '\n';
    }

}