Atcoder Beginner Contest 379 题解

发表于 更新于 分类于 阅读次数： 本文字数： 7.5k
C题WA了九发，赛后发现忘排序了。

Toyota Programming Contest 2024#11（AtCoder Beginner Contest 379）题解

A

题意

给定一个只有三个数字的字符串“abc”，输出“bca”和“cab”。

题解

不要读取数字，直接当作字符或者字符串读取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    string s;
    cin >> s;
    cout << s[1] << s[2] << s[0] << " ";
    cout << s[2] << s[0] << s[1] << "\n";
}

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

B

题意

你有\(n\)颗牙，给定它们的好坏程度。如果能吃一颗草莓的话需要连续\(k\)颗牙都是好牙，并且吃掉一颗草莓后这\(k\)颗牙都会变成烂牙，求最多能吃多少颗草莓。

题解

贪心即可。

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

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int cnt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'O') {
            cnt++;
        } else {
            cnt = 0;
        }
        if (cnt == k) {
            cnt = 0;
            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

题意

\(n\)个格子按照1~\(n\)的顺序排列好，给定\(m\)个位置\(x_i\)，在这些位置对应的格子上有\(a_i\)个石子，现在可以把一个位置的石头向它后一个位置移动（记为一步），求让所有位置都恰好有一个石头需要多少步，否则输出-1代表无解。

题解

首先注意题意是恰有一个石子，那么肯定需要满足所有石子的总数为\(n\)​，否则无解。

然后一定要注意本题的\(a_i\)和\(x_i\)不是按照从左到右的顺序给出的，需要排序。

由于只能把石头向后移动，所以第一个位置肯定是需要石子的，通过思考可以发现本题其实步数是固定的，否则放多放少都不能满足条件。我们不妨维护第一个现有的石子不能满足条件的位置，遍历的过程中每移动到一个位置，这个位置就不能在维护的位置右边，否则无解。考虑计算答案：直接把当前位置的石子尽可能向右拓展，让维护的位置扩大，那么一个区间内放置石子所需要的步数其实是等差数列。我们记\(idx\)是我们维护的第一个现有的石子不能满足条件的位置，当前位置为\(i\)，那么等差数列的首项是\(idx - x_i\)，公差为1，相数为\(a_i\)，那么可以根据已知首项和公差、相数的等差数列求和公式得出需要把答案加上\(a_i(idx - x_i) + a_i*(a_i-1)/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
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i].first;
    }
    for (int i = 0; i < m; i++) {
        cin >> a[i].second;
    }
    int ans = 0;
    int check = 1;
    int sum = 0;
    sort(a.begin(), a.end());
    for (int i = 0; i < m; i++) {
        sum += a[i].second;
    }
    if (sum != n) {
        cout << -1 << "\n";
        return;
    }
    for (int i = 0; i < m; i++) {
        int x = a[i].first, v = a[i].second;
        if (x <= check) {
            ans += v * (check - x) + v * (v - 1) / 2;
            check += v;
        } else {
            cout << -1 << "\n";
            return;
        }
    }
    cout << ans << "\n";
}

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

D

题意

给定\(q\)次操作，每次操作进行以下三种情况之一：1. 种下一颗植物（高度记为0），2. 时间流逝\(t\)，所有种下的植物也长高\(t\)，3. 给定高度\(h\)采摘高度至少为\(h\)的植物并输出数量（这些植物被移除）。

题解

我们直接使用map记录下每个时间对应种下的植物个数即可，同时记录下当前的时间time，那么高度就是time减去刚种下的时间。询问时由于map是有序的，我们直接遍历统计答案即可。

注意map遍历时是不会访问未添加的元素的，而我们对于已添加的元素，即使再设为0还是会访问，这样会破坏复杂度。因此我们必须选择erase方法来清除键值对。但是不能在auto遍历里使用，否则会干扰迭代。因为erase后会返回清除的迭代器的下一个迭代器，我们手动使用迭代器遍历即可。

由于不停地在清除，所以时间复杂度并不高。

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

void solve() {
    int q;
    cin >> q;
    int time = 0;
    map<int, int> mp;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            mp[time]++;
        } else if (op == 2) {
            int t;
            cin >> t;
            time += t;
        } else {
            int h;
            cin >> h;
            int ans = 0;
            for (auto it = mp.begin(); it != mp.end();) {
                if (time - it->first >= h) {
                    ans += it->second;
                    it = mp.erase(it);
                } else {
                    break;
                }
            }
            cout << ans << "\n";
        }
    }
}

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

E

题意

给定一个全是0～9的数字的字符串，长度为\(n\le 2\times 10^5\)，记\(f(l,r)\)是字符串把\(l\)到\(r\)位置看成的数字，求： \[ \sum_{i=1}^N\sum_{j=1}^Nf(i,j) \]

题解

自然这类题需要推式子：把字符串记为\(s = a_1a_2...a_n\)，同时由于\(n\)很大，我们需要用数组存储答案的每一位。 \[ \begin{align*}&\sum_{i=1}^N\sum_{j=1}^Nf(i,j)\\\\ &=\sum_{l=1}^N\sum_{r=l}^N\sum_{i=l}^r10^{r-i}a_i\\\\ &=\sum_{i=1}^Na_i\sum_{l=1}^i\sum_{r=l}^N10^{r-i}\\\\ &=\sum_{i=1}^Nia_i\sum_{r=i}^N10^{r-i}\\\\ &=\sum_{i=1}^Nia_i\sum_{r=i}^N(10^0+10^1+...+10^{n-1})\\\\ &=a_1(10^0+10^1+...+10^{n-1})+2a_2(10^0+10^1+...+10^{n-2})+...\\\\ &+ia_i(10^0+10^1+...+10^{n-i})+na_n(10^0)\end{align*} \] 因此我们对于每一位\(10^i\)，都可以求出对应的\(ia_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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int sum = 0;
    vector<int> a(n), ans(n + 10);
    for (int i = 0; i < n; i++) {
        a[i] = s[i] - '0';
        sum += (i + 1) * a[i];
    }
    for (int i = 0; i < n; i++) {
        ans[i] = sum;
        sum -= (n - i) * a[n - i - 1];
    }
    int len = 0;
    for (int i = 0; i < n + 10; i++) {
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
        if (ans[i]) {
            len = i;
        }
    }
    for (int i = len; i >= 0; i--) {
        cout << ans[i];
    }
    cout << "\n";
}

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

F

题意

给定\(n\)座楼和它们的高度\(h_i\)，如果\(i\)能看见\(j\)（\(i<j\)），需要满足\(i,j\)之间不存在比\(j\)高的楼。现在给定\(q\)次询问，每次询问给定两个位置\(l,r\)，求第\(r+1\)到\(n\)座有多少座能被\(l,r\)同时看见。

题解

对于一座楼来说，我们关心的是比它高的楼，这可以用单调栈来处理。

接下来，我们考虑两座楼同时能看见需要满足什么条件。发现\(r\)右边的楼能被\(l\)看见，需要满足\(l,r\)之间的最高楼的高度小于等于\(r\)右边的楼。那么我们考虑将\(q\)次询问按照右端点从右到左的顺序排序从而离线处理。

我们从右到左维护一个单调栈（从栈顶到栈底是非递减的），那么对于每一次询问，我们都可以知道\(r\)能够看见的所有楼。我们只需要在这个单调栈里找到第一个比\(l,r\)之间最高的楼还高（或相等）的楼。

对于找到区间最值，我们想到了ST表处理，而要找到第一个大于条件的数，我们自然想到了在单调栈中二分。不过这里的单调栈是从左到右递减的，我们的二分策略需要相应调整一下，应该为上取整，满足条件后更新左边界。

除此之外，我们还需要特判一些情况：比如单调栈中没有比最高楼还高的楼，此时答案是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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct ST {
    const int n, k;
    vector<int> in1;
    vector<vector<int>> Max;
    ST(int n) : n(n), in1(n + 1), k(log2(n)) {
        Max.resize(k + 1, vector<int>(n + 1));
    }
    void init() {
        for (int i = 1; i <= n; i++) {
            Max[0][i] = in1[i];
        }
        for (int i = 0, t = 1; i < k; i++, t <<= 1) {
            const int T = n - (t << 1) + 1;
            for (int j = 1; j <= T; j++) {
                Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
            }
        }
    }
    int getMax(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = log2(r - l + 1);
        return max(Max[k][l], Max[k][r - (1 << k) + 1]);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> h(n), res(q);
    vector<vector<int>> query(q, vector<int>(3));
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    ST st(n);
    for (int i = 0; i < n; i++) {
        st.in1[i + 1] = h[i];
    }
    st.init();
    for (int i = 0; i < q; i++) {
        cin >> query[i][0] >> query[i][1];
        query[i][0]--, query[i][1]--;
        query[i][2] = i;
    }
    sort(query.begin(), query.end(),
         [&](const vector<int>& i, const vector<int>& j) {
             if (i[1] != j[1]) {
                 return i[1] > j[1];
             }
             return i[0] > j[0];
         });
    int last = n - 1;
    vector<int> stk;
    for (int i = 0; i < q; i++) {
        int l = query[i][0], r = query[i][1], idx = query[i][2];
        for (int j = last; j > r; j--) {
            while (!stk.empty() && h[j] > h[stk.back()]) {
                stk.pop_back();
            }
            stk.push_back(j);
        }
        if (stk.empty()) {
            res[idx] = 0;
            continue;
        }
        int mx = st.getMax(min(l + 2, n), min(r + 1, n));
        int lo = 0, hi = stk.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (h[stk[mid]] >= mx) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        if (h[stk[lo]] < mx) {
            lo--;
        }
        res[idx] = lo + 1;
        last = r;
    }
    for (int i = 0; i < q; i++) {
        cout << res[i] << "\n";
    }
}

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