grant's Blog

记录生活中的点点滴滴

STL应用专题练习（三）

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 7.6k 阅读时长 ≈ 7 分钟

本专题练习参考《算法训练营—入门篇》的STL应用题单。

附上vjudge练习地址： https://vjudge.csgrandeur.cn。

补充C语言网STL专题题单： https://www.dotcpp.com/oj/train/1012/。

T1—-POJ1028

注：原题是全英文，这里机翻成中文，为保证题意理解的准确性请参考原题链接。

1
2
3
4
5
6
7
8
9
10
11
12
13
标准 Web 浏览器包含可在最近访问的页面之间前后移动的功能。实现这些功能的一种方法是使用两个堆栈来跟踪可以通过后移和向前移动来访问的页面。在此问题中，系统会要求您实现此操作。
需要支持以下命令：
BACK：将当前页面推送到正向堆栈的顶部。从向后堆栈的顶部弹出页面，使其成为新的当前页面。如果向后堆栈为空，则忽略该命令。
FORWARD：将当前页面推到向后堆栈的顶部。从正向堆栈的顶部弹出页面，使其成为新的当前页面。如果正向堆栈为空，则忽略该命令。
VISIT ：将当前页面推送到向后堆栈的顶部，并使指定的URL成为新的当前页面。正向堆栈已清空。
QUIT：退出浏览器。
假设浏览器最初加载网页的 URL http://www.acm.org/

输入：
输入是一系列命令。命令关键字 BACK、FORWARD、VISIT 和 QUIT 均为大写。URL 没有空格，最多包含 70 个字符。您可以假定没有问题实例在任何时候都需要每个堆栈中超过 100 个元素。输入的末尾由 QUIT 命令指示。
    
输出：
对于除 QUIT 以外的每个命令，如果未忽略该命令，请在执行命令后打印当前页面的 URL。否则，请打印"Ignored"。每个命令的输出应打印在其自己的行上。不为 QUIT 命令生成任何输出。

考察STL：stack。

参考《C++竞赛语法总结（七）》。

头文件stack包含栈。声明和前面的容器类似。

没有clear函数。

先进后出(FILO)，栈顶插入，栈顶删除

push 向栈顶插入

pop 弹出栈顶元素

top 取栈顶元素

本题涉及到栈的清空操作，因为stack没有clear函数，所以只能重新创建栈或者逐个出栈至栈空。

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
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;

int main(){
    stack<string> forward; // 前向栈
    stack<string> backward; // 后向栈
    
    string url = "http://www.acm.org/";
    string op;
    while (cin >> op && op != "QUIT"){
        if (op == "BACK"){
            if (backward.empty()){
                cout << "Ignored\n";
                continue;
            }
            forward.push(url);
            url = backward.top();
            backward.pop();
            cout << url << '\n';
        }else if (op == "VISIT"){
            backward.push(url);
            cin >> url;
            cout << url << '\n';
            
            // 前向栈不为空则清空
            while (!forward.empty())
                forward.pop();
        }else if (op == "FORWARD"){
            if (forward.empty()){
                cout << "Ignored\n";
                continue;
            }
            backward.push(url);
            url = forward.top();
            forward.pop();
            cout << url << '\n';
        }
    }
    return 0;
}

T2—-HDU1263

1
2
3
4
5
6
7
8
9
10
夏天来了~~好开心啊,呵呵,好多好多水果~~
Joe经营着一个不大的水果店.他认为生存之道就是经营最受顾客欢迎的水果.现在他想要一份水果销售情况的明细表,这样Joe就可以很容易掌握所有水果的销售情况了.
    
输入：
第一行正整数N(0<N<=10)表示有N组测试数据.
每组测试数据的第一行是一个整数M(0<M<=100),表示共有M次成功的交易.其后有M行数据,每行表示一次交易,由水果名称(小写字母组成,长度不超过80),水果产地(小写字母组成,长度不超过80)和交易的水果数目(正整数,不超过100)组成.
    
输出：
对于每一组测试数据,请你输出一份排版格式正确(请分析样本输出)的水果销售情况明细表.这份明细表包括所有水果的产地,名称和销售数目的信息.水果先按产地分类,产地按字母顺序排列;同一产地的水果按照名称排序,名称按字母顺序排序.
两组测试数据之间有一个空行.最后一组测试数据之后没有空行.

考察STL：map。

参考《C++竞赛语法总结（九）》。

本题用到三个数据的映射，所以是一个二维map。

一维map是一个键对应一个值，二维map是两个键组合成的键对应一个值。

本题也可用结构体排序处理，不过比较麻烦。

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
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
using namespace std;

int main(){
    int n,m,num;
    string name,address;
    cin >> n;
    
    while (n--){
        cin >> m;
        
        map<string,map<string,int> > mp; // 注意二维map写法
        while (m--){
            cin >> name >> address >> num;
            mp[address][name] += num;
        }
        
        // 注意两个迭代器的定义不同，二维map是如何迭代的
        map<string,map<string,int> >::iterator it1;
        map<string,int>::iterator it2;
        for (it1 = mp.begin();it1 != mp.end();it1 ++){
            cout << it1->first << '\n';
            for (it2 = it1->second.begin();it2 != it1->second.end();it2 ++){
                cout << "   |----" << it2->first << "(" << it2->second << ")" << '\n';
            }
        }
        
        if (n) cout << '\n'; // 两组数据之间有空行，最后一组数据后无空行
    }
    return 0;
}

T3—-HDU3527

注：原题是全英文，这里机翻成中文，为保证题意理解的准确性请参考原题链接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
X国的国家情报委员会收到一个可靠的信息，Y国将派间谍来偷X国的机密文件。
因此，国家情报委员会的指挥官立即采取措施，他将调查将进入X国的人。
同时，指挥官手中有两份名单，一份是Y国将派往X国的间谍，另一份是X国以前派往Y国的间谍。这两份名单可能有一些重叠。因为间谍可能同时扮演两个角色，这意味着他可能是那个从国家X派往国家Y的间谍，我们就把这种类型称为 "双重间谍"。所以Y国可能会把 "双重间谍 "送回X国，现在很明显，这对X国是有利的，因为 "双重间谍 "可以把Y国的机密文件带回来，而不用担心被Y国的边防拘留，所以指挥官决定抓住那些由Y国派来的人，让普通人和 "双重间谍 "同时进来。
那么你能决定一个应该被指挥官抓住的名单吗？
A:名单上的人将会来到NationX的边境地区。
B:名单上有Y国派来的间谍。
C:该名单包含以前被派往Y国的间谍。
    
输入：
有几个测试用例。
每个测试用例包含四个部分，第一部分包含3个正整数A、B、C，A是将进入边界的人数。B是将由Nation Y发送的人数，C是NationX以前发送过给NationY的人数。
第二部分包含A个字符串，将进入边境的名字列表。
第二部分包含B个字符串，由NationY发送的名字列表。
第二部分包含C个字符串，即 "双重间谍 "的名字列表。
每个测试用例后都会有一个空行。
在一个列表中不会有任何重复的名字，如果重复的名字出现在两个列表中，它们意味着是同一个人。
    
输出：
输出指挥官应该抓到的列表（按照列表B的出现顺序），如果没有人应该被抓住，那么，你应该输出"No enemy spy"

考察STL：vector以及find函数（在algorithm库中）。

参考《C++竞赛语法总结（七）》。

find() 函数本质上是一个模板函数，用于在指定范围内查找和目标元素值相等的第一个元素。

find() 函数常用于查找 vector 和 string。

如下为 find() 函数的语法格式：

InputIterator find (InputIterator first, InputIterator last, const T& val);

其中，first 和 last 为输入迭代器，[first, last) 用于指定该函数的查找范围；val 为要查找的目标元素。

正因为 first 和 last 的类型为输入迭代器，因此该函数适用于所有的序列式容器。

另外，该函数会返回一个输入迭代器，当 find() 函数查找成功时，其指向的是在 [first, last) 区域内查找到的第一个目标元素；如果查找失败，则该迭代器的指向和 last 相同。

值得一提的是，find() 函数的底层实现，其实就是用==运算符将 val 和 [first, last) 区域内的元素逐个进行比对。这也就意味着，[first, last) 区域内的元素必须支持==运算符。

题目的大意就是有三份名单，一份是所有旅客，一份是A间谍名单，一份是B间谍名单。 要求 我们找出现在A名单上但是未出现在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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define pu push_back
using namespace std;

int main(){
    int m,n,k;
    
    while (cin >> m >> n >> k){
        vector<string> a,b,c,ans;
        string str;
        for (int i = 0;i < m;i ++){
            cin >> str;
            a.pu(str);
        }
            
        for (int i = 0;i < n;i ++){
            cin >> str;
            b.pu(str);
        }
        
        for (int i = 0;i < k;i ++){
            cin >> str;
            c.pu(str);
        }
        
        for (int i = 0;i < n;i ++){
            // find函数的三个参数分别是始末迭代器和查找目标
            // 查找成功返回目标出现的第一个位置，查找失败返回末迭代器
            if (find(a.begin(),a.end(),b[i]) != a.end() && find(c.begin(),c.end(),b[i]) == c.end())
                ans.pu(b[i]);
        }
        
        if (!ans.size()){
            cout << "No enemy spy\n";
        }else{
            for (int i = 0;i < ans.size();i ++){
                if (i) cout << ' ';
                cout << ans[i];
            }
            cout  << '\n';    
        }
    }
    return 0;
}

T4—-POJ1281

注：原题是全英文，这里机翻成中文，为保证题意理解的准确性请参考原题链接。

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
并行处理中的一种编程范式是生产者/消费者范式，可以用一个带有 "管理者 "进程和若干 "客户 "进程的系统来实现。客户可以是生产者，也可以是消费者，等等。管理者保持客户进程的跟踪。每个进程都由其成本来识别，成本是一个严格的正整数，范围为1 ... 10000。具有相同成本的进程的数量不能超过10000。队列根据三种类型的请求进行管理，如下所示。
a x - 向队列中添加成本为x的进程。
r - 如果可能的话，根据当前管理器的策略，从队列中删除一个进程。
p i - 执行管理器的政策i，其中i为1或2。默认的管理器策略是1
e - 结束请求列表。

有两个管理器策略。
1 - 移除最小成本过程
2 - 删除最大成本过程

只有当被删除的进程的序号在删除列表中时，管理器才会打印被删除进程的成本。

你的工作是编写一个程序来模拟管理器的过程。
    
输入：
输入是来自标准输入。输入的每个数据集有如下格式。
过程的最大成本
移除列表的长度
删除列表--将显示被删除进程的序号列表；例如，1 4意味着将显示第一和第四个被删除进程的成本
请求列表，每个请求都在一个单独的行中。

每个数据集以一个e请求结束。数据集之间用空行隔开。
    
输出：
程序在标准输出上打印每个被移除的进程的成本，前提是移除请求的序号在列表中，并且队列在那一刻不是空的。如果队列是空的，程序会打印出-1。这些结果被打印在不同的行上。一个空行将不同数据集的结果分开。
    
样例：
5
2
1 3
a 2
a 3
r
a 4
p 2
r
a 5
r
e

结果：
2
5

考察STL：multiset。

参考《算法基础课笔记（十四）》。

1
2
3
4
5
6
7
8
9
10
set/multiset  前者去重，后者不去重!
        insert()  插入一个数
        find()  查找一个数，不存在则返回end迭代器
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound() ：set的核心操作！
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器

注意：题目允许存在相同成本的进程。

本题适合用multiset来处理，考察它的多种操作。

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
49
#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
const int N = 1e4+5;
bool st[N];

int main(){
    int n,m;
    
    while (cin >> n >> m){
        multiset<int> mset;
        int t;
        memset(st,false,sizeof st);
        for (int i = 0;i < m;i ++){
            cin >> t;st[t] = true;
        }
        
        char op;int x,mod = 1,k = 1;
        while (cin >> op,op != 'e'){
            if (op == 'a'){
                cin >> x;
                mset.insert(x);
            }else if (op == 'r'){
                if (mset.empty()){
                    cout << -1 << '\n';
                    continue;
                }
                
                if (mod == 1){
                    int p = *mset.begin(); // 删除列表指的是删除时的顺序
                    // 样例中三次r操作的删除序号是：2,4,5 删除列表是：1,3 所以输出2,5
                    if (st[k++]) cout << p << '\n';
                    mset.erase(mset.begin());
                }else{
                    int p = *--mset.end(); // 注意最大值的写法
                    if (st[k++]) cout << p << '\n';
                    mset.erase(--mset.end());
                }
            }else if (op == 'p'){
                cin >> mod;
            }
        }
        cout << '\n'; // 不同数据间需要空行
    }
    
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！