grant's Blog

记录生活中的点点滴滴

STL应用专题练习（四）

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

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

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

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

T1—-HDU1276

1
2
3
4
5
6
7
8
9
10
11
12
13
某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。
    
本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。  

共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。
    
样例：
2
20
40
输出：
1 7 19
1 19 37

考察STL：list，queue。两个都可以做。

list参考博客： https://blog.csdn.net/yas12345678/article/details/52601578/。

begin()和end()：通过调用list容器的成员函数begin()得到一个指向容器起始位置的iterator，可以调用list容器的 end() 函数来得到list末端下一位置，相当于：int a[n]中的第n+1个位置a[n]，实际上是不存在的，不能访问，经常作为循环结束判断结束条件使用。

push_back() 和push_front()：使用list的成员函数push_back和push_front插入一个元素到list中。其中push_back()从list的末端插入，而 push_front()实现的从list的头部插入。

empty()：利用empty() 判断list是否为空。

clear()：清空list中的所有元素。

pop_back和pop_front()：通过删除最后一个元素，通过pop_front()删除第一个元素；序列必须不为空，如果当list为空的时候调用pop_back()和pop_front()会使程序崩掉。

insert()：在指定位置插入一个或多个元素(三个重载)：

l1.insert(l1.begin(),100); 在l1的开始位置插入100。

l1.insert(l1.begin(),2,200); 在l1的开始位置插入2个100。

l1.insert(l1.begin(),l2.begin(),l2.end());在l1的开始位置插入l2的从开始到结束的所有位置的元素。

erase()：删除一个元素或一个区域的元素(两个重载)

l1.erase(l1.begin()); 将l1的第一个元素删除。

l1.erase(l1.begin(),l1.end()); 将l1的从begin()到end()之间的元素删除。

vector和list、deque的对比：

vector的底层结构是动态顺序表，在内存中是一段连续的空间。

list的底层结构是带头节点的双向循环链表循环链表，在内存中不是一段连续的空间。

vector支持随机访问，可以利用下标精准定位到一个元素上，访问某个元素的时间复杂度是O(1)。

list不支持随机访问，要想访问list中的某个元素只能是从前向后或从后向前依次遍历，时间复杂度是O(N)。

vector任意位置插入和删除的效率低，因为它每插入一个元素（尾插除外），都需要搬移数据，时间复杂度是O(N)，而且插入还有可能要增容，这样一来还要开辟新空间，拷贝元素，是旧空间，效率会更低。

list任意位置插入和删除的效率高，他不需要搬移元素，只需要改变插入或删除位置的前后两个节点的指向即可，时间复杂度为O(1)。

总结：

因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，具体可以遵循下面的原则：

  1. 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector，
  2. 如果你需要大量的插入和删除，而不关心随即存取，则应使用list，
  3. 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。

关于C++ STL中非连续存储容器的删除（erase）的说明：

https://www.cnblogs.com/yelongsan/p/4050404.html。

STL中的容器按存储方式分为两类，一类是按以数组形式存储的容器（如：vector 、deque)；另一类是以不连续的节点形式存储的容器（如：list、set、map）。在使用erase方法来删除元素时，需要注意一些问题。

对整个队伍而言 一至二的范围报数 就像 1 2 1 2 1 2 …直到结束 其中2的出列 再1 2 3 1 2 3 … 其中3的出列

本题需要大量的删除，所以采用双向链表list。

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

int main(){
    int n,m;
    list<int> li;
    list<int>::iterator it;
    cin >> n;
    
    while (n--){
        li.clear();
        cin >> m;
        
        for (int i = 1;i <= m;i ++)
            li.push_back(i); // 链表尾插法
        
        int k = 2; // 先12报数再123报数  
        while (li.size() > 3){
            int cnt = 1;
            // 注意不要it ++，原因看上面erase删除的说明链接
            for (it = li.begin();it != li.end();){
                if (cnt++ % k == 0) it = li.erase(it);
                else it ++;
            }
            k = (k == 2 ? 3 : 2);
        }
        
        for (it = li.begin();it != li.end();it ++){
            if (it != li.begin()) cout << ' ';
            cout << *it;
        }
        cout << '\n';
    }
    return 0;
}

queue题解请参考： https://www.cnblogs.com/alexdzk/p/14687035.html。

T2—-HDU6375

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
度度熊正在学习双端队列，他对其翻转和合并产生了很大的兴趣。

初始时有 N 个空的双端队列（编号为 1 到 N ），你要支持度度熊的 Q 次操作。

①1 u w val 在编号为 u 的队列里加入一个权值为 val 的元素。（w=0 表示加在最前面，w=1 表示加在最后面）。

②2 u w 询问编号为 u 的队列里的某个元素并删除它。（ w=0 表示询问并操作最前面的元素，w=1 表示最后面）

③3 u v w 把编号为 v 的队列“接在”编号为 u 的队列的最后面。w=0 表示顺序接（队列 v 的开头和队列 u 的结尾连在一起，队列v 的结尾作为新队列的结尾）, w=1 表示逆序接（先将队列 v 翻转，再顺序接在队列 u 后面）。且该操作完成后，队列 v 被清空。
    
有多组数据。

对于每一组数据，第一行读入两个数 N 和 Q。

接下来有 Q 行，每行 3~4 个数，意义如上。

N <= 150000,Q <= 400000

1 ≤ u,v ≤ N,0 ≤ w ≤ 1,1 ≤ val ≤ 100000

所有数据里 Q 的和不超过500000

考察STL：list，deque。两个都可以做。

题解一：deque。

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

c.begin() 返回一个迭代器，它指向容器c的第一个元素

c.end() 返回一个迭代器，它指向容器c的最后一个元素的下一个位置

c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素

c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置

反向迭代器：rbegin()，rend()

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 按照题目描述用deque模拟一遍
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
const int N = 150005;
deque<int> d[N];
// 读入数据过大，手写输入
void read(int &x){
    char ch = getchar();
    x = 0;
    for (;ch < '0' || ch > '9';ch = getchar()); // 过滤非数字
    for (;ch >= '0' && ch <= '9';ch = getchar())
        x = x*10 + ch - '0';
}

int main(){
    int m,n;
    
    while (~scanf("%d %d",&m,&n)){
        for (int i = 0;i < m;i ++){
            d[i].clear();
        }
        
        while (n--){
            int op,u,v,w;
            read(op);
            switch(op){
                case 1:
                    read(u),read(v),read(w);
                    if (v == 1) d[u-1].push_back(w);
                    else d[u-1].push_front(w);
                    break;
                case 2:
                    read(u),read(v);
                    if (d[u-1].empty()){
                        printf("-1\n");
                        break;
                    }
                        
                    if (v == 1){
                        printf("%d\n",d[u-1].back());
                        d[u-1].pop_back();
                    }
                    else{
                        printf("%d\n",d[u-1].front());
                        d[u-1].pop_front();
                    }
                    break;
                case 3:
                    read(u),read(v),read(w);
                    if (w == 1)
                        d[u-1].insert(d[u-1].end(),d[v-1].rbegin(),d[v-1].rend());
                    else
                        d[u-1].insert(d[u-1].end(),d[v-1].begin(),d[v-1].end());
                    
                    d[v-1].clear();
                    break;
                    /*position - deque中要插入新元素的索引
                    first - 将迭代器输入到范围内的初始位置
                    last - 将迭代器输入到范围内的最终位置*/
            }
        }
    }
    return 0;
}

题解二：list。用到list的翻转和拼接函数。

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
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
const int N = 150005;
list<int> d[N];

void read(int &x){
    char ch = getchar();
    x = 0;
    for (; ch < '0' || ch > '9';ch = getchar());
    for (; ch >= '0' && ch <= '9';ch = getchar())
        x = x*10 + ch - '0';
}

int main(){
    int n,m;
    
    while (~scanf("%d%d",&n,&m)){
        for (int i = 1;i <= n;i ++)
            d[i].clear();
            
        while (m--){
            int k,u,v,w;
            read(k);
            switch (k){
                case 1:
                    read(u),read(v),read(w);
                    if (v) d[u].push_back(w);
                    else d[u].push_front(w);
                    break;
                case 2:
                    read(u),read(v);
                    if (d[u].empty()){
                        cout << -1 << '\n';
                        break;
                    }
                    
                    if (v){
                        cout << d[u].back() << '\n';
                        d[u].pop_back();
                    }
                    else{
                        cout << d[u].front() << '\n';
                        d[u].pop_front();
                    }
                    break;
                case 3:
                    read(u),read(v),read(w);
                    if (w){
                        d[v].reverse();
                    }
                    d[u].splice(d[u].end(),d[v]);//splice拼接函数会自动清空v，常数时间
                    break;
            }
        }
    }
    return 0;
}

T3—-POJ1915

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

acwing题目地址： https://www.acwing.com/problem/content/1192。（单组样例，本题是多样例）

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
有N颗珠子，它们的形状和大小相同，但重量不同。N 是一个奇数，磁珠被标记为 1， 2， ...， N。您的任务是找到重量为中位数的珠子（（N+1）/2）在所有珠子中）。对一些珠子对进行了以下比较：
给出了一个秤来比较珠子的重量。我们可以确定在两颗珠子之间哪一颗比另一颗重。结果，我们现在知道有些珠子比其他珠子重。我们将去除一些不能具有中等重量的珠子。
例如，以下结果显示了在 M=4 和 N=5 的情况下，M 比较后哪个珠子更重。
从上面的结果中，虽然我们无法确切地确定哪个是中位珠，但我们知道珠子1和珠子4永远不可能有中位重量：珠子2，4，5比珠子1重，珠子1，2，3比珠子4轻。因此，我们可以去除这两颗珠子。
编写一个程序来计算不能具有中位重量的珠子的数量。
1.	Bead 2 is heavier than Bead 1.

2.	Bead 4 is heavier than Bead 3.

3.	Bead 5 is heavier than Bead 1.

4.	Bead 4 is heavier than Bead 2.
    
输入：
输入文件的第一行包含单个整数 t （1 <= t <= 11），即测试用例的数量，后跟每个测试用例的输入数据。每个测试用例的输入如下：
第一行输入数据包含一个整数 N （1 <= N <= 99），表示磁珠的数量，M 表示比较的磁珠对数。在接下来的M行中，给出两个数字，其中第一个珠子比第二个珠子重。
    
输出：
每个测试用例应该有一行。打印永远不会具有中等重量的珠子数量。
    
样例：
1
5 4
2 1
4 3
5 1
4 2
输出：
2

不会，本题有一定难度。

题解一：Floyd传递闭包。

分析：因为n为奇数，中间为(n+1)/2，对于某个珠子，若有至少有(n+1)/2个珠子比它重或轻，则它肯定不排在中间。

转化为图论问题求解，大小关系可以通过传递闭包处理。

参考题解： https://blog.csdn.net/acm_code/article/details/38087229。

参考类似题目： 《2022寒假每日一题笔记（六）》—- 牛奶工厂。

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
int g[N][N]; // g[i][j] = 1 表示i的重量大于j，= 0 表示未确定大小关系

int main(){
    int t,n,m;
    cin >> t;
    
    while (t--){
        cin >> n >> m;
        memset(g,0,sizeof g);
        
        int x,y;
        while (m--){
            cin >> x >> y;
            g[x][y] = 1;
        }
        
        for (int k = 1;k <= n;k ++)
            for (int i = 1;i <= n;i ++)
                for (int j = 1;j <= n;j ++)
                    if (g[i][k] && g[k][j]) // i重于k，k重于j -> i重于j
                        g[i][j] = 1;
        
        int res = 0;                
        for (int i = 1;i <= n;i ++){
            int a = 0,b = 0;
            for (int j = 1;j <= n;j ++){
                if (g[i][j]) a ++;
                if (g[j][i]) b ++;
            } // 当比i重的数量或比i轻的数量 >= (n+1)/2时可以确定一定不是中位数
            if (a >= (n+1) >> 1 || b >= (n+1) >> 1) res ++;
        }
            
        cout << res << '\n';
    }
            
    return 0;
}

题解二：BFS（queue实现）。

能用floyd求传递闭包求解的，都能用bfs求出来。

考察STL：queue。

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

需要两次BFS，一次正向搜索（正向建图），一次反向搜索（反向建图）。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 105,M = 10005;
int a[M],b[M],e[M],ne[M],h[N],q1[N],q2[N],idx;
bool v[N];

void add(int a,int b){ // a->b的边
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

int bfs(int x){
    int cnt = 0;
    queue<int> q;
    memset(v,0,sizeof v);
    v[x] = true;
    q.push(x);
    
    while (!q.empty()){
        int t = q.front();
        q.pop();
        
        for (int i = h[t]; ~i;i = ne[i]){
            int a = e[i];
            if (!v[a]){
                cnt ++;
                q.push(a);
                v[a] = true;
            }
        }
    }
    return cnt;
}

int main(){
    int t,n,m;
    cin >> t;
    
    while (t--){
        cin >> n >> m;
        memset(h,-1,sizeof h);
        
        for (int i = 0;i < m;i ++) cin >> a[i] >> b[i];
        
        // 正向建图
        for (int i = 0;i < m;i ++) add(a[i],b[i]);
        for (int i = 1;i <= n;i ++) q1[i] = bfs(i); // 统计从i出发能到达点的数量
        
        memset(h,-1,sizeof h),idx = 0;
        // 反向建图
        for (int i = 0;i < m;i ++) add(b[i],a[i]);
        for (int i = 1;i <= n;i ++) q2[i] = bfs(i);
        
        int res = 0;
        for (int i = 1;i <= n;i ++){
            if (q1[i] >= (n+1) >> 1 || q2[i] >= (n+1) >> 1)
                res ++;
        }
        
        cout << res << '\n';
    }
    
    return 0;
}

本专题练习系列就此结束！！！

坚持原创技术分享，您的支持将鼓励我继续创作！