本专题练习参考《算法训练营—入门篇》的STL应用题单。
附上vjudge练习地址： https://vjudge.csgrandeur.cn。
补充C语言网STL专题题单： https://www.dotcpp.com/oj/train/1012/。
考察STL：next_permutation()（全排列函数）。
参考《C++竞赛语法总结（九）》。
注：原题是全英文，这里机翻成中文，为保证题意理解的准确性请参考原题链接。
1
2
3
4
5
6
7
8
9
| 商店经理按标签的字母顺序对各种商品进行了排序。所有具有以相同字母开头的标签的种类都存储在带有该字母标签的同一仓库（即同一建筑物中）。白天，商店经理接收并预订要从商店交付的货物订单。每个订单只需要一种商品。商店经理按照预订的顺序处理请求。
您事先知道今天必须由商店经理处理的所有订单，但您不知道他们的预订订单。计算仓库访问的所有可能方式，以便商店经理在白天逐个解决所有需求。
输入
输入包含一行，其中包含所请求货物的所有标签（按随机顺序）。每种商品都由其标签的起始字母表示。仅使用英文字母表中的小写字母。订单数量不超过 200。
输出
输出将包含商店经理可以访问其仓库的所有可能的订单。每个仓库都由一个英文字母的小字母表示 - 货物标签的起始字母。仓库的每个订购仅在单独的行上在输出文件中写入一次，并且包含排序的所有行都必须按字母顺序排序（请参阅示例）。任何输出都不会超过 2 MB。
|
将当前排列更改为 全排列中的下一个排列。如果当前排列已经是 全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为 全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true。next_permutation(v.begin(), v.end()) 或 next_permutation(v + begin, v + end)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string str;
cin >> str;
sort(str.begin(),str.end());
cout << str << '\n';
while (next_permutation(str.begin(),str.end())){
for (int i = 0;i < str.size();i ++) cout << str[i];
cout << '\n';
}
return 0;
}
|
注：原题是全英文，这里机翻成中文，为保证题意理解的准确性请参考原题链接。
1
2
3
4
5
6
7
8
9
10
11
12
| 硬木是植物学上的树木群，具有宽阔的叶子，产生果实或坚果，通常在冬季进入休眠状态。
美国的温带气候产生了数百种硬木物种的森林 - 具有某些生物特征的树木。虽然橡树，枫树和樱桃树都是硬木树的类型，例如，它们是不同的物种。所有硬木物种加起来占美国树木的40%。
另一方面，软木或针叶树，来自拉丁语，意思是"锥体轴承"，有针。广泛使用的美国软木包括雪松，冷杉，铁杉，松树，红杉，云杉和柏树。在家中，软木主要用作结构木材，如2x4s和2x6s，具有一些有限的装饰应用。
自然资源部利用卫星成像技术，编制了某一天每棵树的清单。您将计算由每个物种表示的树群的总分数。
输入
您的程序的输入包括卫星观测到的每棵树的物种列表;每行一棵树。没有物种名称超过30个字符。不超过10，000种，不超过1，000，000棵树。
输出
按字母顺序将种群中表示的每个物种的名称，后跟其所代表的种群百分比打印到小数点后 4 位。
|
数据量很大，注意输入。
考察STL：map。
参考《C++竞赛语法总结（八）》。
在使用 map 容器存储多个键值对时，该容器会自动根据各键值对的键的大小，按照既定的规则进行排序。
默认情况下，map 容器选用std::less<T>排序规则（其中 T 表示键的数据类型），其会根据键的大小对所有键值对做升序排序。也可以自定义排序。
map:
优势：
1.有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
2.红黑树，内部实现一个红黑书使得map的很多操作在logn的时间复杂度下就可以实现，因此效率非常的高
劣势：
空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
unordered_map:
优势：
因为内部实现了哈希表，因此其查找速度非常的快
劣势：
哈希表的建立比较耗费时间
对于有顺序要求的问题，使用map；
对于查找问题，使用unordered_map。
注意：不能使用scanf读取string类型变量！！！
这是语法内容了，忘记了复习一下。
对于string变量，输入只能用getline，输出只能用cout。
还有迭代器的使用不要忘了，类似指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int main(){
string str;
map<string,int> m;
int cnt = 0;
while (getline(cin,str)){
m[str] ++;
cnt ++;
}
for (map<string,int>::iterator it = m.begin();it != m.end();it ++){
cout << it->first << ' ';
printf("%.4f\n",100.0*it->second/cnt);
}
return 0;
}
|
1
2
3
4
5
6
| 给你两个集合，要求{A} + {B}.
注:同一个集合中不会有两个相同的元素.
每组输入数据分为三行,第一行有两个数字n,m(0<n,m<=10000),分别表示集合A和集合B的元素个数.后两行分别表示集合A和集合B.每个元素为不超出int范围的整数,每个元素之间有一个空格隔开.
针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,每个元素之间有一个空格隔开.
|
考察STL：set。
参考《C++竞赛语法总结（八）》。
set与unordered相比：
1、set比unordered_set使用更少的内存来存储相同数量的元素。
2、对于少量的元素，在set中查找可能比在unordered_set中查找更快。
3、尽管许多操作在unordered_set的平均情况下更快，但通常需要保证set在最坏情况下有更好的复杂度(例如insert)。
4、如果您想按顺序访问元素，那么set对元素进行排序的功能是很有用的。
5、您可以用<、<=、>和>=从字典顺序上比较不同的set集。unordered_set集则不支持这些操作。
一般来说，在如下情况，适合使用set：
1、我们需要有序的数据(不同元素)。
2、我们必须打印/访问数据(按排序顺序)。
3、我们需要知道元素的前任/继承者。
一般来说，在如下情况，适合使用unordered_set：
1、我们需要保留一组元素，不需要排序。
2、我们需要单元素访问，即不需要遍历。
3、仅仅只是插入、删除、查找的话。
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
| #include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
int main(){
int n,m;
while (~scanf("%d %d",&n,&m)){
set<int> s;
int x;
for (int i = 0;i < n;i ++){
scanf("%d",&x);
s.insert(x);
}
for (int i = 0;i < m;i ++){
scanf("%d",&x);
s.insert(x);
}
for (set<int>::iterator it = s.begin();it != s.end();it ++){
if (it != s.begin()) printf(" ");
printf("%d",*it);
}
printf("\n");
}
return 0;
}
|
注：原题是全英文，这里机翻成中文，为保证题意理解的准确性请参考原题链接。
1
2
3
4
5
6
7
8
9
10
11
| FJ正在调查他的牛群，以找到最普通的奶牛。他想知道这头"中位数"奶牛的产奶量是多少：一半的奶牛的奶量与中位数一样多或更多;一半给予同样多或更少。
给定奇数头奶牛N（1 <= N<10，000）及其牛奶产量（1..1，000，000），找到给予的牛奶中位数，使得至少一半的奶牛提供相同量或更多的牛奶，至少一半的奶牛提供相同或更少的牛奶。
输入：
* 第 1 行：单个整数 N
* 第 2 行..N+1：每行包含一个整数，该整数是一头奶牛的产奶量。
输出：
* 第 1 行：单个整数，即牛奶输出的中位数。
|
考察STL：nth_element。
参考《寒假每日一题入门题（一）》。
快速选择函数nth_element(数组初位置，寻找元素，数组末位置)（STL）
C++的STL库中的nth_element()方法，默认是求区间第k小的（划重点）。
举个栗子求第3小，对于 a[9]={4,7,6,9,1,8,2,3,5};
nth_element(a,a+2,a+9)，将下标为2，也就是第3个数放在正确的位置，求的是第3小的数a[2]。（下标从零开始）
nth_element(a,a+k,a+n)，函数只是把下标为k的元素放在了正确位置，对其它元素并没有排序，当然k左边元素都小于等于它，右边元素都大于等于它，所以可以利用这个函数快速定位某个元素。
那求第k大时呢？我们可以转化成求第n-k+1小，此时下标应该是n - k。
nth_element(a,a+n-k,a+n)，将下标为n-k，也就是第n-k+1个数放在正确的位置，求的是第k大的数a[n-k]。
时间复杂度：$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e4+5;
int q[N];
int main(){
int n;
cin >> n;
for (int i = 0;i < n;i ++) cin >> q[i];
nth_element(q,q + (n >> 1),q + n);
cout << q[n >> 1];
return 0;
}
|
注：原题是全英文，这里机翻成中文，为保证题意理解的准确性请参考原题链接。
1
2
3
4
5
6
7
8
9
10
11
12
13
| 你要编写一个程序，该程序必须从一组给定的字母中生成所有可能的单词。
示例：给定单词"abc"，您的程序应该 - 通过探索三个字母的所有不同组合 - 输出单词"abc"，"acb"，"bac"，"bca"，"cab"和"cba"。
在从输入文件中获取的单词中，某些字母可能会多次出现。对于给定的单词，程序不应多次生成同一单词，并且这些单词应按字母升序输出。
输入：
输入由几个单词组成。第一行包含一个数字，给出了要遵循的单词数。以下每行包含一个单词。单词由从A到Z的大写或小写字母组成，大写和小写字母应被视为不同。每个单词的长度小于 13。
输出：
对于输入中的每个单词，输出应包含可以使用给定单词的字母生成的所有不同单词。从同一输入词生成的单词应按字母升序输出。大写字母位于相应的小写字母之前。
提示：
大写字母位于相应的小写字母之前。
所以正确的字母顺序是"A'<"<"B"<<......<'Z'<'z'。
|
考察STL：next_permutation()（全排列函数）。
参考《C++竞赛语法总结（九）》。
参考博客： next_permutation的多种题型介绍（很全面！）
next_permutation()除了传入begin和end之外，也可以再传一个cmp函数进去。规则类似于sort()，cmp函数与重载小于号作用相同。
库函数 int tolower(int c) 把给定的字母转换为小写字母。返回值是一个可被隐式转换为 char 类型的 int 值。
相应地有库函数 int toupper(int c)。
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
| #include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(char a,char b){
if (tolower(a) != tolower(b)){
return tolower(a) < tolower(b);
}
else return a < b;
}
int main(){
int n;
cin >> n;
string str;
while (n--){
cin >> str;
sort(str.begin(),str.end(),cmp);
cout << str << '\n';
while (next_permutation(str.begin(),str.end(),cmp)){
cout << str << '\n';
}
}
return 0;
}
|
