牛客小白月赛90补题

过 4 题排名 441，比上次月赛难度低，题目对小白非常友好。给出题人点赞，先就补一下 E 题。

A

签到

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

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int main() {

    int n, m;
    cin >> n >> m;
    int a[N], b[N];

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;

    for (int i = 0; i < m; i++) {
        cin >> b[i];
        ans += a[b[i] - 1];
    }

    cout << ans << endl;
    return 0;
}

B

每局游戏的结果可能有胜平负三种，游戏的胜者得到 3分，败者不得分，若打平则双方都得 1分。
判断得分是否是对的
思路：abs(a-b) % 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int main() {

    int t, x, y;
    ll ans = 0;
    cin >> t;
    while (t--) {
        cin >> x >> y;
        int l = abs(x - y);
        if (l % 3 == 0) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

C

请你帮她找出从低位对齐后任意一位均与 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
43
44
45
#include <bits/stdc++.h>  
  
using namespace std;  
typedef long long ll;  
  
vector<int> getNums(int x) {  
    vector<int> ret;  
    while (x > 0) {  
        ret.push_back(x % 10);  
        x /= 10;  
    }    return ret;  
}  
  
void solve(int n) {  
    ll ans = 0;  
    vector<int> v, an;  
    v = getNums(n);  
    for (int j: v) {  
        if (j == 0) {  
            an.push_back(1);  
        } else {  
            an.push_back(0);  
        }    }    // remove tail 0  
    while (!an.empty() && an[an.size() - 1] == 0) {  
        an.pop_back();  
    }    // calc from an  
    for (int j = an.size() - 1; j >= 0; j--) {  
        ans *= 10;  
        ans += an[j];  
    }  
    if (ans == 0) {  
        if (v[0] == 1) {  
            ans = 2;  
        } else {  
            ans = 1;  
        }    }    cout << ans << endl;  
}  
  
int main() {  
    ll n, t;  
    cin >> t;  
    while (t--) {  
        cin >> n;  
        solve(n);  
    }}

D

暴力枚举就行

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
#include <bits/stdc++.h>  
  
using namespace std;  
typedef long long ll;  
const int MOD = 998244353;  
  
bool isValid(const vector<pair<int, int>> &s, int c, int n) {  
    vector<int> cov(n + 1, 0);  
    for (int i = 0; i < s.size(); i++) {  
        // 检查第i个线段是否被选中  
        // 选中的线段，将覆盖的点的覆盖次数加1  
        if (c & (1 << i)) {  
            for (int j = s[i].first; j <= s[i].second; j++) {  
                cov[j]++;  
            }        }    }    for (int i = 1; i <= n; i++) {  
        if (cov[i] < 2) return false;  
    }    return true;  
}  
  
int main() {  
    ll n, m, ans = 0;  
    cin >> n >> m;  
    vector<pair<int, int>> s(m);  
  
    for (int i = 0; i < m; i++) {  
        cin >> s[i].first >> s[i].second;  
    }    for (int i = 0; i < (1 << m); i++) {  
        if (isValid(s, i, n)) {  
            ans++;  
            ans %= MOD;  
        }    }    cout << ans << endl;  
    return 0;  
}

E 补题

Codeforces

巧妙的思路，因为 A 的 cost 是单调递增的，只需要去找后面更小的 B 就行了
用一个大根堆来维护最大值，先取前 K 个，然后在剩余的里面遍历，加入一个 b[i] 剩余就将堆里的一个最大值 pop，保证当前一定是 0-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
#include <bits/stdc++.h>  
  
using namespace std;  
typedef long long ll;  
  
int main() {  
    ll n, q;  
    cin >> n >> q;  
    vector<ll> a(n), b(n), preA(n + 1, 0);  
    for (ll i = 0; i < n; ++i) {  
        cin >> a[i];  
        preA[i + 1] = preA[i] + a[i];  
    }    for (ll i = 0; i < n; ++i) {  
        cin >> b[i];  
    }  
    while (q--) {  
        int k;  
        cin >> k;  
        // 1. get the sum of the first k A tasks  
        ll sum = preA[k] - preA[0], now = 0;  
        // pq is a max heap  
        priority_queue<int> pq;  
        // 2. pq push the first k B tasks  
        // now is the sum of the first k B tasks        for (int i = 0; i < k; i++) {  
            pq.push(b[i]);  
            now += b[i];  
        }        ll ans = now + sum;  
        // add [k, n) B tasks  
        for (int i = k; i < n; i++) {  
            sum += a[i];  
            pq.push(b[i]);  
            now += b[i];  
            now -= pq.top();  
            pq.pop();  
            ans = min(ans, now + sum);  
        }        cout << ans << endl;  
    }  
    return 0;  
}

F 补题