https://blog.csdn.net/qq_46025844/article/details/127948957
实训概要
实训专题
STL 与基础数据结构专题训练
实训目的
掌握STL常用的算法、容器、容器适配器的使用方法。
能够利用STL的算法、容器、容器适配器求解问题。
题目列表
A：摘苹果
B：立方和
C：计算个数
D：后缀表达式的值
E：做蛋糕
F：查资料
G：明明的随机数
题解
A：摘苹果
【题目名称】摘苹果
【题目描述】
苹果树上有 n nn 个苹果，每个苹果的高度分別为 h 1 , h 2 , … , h n h_{1},h_{2},\dots,h_{n}h
1
,h
2
,…,h
n
。
你拥有一个非常方便的摘苹果工具，每次可以把指定高度上的所有苹果全部摘下来。
你打算摘 q qq 次，第 i ii 次摘高度为 a i a_{i}a
i
的所有苹果。
问每次可以摘到多少个苹果？
【输入】
第一行包含两个正整数 n , q ( 1 ≤ n ≤ 1 0 6 , 1 ≤ q ≤ 2 ∗ 1 0 5 ) n,q(1≤n≤10^{6},1≤q≤2*10^{5})n,q(1≤n≤10
6
,1≤q≤2∗10
5
)，分别表示苹果的数量和摘苹果的次数。
第二行包含 n nn 个正整数 h 1 , h 2 , … , h n ( 1 ≤ h i ≤ 1 0 9 ) h_{1},h_{2},\dots,h_{n}(1\le h_{i} \le 10^{9})h
1
,h
2
,…,h
n
(1≤h
i
≤10
9
)，分别表示每个苹果的高度。
其后 q qq 行，第 i ii 行包含一个正整数 a ( 1 ≤ a i ≤ 1 0 9 ) a(1≤ a_i ≤ 10^9)a(1≤a
i
≤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<bits/stdc++.h>
using namespace std;
int n, q, tmp;
map<int, int> 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 xx，问是否存在至少一对正整数对 ( a , b ) (a,b)(a,b) 满足 a 3 + b 3 = x a^3+b^3=xa
3
+b
3
=x?
【输入】
第一行包含一个正整数 T ( 1 ≤ T ≤ 100 ) T(1≤ T≤100)T(1≤T≤100)，表示测试数据组数。
每组数据占一行，包含一个正整数 x ( 1 ≤ x ≤ 1 0 12 ) x(1≤ x ≤10^{12})x(1≤x≤10
12
)。
【输出】
对于每组数据，如果存在至少一对 ( a , b ) (a,b)(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
【题目分析】
本题有两种思路：
由于 x 最大不超过 1 0 12 10^{12}10
12
，故 a , b a,ba,b 的范围在 [ 1 , 1 0 4 ] [1,10^{4}][1,10
4
]，因此可以对 a aa 枚举，对 b bb 用二分，实测可以 AC。（但是不能 a , b a,ba,b 均枚举，会超时）
可以先将所有 a 3 a^3a
3
存入容器中，然后枚举 b bb ，看 x − b 3 x-b^3x−b
3
是否在容器中，若有，则有解。
? PS1：使用 vector 会超时，因为在 vector 中查找元素，时间复杂度为 O ( N ) O(N)O(N)；而在 set、map 中，查找的时间复杂度为 O ( l o g N ) O(logN)O(logN)，时间会大大降低。
? PS2：本题数据上限很大，已经超出了 int 类型的范围，需要使用 long long 类型。（ 1ll 是 1 的 long long 形式，任何 int 类型数据 * 1ll 后均能转换为 long long 类型）
【 C++ 代码】
思路1：
#include<bits/stdc++.h>
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<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, flag;
ll x;
set<ll> 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<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, flag;
ll x;
vector<ll> v;
vector<ll>::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 ≤ n ≤ 1000 ) n(1 ≤ n ≤ 1000)n(1≤n≤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<bits/stdc++.h>
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<bits/stdc++.h>
using namespace std;
stack<int> 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 NN 张蛋糕订单。
店内有充足的原材料（奶油、淀粉、鸡蛋）可以用于制作蛋糕，每种原材料按份存储，每份都有一个美味度。已知第 i ii 份订单的蛋糕需要使用 x i x_ix
i
份奶油、y i y_iy
i
份淀粉以及 z i z_iz
i
份鸡蛋制作。
作为店长，你决定按顺序每次取目前最好的材料制作蛋糕。换句话说，你会按订单的给定顺序制作蛋糕，对于第一份蛋糕，会使用美味度最高的 x i x_ix
i
份奶油、y i y_iy
i
份淀粉以及 z i z_iz
i
份鸡蛋进行制作；对于第二份蛋糕，会使用剩下的美味度最高的 x 2 x_2x
2
份奶油、y 2 y_2y
2
份淀粉以及 z 2 z_2z
2
份鸡蛋进行制作；以此类推。
已知一份蛋糕的美味度等同于所有使用掉的原材料的美味度之和，问每份蛋糕的美味度分别是多少？
【输入】
第一行包含三个正整数 X , Y , Z ( 1 ≤ X , Y , Z ≤ 1 0 5 ) X,Y,Z(1 \le X,Y,Z \le 10^5)X,Y,Z(1≤X,Y,Z≤10
5
)，分别表示店内一开始拥有的奶油、淀粉以及鸡蛋的份数。
第二行包含 X XX 个正整数，表示每份奶油的美味度。
第三行包含 Y YY 个正整数，表示每份淀粉的美味度。
第四行包含 Z ZZ 个正整数，表示每份鸡蛋的美味度。
第五行包含一个正整数 N ( 1 ≤ N ≤ m i n ( X , Y , Z ) ) N(1≤ N ≤ min(X,Y, Z))N(1≤N≤min(X,Y,Z))，表示订单的数量。
其后 N NN 行，每行包含三个正整数 x i , y i , z i ( 1 ≤ x i , y i , z i ≤ 10 ) x_i,y_i,z_i(1 \le x_i,y_i,z_i \le 10)x
i
,y
i
,z
i
(1≤x
i
,y
i
,z
i
≤10)，分别表示制作每份订单的蛋糕所需要使用的奶油、淀粉及鸡蛋的份数。
每份材料的美味度是一个不超过 10000 1000010000 的正整数。
数据保证 ∑ x i ≤ X , ∑ y i ≤ Y , ∑ z i ≤ Z \sum x_{i} \leq X, \sum y_{i} \leq Y, \sum z_{i} \leq Z∑x
i
≤X,∑y
i
≤Y,∑z
i
≤Z
【输出】
输出 N NN 行，每行包含一个正整数，表示每份订单的蛋糕的美味度。
【输入样例】
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<bits/stdc++.h>
using namespace std;
int X, Y, Z, N, tmp, x, y, z;
priority_queue<int> qx; //定义3个优先队列，默认为大顶堆，美食度高的元素排在队首
priority_queue<int> qy;
priority_queue<int> 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 mm 份资料。你认为新查到的资料总是比以前查的资料更有价值，因此每次你会把 最早 存入电脑的那份资料删除，腾出空间来存新的资料。
给定你要查询的资料的顺序，问你总共需要 上网查找 多少次？
初始时电脑上没有任何资料。
【输入】
第一行包含两个正整数 n , m ( 1 ≤ n , m ≤ 1 0 5 ) n,m(1≤n,m≤10^5)n,m(1≤n,m≤10
5
)，分别表示需要查找的次数以及电脑的最大容量。
第二行包含 n nn 个正整数 a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 5000 ) a_1,a_2,…,a_n(1 \le a_i \le5000)a
1
,a
2
,…,a
n
(1≤a
i
≤5000)，表示每次要查的资料。
【输出】
输出一个整数，表示需要上网查的次数。
【输入样例】
7 3
1 9 1 9 8 10 1
1
2
【输出样例】
5
1
【题目分析】
本题使用 STL 中的 deque，会比较方便。（本题涉及查询，而 容器适配器 queue 不支持查询，故推荐使用deque ）
【 C++ 代码】：
#include<bits/stdc++.h>
using namespace std;
int n, m, tmp, cnt;
deque<int> dq;
deque<int>::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 NN 个 1 到 1000 之间的随机整数 N ≤ 100 N≤100N≤100，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成 “去重” 与 “排序” 的工作。
【输入】
有 2 行，第 1 行为 1 个正整数，表示所生成的随机数的个数：N NN
第 2 行有 N NN 个用空格隔开的正整数，为所产生的随机数。
【输出】
2 行，第 1 行为 1 个正整数M，表示不相同的随机数的个数。第 2 行为 M MM 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
【输入样例】
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<bits/stdc++.h>
using namespace std;
int N, tmp;
set<int> 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;
}
————————————————
版权声明：本文为CSDN博主「Rickyの水果摊」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_46025844/article/details/127948957