【信息奥赛实训】Week1——STL 与基础数据结构专题训练

【信息奥赛实训】Week1-Lab-STL

作者｜Rickyの水果摊

时间｜2022年11月20日

---

实训概要

实训专题

STL 与基础数据结构专题训练

实训目的

• 掌握STL常用的算法、容器、容器适配器的使用方法。
• 能够利用STL的算法、容器、容器适配器求解问题。

题目列表

• A：摘苹果
• B：立方和
• C：计算个数
• D：后缀表达式的值
• E：做蛋糕
• F：查资料
• G：明明的随机数

题解

A：摘苹果

【题目名称】摘苹果

【题目描述】

苹果树上有 $n$ 个苹果，每个苹果的高度分別为 $h_1,h_2,\dots ,h_n$。

你拥有一个非常方便的摘苹果工具，每次可以把指定高度上的所有苹果全部摘下来。

你打算摘 $q$ 次，第 $i$ 次摘高度为 $a_i$ 的所有苹果。

问每次可以摘到多少个苹果？

【输入】

第一行包含两个正整数 $n,q(1\le n\le 10^6,1\le q\le 2\ast 10^5)$，分别表示苹果的数量和摘苹果的次数。

第二行包含 $n$ 个正整数 $h_1,h_2,\dots ,h_n(1\le h_i\le 10^9)$，分别表示每个苹果的高度。

其后 $q$ 行，第 $i$ 行包含一个正整数 $a(1\le a_i\le 10^9)$，表示当次要摘的苹果的高度。

【输出】

对于每次摘苹果的操作，在一行内输出一个整数，表示这一次摘到的苹果的数量。

【输入样例】

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

【输出样例】

3
2
0
0
1
2
3
4

---

【题目分析】

本题考查 STL 中的 map ，只需统计每个高度的苹果数，然后采摘时输出即可，难度较低。

另外题目输入量较大，使用 cin读入优化 可以有效减少时间。

【 C++ 代码】：

#include

using namespace std;
int n, q, tmp;
map mp;

int main() {
    ios::sync_with_stdio(false); //cin读入优化
    cin.tie(0);

    cin >> n >> q;
    mp.clear();
    for (int i = 0; i < n; ++i) {
        cin >> tmp;
        mp[tmp]++;   //该高度苹果数量累加
    }

    for (int i = 0; i < q; ++i) {
        cin >> tmp;
        cout << mp[tmp] << endl;  //输出该高度苹果总数
        mp[tmp] = 0;    //清零当前高度苹果数
    }

    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：立方和

【题目名称】立方和

【题目描述】

给你一个正整数 $x$，问是否存在至少一对正整数对 $(a,b)$ 满足 $a^3+b^3=x$?

【输入】

第一行包含一个正整数 $T(1\le T\le 100)$，表示测试数据组数。

每组数据占一行，包含一个正整数 $x(1\le x\le 10^{12})$。

【输出】

对于每组数据，如果存在至少一对 $(a,b)$ 满足题意，输出 YES，否则输出 NO

【输入样例】

6
1
2
3
8
9
8567958184
1
2
3
4
5
6
7

【输出样例】

NO
YES
NO
NO
YES
YES
1
2
3
4
5
6

---

【题目分析】

本题有两种思路：

1. 由于 x 最大不超过 $10^{12}$，故 $a,b$ 的范围在 $[1,10^4]$，因此可以对 $a$ 枚举，对 $b$ 用二分，实测可以 AC。（但是不能 $a,b$ 均枚举，会超时）
2. 可以先将所有 $a^3$ 存入容器中，然后枚举 $b$ ，看 $x-b^3$ 是否在容器中，若有，则有解。

🍉 PS1：使用 vector 会超时，因为在 vector 中查找元素，时间复杂度为 $O(N)$；而在 set、map 中，查找的时间复杂度为 $O(logN)$，时间会大大降低。

🍉 PS2：本题数据上限很大，已经超出了 int 类型的范围，需要使用 long long 类型。（ 1ll 是 1 的 long long 形式，任何 int 类型数据 * 1ll 后均能转换为 long long 类型）

【 C++ 代码】

思路1：

#include

using namespace std;
typedef long long ll;
ll T, tmp, flag;

ll f(ll a, ll b);

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> T;
    while (T--) {
        cin >> tmp;
        flag = 0;

        for (ll a = 1; a <= 10001; ++a) {  //对a枚举
            ll b, res = 0, mid;
            ll l = a;
            ll r = 10001;

            while (l <= r) {  //对b二分
                mid = l + (r - l) / 2;
                res = f(a, mid);
                if (res == tmp) {
                    b = mid;
                    flag = 1;
                    break;
                } else if (res < tmp) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
          
            if (flag) break;  //已找到，退出a的枚举
        }
      
        if (flag) cout << "YES" << endl;  //输出结果
        else cout << "NO" << endl;
    }
    return 0;
}

ll f(ll a, ll b) {
    return a * a * a + b * b * 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
39
40
41
42
43
44
45
46
47
48

思路2：

AC 版 ✅

#include

using namespace std;
typedef long long ll;

int T, flag;
ll x;
set s;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    for (int i = 1; i <= 10001; ++i) {
        s.insert(1ll * i * i * i);   //向s中存入所有可能的a^3
    }

    cin >> T;
    while (T--) {
        flag = 0;
        cin >> x;
        for (ll b = 1; b * b * b < x; b++) {   //枚举b
            if (s.count(x - 1 * b * b * b) == 1) {  //查看(x-b^3)是否在set中
                flag = 1;
                break;
            }
        }
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    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

vector 超时版 ❌

#include

using namespace std;
typedef long long ll;
int T, flag;
ll x;
vector v;
vector::iterator it;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    for (int i = 1; i <= 10001; ++i) {
        v.push_back(1ll * i * i * i);   //1ll是1的long long 形式
    }

    cin >> T;
    while (T--) {
        flag = 0;
        cin >> x;
        for (ll b = 1; 1ll * b * b * b < x; b++) {
            //使用vector查找时会超时
            it = find(v.begin(), v.end(), x - 1ll * b * b * b);
            if (it != v.end()) {
                flag = 1;
                break;
            }
        }
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    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

---

C：计算个数

【题目名称】计算个数

【题目描述】

给定一个正整数 n，你可以执行以下操作：

• 不做处理
• 在当前数的左侧拼接一个正整数。如果此前尚未拼接过，则拼接的正整数不能超过原数 n 的一半，否则不能超过上一次被拼接的数的一半。拼接完成后，可以继续按照此规则继续处理，直到不能再加正整数为止，或者不做处理。

问总共能处理出多少种正整数？

【输入】

输入仅一个正整数 $n(1\le n\le 1000)$。

【输出】

输出一个整数，表示能被处理出来的数字的种类数。

【输入样例】

4
6
8
1
2
3

【输出样例】

4
6
10
1
2
3

---

【题目分析】

本题考查 递推 思想。

以题目中的 8 为例，f(8) 代表 8 拼接后的总个数。

f(8) = f(4) 的个数与 8 拼 + f(3) 的个数与 8 拼 + f(2) 的个数与8拼 + f(1) 的个数与8拼，即 f(8) = f(4) + f(3) + f(2) + f(1)。

因此从 递推 角度，从前往后推，即可得到每一个 f(n) 拼接后的个数

【 C++ 代码】：

#include

using namespace std;
typedef long long ll;
const int NMAX = 1005;
int n, tmp;
ll f[NMAX];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    f[1] = 1;
    for (int i = 2; i < NMAX; ++i) {
        f[i] = 1;
        for (int j = 1; j <= i / 2; ++j) {
            f[i] += f[j];
        }
    }

    while (cin >> n) {
        cout << f[n] << endl;
    }
    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

---

D：后缀表达式的值

【题目名称】后缀表达式的值

【题目描述】

从键盘读入一个后缀表达式（字符串），只含有 0-9 组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。

每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。

【输入】

一个后缀表达式，以 @ 作为结束标志。

数据保证输入的运算数均是正整数，且每个数值在运算过程中均不会超过 int 所表示的范围。

除法当作整除即可。

【输出】

输出一个整数，表示后缀表达式的值。

【输入样例】

16 9 4 3 +*-@
1

【输出样例】

-47
1

---

【题目分析】

本题考查 STL 中的 stack ，需要在理解 后缀表达式 的基础上，利用 stack 书写相应代码

后缀表达式 相关知识点博客：http://t.csdn.cn/vvkbP

🍉 PS：本题数据的读取推荐使用 scanf，cin 在读取单个字符时，会跳过空格，而 scanf不会

【 C++ 代码】：

#include

using namespace std;
stack s;
char c;
int sum, tmp;

int main() {

    while (scanf("%c", &c)) {   //利用scanf，每次读取一个字符（包括空格）
        if (c == '@') {
            break;
        
        //遇到数字，继续读入
        } else if (c >= '0' && c <= '9') { 
            tmp = tmp * 10 + c - '0';
          
        //遇到空格，将当前数字元素入栈
        } else if (c == ' ') {   
            s.push(tmp);
            tmp = 0;
          
        //遇到运算符，进行运算
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            //弹出主栈顶元素num2（主栈顶元素放在操作符右边）和次栈顶元素num1
            int num2 = s.top();
            s.pop();
            int num1 = s.top();
            s.pop();
          
            //计算
            if (c == '+') num2 = num1 + num2;
            else if (c == '-') num2 = num1 - num2;
            else if (c == '*') num2 = num1 * num2;
            else if (c == '/') num2 = num1 / num2;
          
            //将计算后的元素再次入栈
            s.push(num2);
        }
    }
  
    cout << s.top() << endl;  //当前栈顶元素即为运算结果
    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

---

E：做蛋糕

【题目名称】做蛋糕

【题目描述】

你是一家蛋糕店的老板，这一天你接到了 $N$ 张蛋糕订单。

店内有充足的原材料（奶油、淀粉、鸡蛋）可以用于制作蛋糕，每种原材料按份存储，每份都有一个美味度。已知第 $i$ 份订单的蛋糕需要使用 $x_i$ 份奶油、$y_i$ 份淀粉以及 $z_i$ 份鸡蛋制作。

作为店长，你决定按顺序每次取目前最好的材料制作蛋糕。换句话说，你会按订单的给定顺序制作蛋糕，对于第一份蛋糕，会使用美味度最高的 $x_i$ 份奶油、$y_i$ 份淀粉以及 $z_i$ 份鸡蛋进行制作；对于第二份蛋糕，会使用剩下的美味度最高的 $x_2$ 份奶油、$y_2$ 份淀粉以及 $z_2$ 份鸡蛋进行制作；以此类推。

已知一份蛋糕的美味度等同于所有使用掉的原材料的美味度之和，问每份蛋糕的美味度分别是多少？

【输入】

第一行包含三个正整数 $X,Y,Z(1\le X,Y,Z\le 10^5)$，分别表示店内一开始拥有的奶油、淀粉以及鸡蛋的份数。

第二行包含 $X$ 个正整数，表示每份奶油的美味度。

第三行包含 $Y$ 个正整数，表示每份淀粉的美味度。

第四行包含 $Z$ 个正整数，表示每份鸡蛋的美味度。

第五行包含一个正整数 $N(1\le N\le min(X,Y,Z))$，表示订单的数量。

其后 $N$ 行，每行包含三个正整数 $x_i,y_i,z_i(1\le x_i,y_i,z_i\le 10)$，分别表示制作每份订单的蛋糕所需要使用的奶油、淀粉及鸡蛋的份数。

• 每份材料的美味度是一个不超过 $10000$ 的正整数。
• 数据保证 $\sum x_i\le X,\sum y_i\le Y,\sum z_i\le Z$

【输出】

输出 $N$ 行，每行包含一个正整数，表示每份订单的蛋糕的美味度。

【输入样例】

3 4 5
3 1 4
1 5 9 2
6 5 3 5 8
2
1 1 1
1 2 3
1
2
3
4
5
6
7

【输出样例】

21
26
1
2

---

【题目分析】

本题可以使用 STL 中的很多容器，若选择 vector、deque 等，只需读入数据后，用 sort() 对其降序排序即可；若选择 priority_queue，其默认形式为 大顶堆，符合题目要求，较为推荐。

【 C++ 代码】：

#include

using namespace std;
int X, Y, Z, N, tmp, x, y, z;
priority_queue qx;  //定义3个优先队列，默认为大顶堆，美食度高的元素排在队首
priority_queue qy;
priority_queue qz;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    //读入店铺食材库存
    cin >> X >> Y >> Z;
    for (int i = 0; i < X + Y + Z; ++i) {
        cin >> tmp;
        if (i < X)
            qx.push(tmp);  //食材根据美味度入队
        else if (i < X + Y)
            qy.push(tmp);
        else
            qz.push(tmp);
    }

    //读入订单
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int sum = 0;   //每个订单的美食度
        cin >> x >> y >> z;
        for (int j = 0; j < x + y + z; ++j) {
            if (j < x) {
                sum += qx.top();   //根据订单要求，选择食材（食材出队）
                qx.pop();
            } else if (j < x + y) {
                sum += qy.top();
                qy.pop();
            } else {
                sum += qz.top();
                qz.pop();
            }
        }
        cout << sum << endl;
    }

    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

---

F：查资料

【题目名称】

【题目描述】

你忽然被布置了一篇论文，并且时间已经所剩无几！众所周知，写论文需要引用较多的参考文献，因此你需要花费一定的时间去网上寻找资料。

你需要按顺序查找一些资料，每份资料都可以用一个正整数表示。每次上网查找完资料后，你 都会 把这份资料存进你的电脑。

此后，如果你需要再次查找这份资料，并且发现电脑上存着这份资料，就不需要再花更多的时间上网找了。

但现在有一个新的问题，你的电脑容量不大够了，只能够让你存最多 $m$ 份资料。你认为新查到的资料总是比以前查的资料更有价值，因此每次你会把 最早 存入电脑的那份资料删除，腾出空间来存新的资料。

给定你要查询的资料的顺序，问你总共需要 上网查找 多少次？

初始时电脑上没有任何资料。

【输入】

第一行包含两个正整数 $n,m(1\le n,m\le 10^5)$，分别表示需要查找的次数以及电脑的最大容量。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots ,a_n(1\le a_i\le 5000)$，表示每次要查的资料。

【输出】

输出一个整数，表示需要上网查的次数。

【输入样例】

7 3
1 9 1 9 8 10 1
1
2

【输出样例】

5
1

---

【题目分析】

本题使用 STL 中的 deque，会比较方便。（本题涉及查询，而 容器适配器 queue 不支持查询，故推荐使用deque ）

【 C++ 代码】：

#include

using namespace std;
int n, m, tmp, cnt;
deque dq;
deque::iterator it;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cnt = 0;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> tmp;

        //查询当前资料是否在电脑中
        it = find(dq.begin(), dq.end(), tmp);
        if (it == dq.end()) { //当前电脑中未找到
            //查找次数+1
            cnt++;

            //将当前新资料放入电脑中
            if (dq.size() == m) {  //若电脑容量已满，弹出首资料
                dq.pop_front();
            }
            dq.push_back(tmp);
        }
    }
    cout << cnt << endl;
    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

---

G：明明的随机数

【题目名称】明明的随机数

【题目描述】

先用计算机生成了 $N$ 个 1 到 1000 之间的随机整数 $N\le 100$，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成 “去重” 与 “排序” 的工作。

【输入】

有 2 行，第 1 行为 1 个正整数，表示所生成的随机数的个数：$N$

第 2 行有 $N$ 个用空格隔开的正整数，为所产生的随机数。

【输出】

2 行，第 1 行为 1 个正整数M，表示不相同的随机数的个数。第 2 行为 $M$ 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

【输入样例】

10
20 40 32 67 40 20 89 300 400 15
1
2

【输出样例】

8
15 20 32 40 67 89 300 400
1
2

---

【题目分析】

本题考查 STL 中的 set ，set 容器自带 ”去重“ 和 ”排序“ 的效果，非常适合本题。

【 C++ 代码】：

#include

using namespace std;
int N, tmp;
set s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> tmp;
        s.insert(tmp);   //set容器默认升序
    }

    cout << s.size() << endl;
    for (auto t: s) {
        cout << t << " ";
    }
    cout << endl;

    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