【信息奥赛实训】Week1——STL 与基础数据结构专题训练-阿南达文事网

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

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

作者｜Rickyの水果摊

时间｜2022年11月20日

实训概要

实训专题

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

实训目的

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

题目列表

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

题解

A：摘苹果

【题目名称】摘苹果

【题目描述】

苹果树上有 n n n 个苹果，每个苹果的高度分別为 h 1 , h 2 , … , h n h_{1},h_{2},\dots,h_{n} h1,h2,…,hn。

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

你打算摘 q q q 次，第 i i i 次摘高度为 a i a_{i} ai 的所有苹果。

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

【输入】

第一行包含两个正整数 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≤106,1≤q≤2∗105)，分别表示苹果的数量和摘苹果的次数。

第二行包含 n n n 个正整数 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}) h1,h2,…,hn(1≤hi≤109)，分别表示每个苹果的高度。

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

【输出】

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

【输入样例】

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

【输出样例】

【题目分析】

本题考查 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;
}

B：立方和

【题目名称】立方和

【题目描述】

给你一个正整数 x x x，问是否存在至少一对正整数对 ( a , b ) (a,b) (a,b) 满足 a 3 + b 3 = x a^3+b^3=x a3+b3=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≤1012)。

【输出】

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

【输入样例】

【输出样例】

NO
YES
NO
NO
YES
YES

【题目分析】

本题有两种思路：

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

🍉 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;
}

思路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++) {   //枚举bif (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;
}

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;
}

C：计算个数

【题目名称】计算个数

【题目描述】

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

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

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

【输入】

输入仅一个正整数 n ( 1 ≤ n ≤ 1000 ) n(1 ≤ n ≤ 1000) n(1≤n≤1000)。

【输出】

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

【输入样例】

4
6
8

【输出样例】

4
6
10

【题目分析】

本题考查递推思想。

以题目中的 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;
}

D：后缀表达式的值

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

【题目描述】

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

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

【输入】

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

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

除法当作整除即可。

【输出】

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

【输入样例】

16 9 4 3 +*-@

【输出样例】

-47

【题目分析】

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

后缀表达式相关知识点博客：

🍉 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（主栈顶元素放在操作符右边）和次栈顶元素num1int 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;
}

E：做蛋糕

【题目名称】做蛋糕

【题目描述】

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

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

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

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

【输入】

第一行包含三个正整数 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≤105)，分别表示店内一开始拥有的奶油、淀粉以及鸡蛋的份数。

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

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

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

第五行包含一个正整数 N ( 1 ≤ N ≤ m i n ( X , Y , Z ) ) N(1≤ N ≤ min(X,Y, Z)) N(1≤N≤min(X,Y,Z))，表示订单的数量。

其后 N N N 行，每行包含三个正整数 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) xi,yi,zi(1≤xi,yi,zi≤10)，分别表示制作每份订单的蛋糕所需要使用的奶油、淀粉及鸡蛋的份数。

每份材料的美味度是一个不超过 10000 10000 10000 的正整数。
数据保证 ∑ x i ≤ X , ∑ y i ≤ Y , ∑ z i ≤ Z \sum x_{i} \leq X, \sum y_{i} \leq Y, \sum z_{i} \leq Z ∑xi≤X,∑yi≤Y,∑zi≤Z

【输出】

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

【输入样例】

【输出样例】

21
26

【题目分析】

本题可以使用 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);elseqz.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;
}

F：查资料

【题目名称】

【题目描述】

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

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

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

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

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

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

【输入】

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

第二行包含 n n n 个正整数 a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 5000 ) a_1,a_2,…,a_n(1 \le a_i \le5000) a1,a2,…,an(1≤ai≤5000)，表示每次要查的资料。

【输出】

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

【输入样例】

7 3
1 9 1 9 8 10 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()) { //当前电脑中未找到//查找次数+1cnt++;//将当前新资料放入电脑中if (dq.size() == m) {  //若电脑容量已满，弹出首资料dq.pop_front();}dq.push_back(tmp);}}cout << cnt << endl;return 0;
}

G：明明的随机数

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

【题目描述】

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

【输入】

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

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

【输出】

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

【输入样例】

10
20 40 32 67 40 20 89 300 400 15

【输出样例】

8
15 20 32 40 67 89 300 400

【题目分析】

本题考查 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;
}