Codeforces Round 994 + 990 题解

发表于 更新于 分类于 阅读次数： 本文字数： 7.7k
994 好多 mex，怎么每次 A 题都要读半天才懂呜呜呜。

Codeforces Round 990 (Div. 2) 题解

A

题意

一个人在 \(n\) 天涂格子，每天涂 \(a_i\) 个，它要涂成正方形，规则是：初始涂成边长为 1 的，然后再涂外面一圈（使得边长为 3 ），一直重复下去。如果一天涂完所有格子之后刚好是正方形，他就很高兴。输出高兴的天数。

题解

按照题意模拟，每次涂完之后，新的正方形边长就加二。

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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int sum = 0, ans = 0;
    int j = 1;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        while (sum > j * j) {
            j += 2;
        }
        if (sum == j * j) {
            ans++;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

给定一个字符串，你可以选择一个位置，把这个位置的字符变成另一个位置的字符，要求新的字符串的不同排列个数最少，输出新字符串。

题解

我们显然需要让相同的字符串尽可能多，而让单独的字符串尽可能少。因此把出现次数最少的字符替换为出现次数最多的即可。

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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int sum = 0, ans = 0;
    int j = 1;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        while (sum > j * j) {
            j += 2;
        }
        if (sum == j * j) {
            ans++;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

给定一个 \(2\times n\) 的矩阵，可以任意交换两列，然后从 \((1,1)\) 出发到达 \((2,n)\)，只能向下或向右移动，求能获得的最大分数。

题解

注意到只能向下移动一次，因此有一列是需要同时走上下两格的，我们让这一列最大，而其他列均取最大值即可。

但是要注意，可能很多列都存在最大值，因此更好的方法是枚举每一列都向下，其他列去最大值。

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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    vector<array<int, 2>> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0];
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i][1];
    }
    int ans = -2e9;
    for (int i = 1; i <= n; i++) {
        int res = 0;
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                continue;
            }
            res += max(a[j][0], a[j][1]);
        }
        ans = max(ans, res + a[i][0] + a[i][1]);
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给定一个数组，你可以进行下一操作任意次：选择一个位置，把该位置的数加一，然后放到末尾去，求操作后的最小字典序。

题解

一个事实是，最后的数组开头一定是原数组的最小值，因此在原数组的最小值的位置前面的数一定会被操作，后面的位置需要形成递增序列才能字典序最小，否则一定有更优的办法。

注意到每个数最多被操作一次，且跟操作顺序有关。如果对于一个数 \(a_i\) ，在它后面有更小的数，（即会形成逆序对）它一定会被操作。我们这样判断一次后，会有被标记的数（会形成逆序对）和不被标记的数。我们把不被标记的数单独拿成一个数组，但是这个数组不一定是升序的，举个例子：1 2 2 1 4，不被操作的数有 1 1 4，此时两个 2 放到最后，并不能符合条件，我们还需要一次遍历，使得不被标记的数都小于或等于之前被操作的数的最小值，再次标记一遍。然后排序即可。

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 <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<bool> vis(n + 1);
    int mn = 2e9, mnn = 2e9;
    for (int i = n; i >= 1; i--) {
        mn = min(a[i], mn);
        if (a[i] > mn) {
            a[i]++;
            vis[i] = true;
            mnn = min(mnn, a[i]);
        }
    }
    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " \n"[i == n];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Codeforces Round 994 (Div. 2) 题解

A

题意

给定一个数组，可以进行多次操作：选择一个子数组，把这个子数组换成它们的 \(\text{mex}\)，求把数组变成全是 0 的最少操作次数。

题解

特判全是 0 的情况。我们关注包含全部不是 0 的数的极小区间，这个区间如果有 0 ，答案就是 2，否则答案就是 1。

具体实现上，可以通过前缀和，枚举区间分割端点。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + (a[i] != 0);
    }
    if (accumulate(a.begin() + 1, a.end(), 0ll) == 0) {
        cout << 0 << "\n";
        return;
    }
    for (int i = 2; i < n; i++) {
        if (a[i] == 0 && pre[i] != 0 && pre[n] - pre[i] != 0) {
            cout << 2 << "\n";
            return;
        }
    }
    cout << 1 << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

给定一个字符串 \(s\)，字符只有 “p”、“s”、“.”，需要判断是否有满足条件的数组：数组本身是一个排列，对于位置 \(i\) ，如果 \(s_i\) 为 “p”，那么到 \(i\) 的前缀在数组中必须是一个排列；如果是“s”，到 \(i\) 的后缀必须是一个排列。

题解

由于排列的限制，首先可以注意到的是 “s” 必须在 “p” 的左边，否则就需要两个 1，不满足条件。其次，如果 “s”，“p” 同时存在的话，每个形成的区间之间必须是相互包含的关系，否则所用的数就会有冲突。因此，同时有 “s”，“p” 的话，至少要满足最左边的 “s“ 在最左边或者最右边的 “p” 在最右边。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    int ps = 0, pp = 0;
    for (int i = n; i >= 1; i--) {
        if (s[i] == 's') {
            ps = i;
            break;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'p') {
            pp = i;
            break;
        }
    }
    if (ps == 0 || pp == 0) {
        cout << "YES\n";
        return;
    }
    if (ps > pp || (ps != 1 && pp != n)) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

给定 \(n\) 个人，它们形成一个环，相邻的数彼此是朋友，再给出额外的一组朋友 \(x,y\)。构造一组数据 \(a_i\)，使得对于每个人，它的朋友的 \(\text{mex}\) 为自身。

题解

先不考虑额外的一组朋友，如果人数是偶数的话，可以 0 1 0 1 这样构造，否则可以2 1 0 1 0 1 0 这样构造。再考虑额外的一组朋友：偶数的话如果连接的两个数是 1 1 或 0 0，就都变成 2，否则无影响。奇数的话，同理，但是我们构造时可以固定 2 为 \(x\)，这样不会有任何变动。

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>
using namespace std;
#define int long long

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    if (x > y) {
        swap(x, y);
    }
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) {
        p[i] = (i % 2 == 1 ? 0 : 1);
    }
    if (n % 2 == 1) {
        p[x] = 2;
        int cnt = 1;
        for (int i = x + 1; i <= n; i++) {
            p[i] = (cnt % 2 == 1 ? 1 : 0);
            cnt++;
        }
        for (int i = 1; i < x; i++) {
            p[i] = (cnt % 2 == 1 ? 1 : 0);
            cnt++;
        }
    } else {
        if (p[x] == 1 && p[y] == 1) {
            p[x] = 2;
        }
        if (p[x] == 0 && p[y] == 0) {
            p[y] = 2;
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << p[i] << " \n"[i == n];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给定一个矩阵，你要从左上角走到右下角（只能向右或向下）走到一格需要花费该格的值，开始之前可以进行任意次操作：每次操作可以选择一行，将这行循环左移一次，但是需要花费 \(k\) 。求能花费的最小值。

题解

设 \(dp_{i,j,x}\) 为能走到 \((i,j)\) ，在第 \(i\) 行循环左移 \(x\) 次能获得的最大权重，注意到一行最多循环左移 \(m-1\) 次，否则就无用了，还会浪费值。那么对于每一行，我们枚举循环左移 \(x\) 次，状态转移就是向右走：\(dp_{i,j} = dp_{i,j-1} + a_{i,(j+x)}\)，向下走：\(dp_{i,j} = dp_{i-1,j} + a_{i,(j+x)} - kx\)，这里是循环左移的。

初始值应该设 \(dp_{0,1}\) 和 \(dp_{1,0}\) 为 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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(m + 1, vector<int>(m, 1e18)));
    vector<vector<int>> mdp(n + 1, vector<int>(m + 1, 1e18));
    mdp[0][1] = mdp[1][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int x = 0; x < m; x++) {
                auto get = [&](int i, int j, int x) {
                    if (j + x == m) {
                        return a[i][m];
                    }
                    return a[i][(j + x) % m];
                };
                dp[i][j][x] =
                    min(dp[i][j][x], mdp[i - 1][j] + k * x + get(i, j, x));
                dp[i][j][x] = min(dp[i][j][x], dp[i][j - 1][x] + get(i, j, x));
                mdp[i][j] = min(mdp[i][j], dp[i][j][x]);
            }
        }
    }
    cout << mdp[n][m] << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}