首页 > 其他分享 >STL和基本数据结构

STL和基本数据结构

时间:2023-11-19 13:24:27浏览次数:36  
标签:基本 include 示例 STL 元素 cin int 数据结构 OUT

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;
}

标签:基本,include,示例,STL,元素,cin,int,数据结构,OUT
From: https://www.cnblogs.com/KAI040522/p/17841925.html

相关文章

  • yolov8基本使用方式
    命令行启动:yolotask=detectmode=predictmodel=./yolov8n.ptsource="./ultralytics/asset/bus.jpg"python命令启动:fromultralyimportYOLOyolo=YOLO("./yolov8n.pt",task="detect")resoult=yolo(source="./ultralytics/assets/bus.jp......
  • Linux信号基本概念
    信号分为两大类:标准信号,用于内核向进程通知事件,信号范围为1~31实时信号信号产生后,会在稍后被传递给某进程,进程也会采取某措施来响应信号。在产生和到达期间,信号处于pending(等待)状态。有时需要确保一段代码不被传递来的信号所中断,这时可以把信号添加到进程的信号掩码中,阻塞......
  • Qt 基本CMakeLists.txt 文件
    cmake_minimum_required(VERSION3.5)project(untitledVERSION0.1LANGUAGESCXX)set(CMAKE_AUTOUICON)set(CMAKE_AUTOMOCON)set(CMAKE_AUTORCCON)set(CMAKE_CXX_STANDARD17)set(CMAKE_CXX_STANDARD_REQUIREDON)find_package(QTNAMESQt6Qt5REQUIREDCOM......
  • OpcUaHelper的基本使用
    FromBrowseServer使用此窗口服务可以查看服务器的节点状态。 1OpcUaHelper.Forms.FormBrowseServerformBrowseServer=newForms.FormBrowseServer();2formBrowseServer.ShowDialog(); 当然你可以固定住这个地址,传入地址即可,此处为示例: 1OpcUaHelper.Forms.Fo......
  • USB基本概念二
    Q1.USB总线驱动是干嘛用的?A1.1.识别USB设备2.给USB设备找到并安装对应的驱动程序3.提供USB读写函数新接入的USB设备默认地址(编号)为0,在未分配新编号前,PC主机使用0地址与其通信。(指匹配到驱动之前,会先与USB设备的prot0进行沟通,然后配置,当总线添加设备后,与驱动匹配后,择交给驱......
  • 无涯教程-RSpec - 基本语法
    让无涯教程仔细看看HelloWorld示例的代码。首先,如果不清楚,正在测试HelloWorld类的函数。当然,这是一个非常简单的类,仅包含一个方法say_hello()。这又是RSpec代码-describeHelloWorlddocontext“WhentestingtheHelloWorldclass”doit"Thesay_......
  • STL和基本数据结构
    STL和基本数据结构一、vector用法:vector是STL的动态数组。圆桌问题****TimeLimit:3000/1000MS(Java/Others)***MemoryLimit:65535/32768K(Java/Others)*ProblemDescription圆桌上围坐着2n个人。其中n个人是好人,另外n个人是坏人。如果从第一个人开始数数,数到......
  • 【数据结构】第一章——绪论2
    前言大家好,很高兴又和大家见面啦!!!今天我们将继续介绍数据结构第一章的相关内容。在上一篇中,我们介绍了数据结构的基本概率,简单说明了一下数据结构的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。我个人是感觉这些定义有点不好理解,不过没关系,这些内容会随着我们学习的......
  • 数据结构之二叉树的遍历2(java)
    一:概述二叉树的深度遍历3种方式:前序遍历、中序遍历、后序遍历。下面是具体的这三种方式的遍历代码。二:具体概述用递归的方式实现前序遍历、中序遍历、后序遍历。publicclassTreeNodeTraveral{/***构建二叉树**@paraminputList输入序列*/......
  • 数据结构概念篇
    数组特性连续,顺序查找o1队列特性不连续,随机插入,删除o1栈stack特性​ 先进后出,pushpop​ 应用undo/redo上一页,下一页浏览器访问日志panic使用数组和链表分别实现栈队queue特性先进先出enqueuedequeue应用抢票打客服使用数组和链表分别......