算法练习专栏——牛客练习——牛客小白赛90

A:小A的文化节

链接

题目描述

​ 小A的学校举办了一年一度的文化节！

​ 在文化节中有 n 个项目，其中参加第 iii 个项目的欢乐度是 ai 。虽然小A很想把全部项目都体验一遍，但是她的时间是有限的，因此她只能参加其中的 m 个项目。

​

现在小A告诉你她参加了哪些项目，请你帮她计算一下她的欢乐度吧。

输入描述:

1
2
3
4
5
6
7
8
9
第一行两个正整数 n 和 m  (1≤m≤n≤100)，分别表示文化节总的项目数和小A参加的项目数。


第二行 n 个正整数，其中第 i 个数字 ai(1≤ai≤105) 表示参加第 iii 个项目得到的欢乐度。


第三行 m 个正整数，其中第 i 个数字 bi(1≤bi≤n) 表示小A参加了编号为 bi 的项目。

数据保证 bi 各不相同。

输出描述:

1
输出一行一个整数表示小A的欢乐度。

示例1

输入

复制

1
2
3
5 3
1 2 3 4 5
1 3 5

输出

复制

1
9

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
const int N = 110;
int a[N];
int n, m;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    int res = 0;
    while (m--) {
        int x;
        cin >> x;
        res += a[x];
    }
    
    cout << res;
    return 0;
}

B:小A的游戏

链接

题目描述

小A和小B在玩一个游戏，每局游戏的结果可能有胜平负三种。游戏的胜者得到 3 分，败者不得分，若打平则双方都得 1 分。

现在他们进行了若干局游戏，比分记录着小A为 X 分，小B为 Y 分。由于持续的时间太长了，他们不确定记录的比分是否是正确的了，请你来判断一下此时的比分是否合法吧。

输入描述:

1
2
3
4
5
多组测试。

第一行一个正整数 T  (1≤T≤103) ，表示测试数据组数。

接下来 T 行，每行两个整数 X 和 Y  (0≤X,Y≤109) ，分别表示比分所记录的小A和小B的分数。

输出描述:

1
对于每组测试，如果合法输出一行 "Yes" ，否则输出 "No"（均不包含引号）。

示例1

输入

复制

1
2
3
4
3
1 3
3 3
4 15

输出

复制

1
2
3
No
Yes
No

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N = 1010;
int T, n;
int a[N];

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> T;
    while (T--) {
        int x, y;
        cin >> x >> y;
        int a = x / 3, b = x % 3, aa = y / 3, bb = y % 3;
        if (b != bb) cout << "No\n";
        else cout << "Yes\n";
        
    }

    
    return 0;
}

C:小A的数字

链接

题目描述

小A给定一个数字 n ，请你帮她找出从低位对齐后任意一位均与 n 对应数位不同的最小正整数。

对于本题题面描述中的从低位对齐后任意一位均与 n 对应数位不同，你需要保证你所输出的答案的位数小于 n 的位数时，即使在添加前导零至与 n 的位数相同后，也不应有任意一位的数字两两相同。

输入描述:

1
2
3
4
5
6
7
多组测试。


第一行一个正整数 T  (1≤T≤103) ，表示测试数据组数。


对于每组测试数据，一行一个不含前导零的整数 n(2≤n≤109)n  ，表示所给的数字。

输出描述:

1
对于每组测试，输出一行一个正整数表示答案。

示例1

输入

复制

1
2
3
4
3
2
10
101

输出

复制

1
2
3
1
1
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
50
51
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int n, T;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> T;
    while (T--) {
        string s1, s;
        cin >> s;
        s1 = s;
        for (int i = 0; i < s1.length(); i++) {
            if (s1[i] != '0') s1[i] = '0';
            else {
                s1[i] = '1';
            }
        }
        if (s1.length() == 1) {
            if (s1 != "1") cout << "1";
            else if (s1 == "0") cout << "1";
            else if (s1 == "1") cout << "2";
            cout << '\n';
            continue;
        }
        bool flag = false;
        for (int i = 0; i < s1.length(); i++){
            if (s1[i] == '1' && !flag) {
                flag = true;
                cout << s1[i];
            } else if (!flag){
                continue;
            } else {
                cout << s1[i];
            }
        }
        if (!flag) {
            if (s[s.length() - 1] != '1') cout << "1";
            else if (s[s.length() - 1] == '0') cout << "1";
            else if (s[s.length() - 1] == '1') cout << "2";
        }
        cout << '\n';
    }
    
    
    
    return 0;
}

D:小A的线段（easy version）

链接

题目描述

​ 本题为 easy version ，与 hard version 的区别仅为m 的数据范围。

​ 在一个标有 1−n 的数轴上给定 m 条线段，第 iii 个线段的左右端点分别为 sti , edi ，求有多少种线段的选择方案可以使得数轴上的每个整数点至少被覆盖两次。

​ 定义两种选择方案不同当且仅当至少有一个线段在两种方案中的状态（选/不选）不同。

​ 由于方案数可能很多，所以你需要输出满足条件的方案数对 998244353 取模的结果。

输入描述:

1
2
3
第一行两个正整数 n  (2≤n≤105) 和 m  (1≤m≤10) ，分别表示数轴长度和线段个数。

接下来 m 行，每行两个正整数，其中第 iii 行的两个正整数 st 和 edi  (1≤sti<edi≤n) 分别表示第 i 条线段的起点和终点。

输出描述:

1
输出满足条件的方案数对 998244353 取模的结果。

示例1

输入

复制

1
2
3
4
5
5 4
4 5
1 5
3 5
1 4

输出

复制

1
3

思路

暴力模拟，实际上还是蛮明显的

代码（死亡暴力1000ms+）

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

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

#define l first
#define r second

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<PII> a(m);
    lop(i, 0, m)
    {
        cin >> a[i].l >> a[i].r;
        a[i].l --;
        a[i].r --;
    }
    int U = 1 << m;
    int ans = 0;
    lop(S, 1, U)
    {
        vector<bool> vis(m);
        lop(j, 0, m)
        {
            if(S >> j & 1)
                vis[j] = true;
        }
        bool flag = true;
        lop(j, 0, n)
        {
            int cnt = 0;
            lop(k, 0, m)
            {
                if(vis[k] and a[k].l <= j and j <= a[k].r)
                {
                    cnt ++;
                }
            }
            if(cnt < 2)
            {
                flag = false;
                break;
            }
        }
        if(flag)
        {
            ans += 1;
        }
    }
    cout << ans << el;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

代码（）

E:小A的任务

链接

题目描述

小A现在需要完成有序的 A 类任务和 B 类任务各 n 个，初始时只有第 1 个 A 类任务可以进行。进行第 i 个 A 类任务需在完成第 i − 1 个 A 类任务之后，进行第 i 个 B 类任务需要在完成第 iii 个 A 类任务之后。且在同一时刻只能进行 A 类和 B 类中的一类任务，同一类的任务只能同时进行一个，任何一个任务都至多完成一次。

总共有 q 次询问，每次询问你需要回答完成 k 个 B 类任务至少需要多长时间。

输入描述:

1
2
3
4
5
6
7
第一行两个整数 n  (1≤n≤105)n和 q  (1≤q≤100) ，分别表示任务个数与询问次数。

第二行 n 个整数，其中第 i 个数字 ai  (1≤ai≤109) 表示完成第 i 个 A 类任务所需要的时间。

第三行 n 个整数，其中第 i 个数字 bi  (1≤bi≤109) 表示完成第 i 个 B 类任务所需要的时间。

接下来 q 行，每行一个整数 k  (1≤k≤n) ，表示询问。

输出描述:

1
对于每次询问，输出一行一个整数，表示询问结果。

示例1

输入

复制

1
2
3
4
5
6
4 3
1 2 3 4
4 1 2 3
1
2
3

输出

复制

1
2
3
4
8
13

示例2

输入

复制

1
2
3
4
5
5 2
19 1 20 2 17
12 20 17 4 2
3
5

输出

复制

1
2
75
114

备注:

1
对于样例一的第一个询问，需要先完成前 2 个 A 类任务，再完成第 2 个 B 类任务。

思路

image-20240427001423744

代码

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

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

void solve()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    vector<int> a(n + 1), b(n + 1);
    vector<LL> pre(n + 1);
    lop(i, 0, n)
    {
        cin >> a[i];
    }
    pre[0] = a[0];
    lop(i, 1, n)
    {
        pre[i] = pre[i - 1] + a[i];
    }
    lop(i, 0, n)
    {
        cin >> b[i];
    }
    while (m--)
    {
        int k;
        cin >> k;
        priority_queue<int, vector<int>, less<int>> q;

        LL now = 0;
        LL ans;
        lop(i, 0, k)
        {
            now += b[i];
            q.push(b[i]);
        }
        ans = pre[k - 1] + now;

        lop(i, k, n)
        {
            if (b[i] < q.top())
            {
                now -= q.top();
                q.pop();
                q.push(b[i]);
                now += b[i];
                cmin(ans, now + pre[i]);
            }
        }
        cout << ans << el;
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}