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
是否在容器中，若有，则有解。