Educational Codeforces Round 147 (Rated for Div. 2)

发表于 分类于 ，

Educational Codeforces Round 147 (Rated for Div. 2)

Complete problemset

A. Matching

题意

给出最多5个字符的字符串。求0~9以及?组成。

其中?可以表示匹配任何数。

问有多少种无前导0的匹配数。

思路

当字符串第一个字符为0，则没有匹配方式。

若第一个字符是?，则这个?只能匹配9个数。

其余的?可以匹配10个数。然后根据乘法原理累乘即可。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    string s;
    cin >> s;
    int n = s.size();
    if (s[0] == '0') {
        cout << "0\n";
        return;
    }
    int ans;
    if (s[0] == '?') {
        ans = 9;
        for (int i = 1; i < n; i++) {
            if (s[i] == '?')
                ans *= 10;
        }
    } else {
        ans = 1;
        for (int i = 0; i < n; i++) {
            if (s[i] == '?')
                ans *= 10;
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

B. Sort the Subarray

题意

对于一个数组$a$，我们选取数组中的一个子数组$a[l..r]$将其排好序而其余不变，形成一个新的数组$a’$

现在已知$a$和$a’$。求最大r-l的l和r。多个答案可以选一个输出。

思路

我们用双指针。

设指针 $l = 0, r = n-1$

首先从左至右找到第一个使得$a[l] \ne a’[l]$的l。

然后从右至左找到第一个使得$a[r] \ne a’[r]$的r。

显然$a[l..r]$是一个合法的解，我们可以让尝试让l减小，r增大。

我们记录$a[l..r]$中的最大值和最小值。

当$a[l-1]$比最小值更小，则l可以减少，并更新最小值；当$a[r+1]$比最大值更大，则r可以增加，并更新最大值。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto& i : a)
        cin >> i;
    for (auto& i : b)
        cin >> i;
    if (a == b) {
        cout << "1 " << n << "\n";
        return;
    }
    int l = 0, r = n - 1;
    while (a[l] == b[l])
        l++;
    while (a[r] == b[r])
        r--;
    while (l > 0 && b[l - 1] <= b[l])
        l--;
    while (r < n - 1 && b[r] <= b[r + 1])
        r++;
    cout << l + 1 << " " << r + 1 << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

C. Tear It Apart

题意

给出一个字符串，全由小写英文字母组成。

每一次操作，你可以选择一些互不相邻的位置，并将这些位置的字符移除，然后形成一个新的字符串。

问最少需要多少次操作可以使得字符串中的字符全一致。

思路

我们可以考虑枚举保留哪一个字符。

不妨设保留了a字符。在除了a字符外，其余字符形成了一些子串。设第i个子串的长度为$len_i$，每一次操作，每个子串移除的字符数最多是$\lceil\frac{len_i}{2} \rceil$。

每个子串可以同步移除，实际上只需要考虑最长的子串移除需要多少步就行了。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    string s;
    cin >> s;
    int n = s.size();
    int ans = n;
    for (char i = 'a'; i <= 'z'; i++) {
        int mx = 0;
        for (int j = 0; j < n;) {
            int p = j;
            while (p < n && s[p] != i)
                p++;
            mx = max(mx, p - j);
            j = p + 1;
        }
        int tans = 0;
        while (mx) {
            mx /= 2;
            tans++;
        }
        ans = min(ans, tans);
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

D. Black Cells

题意

现在有一个有白色单元格租场的长带条。

有一个按钮，当按下时当前的指针所指向的单元格会变为黑色。

当前位置在0单元格。我们每次操作可以执行以下三种操作种的一个：

  • 指针右移动，位置+1
  • 按住按钮
  • 松开按钮

我们现在有m个区间，我们只能在这些区间内进行着色。这些区间不会重叠。

当需要让k个单元格变为黑色，我们最少需要操作多少次？

思路

贪心

我们发现区间长度大于2的区间必须要涂色。

如果操作了a次，但是有一个长度为3的区间没有涂色。此时，为其涂色，会发现我们向移动的总步数减少了3，而区间涂色需要花费按压和松开两步操作，所以总操作次数成为了$a-3+2$，显然是要优于a的。

而对于区间长度恰好为2的区间上色不会让答案更劣。

我们可以尽可能多的选择区间长度大于1的区间进行上色。

现在遍历每个区间$[l_i, r_i]$，$i$从1开始。

记s为遍历到当前区间所有的长度大于1的区间，记c为长度为1的区间的个数。

若$s\ge k$则说明全部对大于1的区间涂色便可以满足要求。操作数由右移动次数+按压次数组成。右移次数是$r_i-(s-k)$，按压次数是长度大于1区间的个数$i-c$。

否则，若$s+c\ge k$，可以全选长度大于1的区间，外加k-s个长度为1的区间进行涂色可以满足要求。长度大于1的区间有$i-c$个，总按压次数是$(i-c) * 2 + (k-s) *2$，需要右移动到$r_i$

遍历过程中维护答案的最小值即可。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, k;
    cin >> n >> k;
    vector<ll> L(n), R(n);
    for (ll& i : L)
        cin >> i;
    for (ll& i : R)
        cin >> i;
    ll s = 0, c = 0, ans = 2e9 + 7;
    for (int i = 0; i < n; i++) {
        if (R[i] - L[i] == 0)
            c++;
        else
            s += R[i] - L[i] + 1;
        if (s >= k) {
            ans = min(ans, R[i] - (s - k) + 2 * (i + 1 - c));
        } else if (s + c >= k) {
            ans = min(ans, R[i] + 2 * (i + 1 - c + k - s));
        }
    }
    if (ans == 2e9 + 7) {
        cout << "-1\n";
    } else {
        cout << ans << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

E. Rearrange Brackets

题意

思路

代码

1
2


F. Timber

题意

思路

代码

1
2