Martian148's blog
martian148
2024-08-06
目录

Educational Codeforces Round 168 (Rated for Div. 2) A-E

Educational Codeforces Round 168 (Rated for Div. 2) (opens new window)

# A - Strong Password

# Solution

找到两个相同的往里面插入一个不同的即可

# Code

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

void solve() {
    string s; cin >> s;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == s[i - 1]) {
            string t = s;
            char c = s[i] == 'a' ? 'b' : 'a';
            t.insert(t.begin() + i, c);
            cout << t << '\n';
            return;
        }
    }
    char c = s[0] == 'a' ? 'b' : 'a';
    cout << c << s << '\n';
}

int main() {
    // freopen ("A.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    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

# B - Make Three Regions

# Solution

找到这样一个区块

...
x.x
1
2

说明在第一行的中间可以放置一个

然后交换一二行再跑一次

# Code

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

int calc(vector<int> a, vector<int> b, int n) {
    int res = 0;
    for (int i = 2; i + 1 <= n; i++) {
        if (a[i] == 0 && a[i - 1] == 0 && a[i + 1] == 0)
        if (b[i] == 0 && b[i - 1] == 1 && b[i + 1] == 1)
            res += 1;
    }
    return res;
}

void solve() {
    int n; cin >> n;
    vector<int> a(n + 2, 0), b(n + 2, 0);
    a[0] = a[n + 1] = b[0] = b[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
        char x; cin >> x;
        if (x == 'x') a[i] = 1;
        else a[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        char x; cin >> x;
        if (x == 'x') b[i] = 1;
        else b[i] = 0;
    }
    int ans = calc(a, b, n) + calc(b, a, n);
    cout << ans << '\n';
}

int main() {
    freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    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

# C - Even Positions

# Solution

贪心得想，左括号和右括号肯定越近越好

所以对于一个 _ 如果里面的左括号较多，我们放置左括号，否则放置右括号，然后我们把右括号的位置塞入一个栈中

对于一个给定的右括号，如果前面的左括号个数不够了，就需要把栈内的一个右括号变成左括号来弥补左括号较少的情况

最后 O(n)O(n) 计算结果即可

# Code

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

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int cnt = 0;
    stack<int> st;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') cnt += 1;
        else if (s[i] == '_') {
            if (cnt > 0) {
                s[i] = ')'; cnt -= 1; st.push(i);
            }
            else {
                cnt += 1; s[i] = '(';
            }
        }
        else if (s[i] == ')') {
            cnt -= 1;
            if (cnt < 0) {
                int pos = st.top(); st.pop();
                s[pos] = '(';
                cnt += 2;
            }
        }
    }
    while (cnt < 0) {
        int pos = st.top(); st.pop();
        s[pos] = '(';
        cnt += 2;
    }
    while (!st.empty()) st.pop();
    long long ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') st.push(i);
        else {
            int pos = st.top(); st.pop();
            ans += i - pos;
        }
    }
    cout << ans << '\n';
}

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    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

# D - Maximize the Root

# Question

你将得到一棵有根树，共有 nn 个顶点。树中的顶点编号从 11 到 nn，根是顶点 11。在第 ii 个顶点上写有值 aia_i。

您可以执行以下操作任意次数（可能为零）：选择一个至少有一个子节点的顶点 vv；将 ava_v 增加 11；并将 vv 的子树中的所有顶点 uu（除 vv 本身外）的 aua_u 减少 11。但是，在每次操作后，所有顶点上的值应为非负数。

您的任务是计算使用上述操作可能写在根上的最大可能值。

# Solution

显然二分答案，考虑如何 check

对于一个 mid，根节点和 mid 的差为 dd，那么就需要把子树都减少 dd

对于一个节点，如果前面减少了 prepre，当前节点的值为 a[u]a[u] ，那么 uu 的子树就需要减少 pre−a[u]pre-a[u]

这样递归处理，直到处理到叶子节点即可

# Code

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

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int cnt = 0;
    stack<int> st;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') cnt += 1;
        else if (s[i] == '_') {
            if (cnt > 0) {
                s[i] = ')'; cnt -= 1; st.push(i);
            }
            else {
                cnt += 1; s[i] = '(';
            }
        }
        else if (s[i] == ')') {
            cnt -= 1;
            if (cnt < 0) {
                int pos = st.top(); st.pop();
                s[pos] = '(';
                cnt += 2;
            }
        }
    }
    while (cnt < 0) {
        int pos = st.top(); st.pop();
        s[pos] = '(';
        cnt += 2;
    }
    while (!st.empty()) st.pop();
    long long ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') st.push(i);
        else {
            int pos = st.top(); st.pop();
            ans += i - pos;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    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

# E - Level Up

# Question

Monocarp 从等级 11 开始游戏。他即将与 nn 只怪物进行战斗，按照从 11 到 nn 的顺序。第 ii 只怪物的等级为 aia_i

对于给定顺序中的每只怪物，Monocarp 的遭遇如下：

  • 如果 Monocarp 的等级严格高于怪物的等级，则怪物会逃跑；
  • 否则，Monocarp 会与怪物战斗。

在每次与怪物战斗 kk 次后，Monocarp 的等级会增加11

给出 qq 个查询

  • ixi~x：如果参数kk等于 xx ，Monocarp 是否会与第ii只怪物战斗（或者这只怪物会逃跑）

# Solution

可以说，根号分治非常强大

首先，肯定要把询问离线下来，按照 kk 分组

对于一个 kk 如果 k≤Bk \le B 那么直接暴力跑就好了

如果 k>Bk>B，那么总的等级数不会超过 nB\frac{n}{B}，我们可以开 nB\frac{n}{B} 个前缀和 pre[j][i]pre[j][i] 表示 表示前 ii 个数中大于 jj 的数的个数

那么对于每个询问，假设我们现在的位置是 pospos，等级为 nownow，那么我们下一个升级的位置就是 第一个满足 pre[j][i]>=pre[now][pos]+kpre[j][i]>=pre[now][pos]+k 的位置，显然可以二分得出，这部分的时间复杂度是个调和计数，大约为 O(nlog⁡2n)O(n\log^2n)

取 B=1000B=1000 可以通过此题

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

constexpr int M = 300, B = 1000;

void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> pre(M, vector<int>(n + 1, 0)); // pre[j][i] 表示前 i 个数中大于 j 的数的个数
    for (int j = 0; j < M; j++)
        for (int i = 1; i <= n; i++) 
            pre[j][i] = pre[j][i - 1] + (a[i] > j); 
    
    vector<vector<pair<int, int>>> ask(n + 1);
    vector<int> ans(q + 1, 0);
    for (int i = 1; i <= q; i++) {
        int id, k; cin >> id >> k;
        ask[k].push_back({id, i});
    }

    for (int k = 1; k <= n; k++) {
        if (ask[k].empty()) continue;
        sort(ask[k].begin(), ask[k].end());

        if (k <= B) {
            int now = 1, cnt = 0, it = 0;
            for (int i = 1; i <= n; i++) {
                while (it < ask[k].size() && ask[k][it].first == i) {
                    ans[ask[k][it].second] = a[i] >= now;
                    ++it;
                }
                if (a[i] >= now && ++cnt == k) ++now, cnt = 0;
            }
        }
        else {
            int pos = 0, now = 0, it = 0;
            while (pos <= n) {
                pos = lower_bound(pre[now].begin(), pre[now].end(), pre[now][pos] + k) - pre[now].begin();
                // 跳到第一个大于 pre[now][pos] + k 的位置
                now += 1;
                while (it < ask[k].size() && ask[k][it].first <= pos) {
                    ans[ask[k][it].second] = a[ask[k][it].first] >= now;
                    ++it;
                }
            }
        }
    }

    for (int i = 1; i <= q; i++) cout << (ans[i] ? "YES" : "NO") << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    int T; T = 1;
    while (T--) solve();
    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
52
53
54
55
56
57
58
上次更新: 2024/10/30, 18:42:16
Codeforces Round 933 (Div. 3) A-G
Codeforces Round 969 (Div. 2)

← Codeforces Round 969 (Div. 2)→

最近更新
01
逻辑学
12-13
02
中华传统文化
12-12
03
欧拉回路
11-14
更多文章>
Theme by Vdoing | Copyright © 2024-2024 Martian148 | MIT License