526互联

STL和基本数据结构

发布时间 2023-11-19 13:13:01作者: W_K_KAI

STL和基本数据结构

一、vector

用法：vector是STL的动态数组。

img

img

img

圆桌问题

Problem Description

圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。

Input

多组数据，每组数据输入：好人和坏人的人数n（<=32767）、步长m（<=32767）；

Output

对于每一组数据，输出2n个大写字母，‘G’表示好人，‘B’表示坏人，50个字母为一行，不允许出现空白字符。相邻数据间留有一空行。

Sample Input

2 3
2 4

Sample Output

GBBG

BGGB

Source

AHOI1999

代码展示：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	vector<int >table; // 创建一个整型向量table
	int n, m;
	while (cin >> n >> m) { // 当输入n和m时循环
		table.clear(); // 清空table向量
		for (int i = 0; i < 2 * n; i++) {
			table.push_back(i); // 向table中添加元素，编号从0到2n-1
		}
		int pos = 0; // 初始化位置变量pos
		for (int i = 0; i < n; i++) { // 循环n次
			pos = (pos + m - 1) % table.size(); // 计算要删除的位置
			table.erase(table.begin() + pos); // 删除指定位置的元素
		}
		int j = 0; // 初始化计数变量j
		for (int i = 0; i < 2 * n; i++) { // 循环2n次
			if (!(i % 50) && i) cout << endl; // 每50个字符换行
			if (j < table.size() && i == table[j]) { // 如果i在table中
				j++;
				cout << "G"; // 输出G
			}
			else
				cout << "B"; // 否则输出B
		}
		cout << endl << endl; // 输出两个换行
	}
	return 0;
}

hdu 4841的vector程序用erase()来删除中间元素，需要把这个元素后面的所有元素往后移或往前移，复杂度是O（n），如果频繁移动，效率很低。

二、栈和stack

img

文本反转

时间限制：2000/1000 MS（Java/其他）

内存限制：65536/32768 K（Java/其他）

问题描述

伊格内修斯喜欢用相反的方式写字。给定 Ignatius 编写的一行文本，您应该反转所有单词，然后输出它们。

输入

输入包含多个测试用例。输入的第一行是一个整数 T，它是测试用例的数量。接下来是 T 个测试用例。
每个测试用例都包含一行包含多个单词的行。一行最多有 1000 个字符。

输出

对于每个测试用例，您应该输出已处理的文本。

示例输入

3
olleh !dlrow
m'I morf .udh
I ekil .mca

示例输出

hello world!
I'm from hdu.
I like acm.

提示

记住使用 getchar（） 在中间 T 之后读取 '\n'，然后你可以使用 gets（） 读取一行并处理它。

作者

伊格内修斯.L

来源

问题 - 1062 (hdu.edu.cn)

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
int main()
{
	int n;
	char ch;
	cin >> n;
	getchar();
	while (n--) {
		stack<char>s;
		while (1) {
			//cin >> ch;
			ch = getchar();
			if (ch == ' ' || ch == '\n' || ch == EOF) {
				while (!s.empty()) {
					cout << s.top();
					s.pop();
				}
				if (ch == '\n' || ch == EOF) break;
				cout << " ";
			}
			else
				s.push(ch);

		}
		cout << endl;
	}
	return 0;
}

三、队列和queue：

“先进先出”

1.常用函数

  1. push() 在队尾插入一个元素
  2. pop() 删除队列第一个元素
  3. size() 返回队列中元素个数
  4. empty() 如果队列空则返回true
  5. front() 返回队列中的第一个元素
  6. back() 返回队列中最后一个元素

queueq;

ACboy needs your help again!

问题描述

ACboy被绑架了！！
他非常想念他的母亲，现在非常害怕。你无法想象他被关进的房间有多黑，:(很差。
作为一个聪明的 ACMer，你想让 ACboy 走出怪物的迷宫。但当你到达迷宫的大门时，怪物说：“我听说你很聪明，但如果不能解决我的问题，你就会和ACboy一起死。
怪物的问题显示在墙上：
每个问题的第一行是一个整数N（命令的数量），以及一个单词“FIFO”或“FILO”。（你很高兴，因为你知道“FIFO”代表“先进先出”，而“FILO”代表“先进先出”）。
而接下来的N行，每行都是“IN M”或“OUT”，（M代表一个整数）。
而问题的答案就是一扇门的通行证，所以如果你想拯救ACboy，请仔细回答问题！

输入

输入包含多个测试用例。
第一行有一个整数，表示测试用例的数量。
每个子问题的输入如上所述。

输出

对于每个命令“OUT”，您应该根据单词“FIFO”或“FILO”输出一个整数，或者如果您没有任何整数，则输出一个单词“None”。

示例输入

4
4 FIFO
IN 1
IN 2
OUT
OUT
4 FILO
IN 1
IN 2
OUT
OUT
5 FIFO
IN 1
IN 2
OUT
OUT
OUT
5 FILO
IN 1
IN 2
OUT
IN 3
OUT

示例输出

1
2
2
1
1
2
None
2
3

源

[2007省赛集训队练习赛（1）

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
int main()
{
	int t, n, temp;
	cin >> t;
	while (t--) {
		string str, str1;
		queue<int>Q;
		stack<int>S;
		cin >> n >> str;
		for (int i = 0; i < n; i++) {
			if (str == "FIFO") {
				cin >> str1;
				if (str1 == "IN") {
					cin >> temp;
					Q.push(temp);
				}
				if (str1 == "OUT") {
					if (Q.empty())
						cout << "None" << endl;
					else
					{
						cout << Q.front() << endl;
						Q.pop();
					}
				}
			}
			else {
				cin >> str1;
				if (str1 == "IN") {
					cin >> temp;
					S.push(temp);
				}
				if (str1 == "OUT") {
					if (S.empty())
						cout << "None" << endl;
					else {
						cout << S.top() << endl;
						S.pop();
					}
				}
			}
		}
	}
	return 0;
}

四、set

set就是集合。STL的set用二叉搜索树实现，集合中的每个元素值出现一次，并且是排好序的。访问元素的时间复杂度是O(log2 n)，很高效！

set<Type> s						      //定义一个set容器
set<Type> s(s1)			              //定义一个set容器，并用容器s1来初始化
set<Type> s(b, e)					  //b和e分别为迭代器的开始和结束的标记
set<Type> s(s1.begin(), s1.begin()+3) //用容器s1的第0个到第2个值初始化s
set<Type> s(a, a + 5)      		      //将a数组的元素初始化vec向量，不包括a[4]
set<Type> s(&a[1], &a[4]) 			  //将a[1]~a[4]范围内的元素作为s的初始值


s.begin()					//返回指向第一个元素的迭代器
s.end()						//返回指向最后一个元素的迭代器
s.clear()					//清除所有元素
s.count()					//返回某个值元素的个数
s.empty()					//如果集合为空，返回true，否则返回false
s.equal_range()				//返回集合中与给定值相等的上下限的两个迭代器
s.erase()					//删除集合中的元素
s.find(k)					//返回一个指向被查找到元素的迭代器
s.insert()					//在集合中插入元素
s.lower_bound(k)			//返回一个迭代器，指向键值大于等于k的第一个元素
s.upper_bound(k)			//返回一个迭代器，指向键值大于k的第一个元素
s.max_size()				//返回集合能容纳的元素的最大限值
s.rbegin()					//返回指向集合中最后一个元素的反向迭代器
s.rend()					//返回指向集合中第一个元素的反向迭代器
s.size()					//集合中元素的数目

例题：

产生冠军

Time Limit: 1000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Problem Description

有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。

Input

输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。

Output

对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。

Sample Input

3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

Sample Output

Yes
No

原题链接：Problem - 2094 (hdu.edu.cn)

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
using namespace std;
int main()
{
	set<string>A, B;
	string s1, s2;
	int n;
	while (cin >> n && n) {
		for (int i = 0; i < n; i++) {
			cin >> s1 >> s2;
			A.insert(s1);
			A.insert(s2);
			B.insert(s2);
		}
		if (A.size() - B.size() == 1)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
		A.clear(), B.clear();
	}
	return 0;
}

五、map

一对一映射，给予关键字快速查找，不允许重复值。

购物

时间限制：10000/5000 MS（Java/其他）

内存限制：32768/32768 K（Java/其他）

问题描述

每个女孩都喜欢购物，蒲公英也是如此。现在她发现店里每天都在涨价，因为春节快到了。她喜欢一家名为“记忆”的商店。现在她想知道这家店的价格在每天变化后排名如何。

输入

一行连数n（n<=10000），代表商店数量。
然后是n行，每行包含一个字符串（长度小于31，只包含小写字母和大写字母。代表商店的名称。
然后一条直线连续一个数字 m （1<=m<=50），代表天。
然后 m 个零件，每个零件连数 n 行，每行连数一个数字 s 和一个字符串 p，代表这一天，商店 p 的价格上涨了 s。

输出

包含m行，在第i行中打印第i天后商店“内存”的排名。我们将排名定义为：如果有t家商店的价格高于“内存”，则其排名为t+1。

示例输入

3
memory
kfc
wind
2
49 memory
49 kfc
48 wind
80 kfc
85 wind
83 memory

示例输出

1
2

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
int main()
{
	int n, m, p;
	map<string, int>shop;
	while (cin >> n) {
		string s;
		for (int i = 1; i <= n; i++)
			cin >> s;
		cin >> m;
		while (m--) {
			for (int i = 1; i <= n; i++) {
				cin >> p >> s;
				shop[s] += p;
			}
			int  rank = 1;
			map<string, int>::iterator it;//迭代器
			for (it = shop.begin(); it != shop.end(); it++) {
				if (it->second > shop["memory"])
					rank++;
			}
			cout << rank << endl;
		}
		shop.clear();
	}
	return 0;
}

六、next_permutation()

STL提供求下一个排列组合的函数next_permutation()。例如求abc的全排列。
返回值：如果没有下一个排列组合，返回false，否则返回true。每执行一次next_permutation()，就会把新的排列放到原来的空间里。

复杂度：O(n)。范围[first,last)

例题：

字典序最小指的是在一组字符串中，按照从前往后的顺序，第一个不同的字符在字母表中较小的字符串排在前面。

伊格内修斯和公主二世

时间限制：2000/1000 MS（Java/其他）

内存限制：65536/32768 K（Java/其他

​ 问题描述

现在，我们的英雄找到了通往BEelzebub feng5166的门。他打开门，发现feng5166正要杀死我们漂亮的公主。但现在别西卜必须首先击败我们的英雄。feng5166说：“我有三个问题要问你，如果你能解决，我就放了公主，或者你也做我的晚餐。伊格内修斯自信地说：“好吧，我终于要救公主了。

“现在我来告诉你第一个问题。” feng5166 说，“给定一个数字 1 到 N 的序列，我们定义 1,2,3...N-1，N 是所有序列中最小的序列，可以由数字 1 到 N 组成（在这个问题中，每个数字可以而且应该只使用一次）。所以很容易看出第二小的序列是 1,2,3...N，N-1。现在我给你两个数字，N 和 M。你应该告诉我由数字 1 到 N 组成的 M 最小序列。这很容易，不是吗？哈哈哈哈哈......“
你能帮伊格内修斯解决这个问题吗？

输入

输入包含多个测试用例。每个测试用例由两个数字组成，N 和 M（1<=N<=1000,1<=M<=10000）。你可以假设总有一个序列满足了 BEelzebub 的需求。输入在文件末尾终止。

输出

对于每个测试用例，您只需要输出满足 BEelzebub 需求的序列。输出序列时，应在两个数字之间打印一个空格，但不要在最后一个数字之后输出任何空格。

示例输入

6 4
11 8

示例输出

1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10

代码示例：

#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
int a[1001];
using namespace std;
int main()
{
	int n, m;
	while (cin >> n >> m) {
		for (int i = 1; i <= n; i++)
			a[i] = i;
		int b = 1;
		do {
			if (b == m)
				break;
			b++;
		} while (next_permutation(a + 1, a + 1 + n));
		for (int i = 1; i < n; i++) 
			cout << a[i] << " ";
		cout << a[n] << endl;
	}
	return 0;
}