STL 是 c++ 的标准模板库。

# 排序与检索

# 题目：大理石在哪里？

现有个大理石，每个大理石上写了一个非负整数。首先把各数从小到大排序，然后
回答 Q 个问题。每个问题问是否有一个大理石写着某个整数 x，如果是，还要回答哪个大理
石上写着。排序后的大理石从左到右编号为 1 ~N. （在样例中，为了节约篇幅，所有大理石上的数合并到一行，所有问题也合并到一行。）

样例输入：

4 1

2 3 5 1
5
1 3 3 3 1
样例输出：
CASE# 1 ：
5 found at 4
CAS E # 2 ：
2 not found
3 found at 3

# 分析

题目赘述不是很清晰，根据样例分析题目大意是：给出两个数大理石数 n 和可以询问的次数 q，输入 n 个数，然后询问数字，系统给出结果。

可以先用 algorithm 头文件中的 sort 和 lower_bound 函数

# 代码

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 10000;

int main() {
  int n, q, x, a[maxn], kase = 0;
  while(scanf("%d%d", &n, &q) == 2 && n) {//scanf函数返回成功读取的参数个数，并且变量n的值不为0。
    printf("CASE# %d:\n", ++kase);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a+n); // 排序，从位置a到位置a+n升序排列
    while(q--) {
      scanf("%d", &x);
      int p = lower_bound(a, a+n, x) - a; // 在已排序数组a中寻找x
      if(p < n && a[p] == x) printf("%d found at %d\n", x, p+1);
      else printf("%d not found\n", x);
    }
  }
  return 0;
}

# 不定长数组

C++ 中的 std::vector 是一个动态数组容器，它可以在运行时根据需要动态调整大小。 std::vector 是 C++ 标准库提供的一个常用容器，提供了许多方便的操作函数和方法，使得对数组的操作更加简单和高效。

使用 std::vector 需要包含 <vector> 头文件，并且使用 std 命名空间，或者通过 using namespace std; 进行命名空间的引入。

下面是一些 std::vector 的简单操作：

创建一个 std::vector ：

	#include <vector>

	std::vector<int> vec; // 创建一个整型 vector

在尾部插入元素：

	vec.push_back(10); // 在尾部插入元素 10
	vec.push_back(20); // 在尾部插入元素 20

获取 std::vector 的大小：

size_t size = vec.size(); // 获取 vector 的大小，此时 size 为 2

//size_t 类型通常用于表示数组的大小、容器的元素个数以及内存分配等操作。

//size_t 是 C++ 语言中用来表示大小或索引的无符号整数类型。

随机访问元素：

	int element = vec[0]; // 获取 vector 中索引为 0 的元素，即 10
	vec[1] = 30; // 修改 vector 中索引为 1 的元素为 30

遍历 std::vector ：

	for (size_t i = 0; i < vec.size(); i++) {
	std::cout << vec[i] << " "; // 输出 vector 中的元素
	}

使用迭代器遍历 std::vector ：

	for (auto it = vec.begin(); it != vec.end(); it++) {
	std::cout << *it << " "; // 输出 vector 中的元素
	}

插入和删除元素：

	vec.insert(vec.begin() + 1, 25); // 在索引为 1 的位置插入元素 25
	vec.erase(vec.begin() + 2); // 删除索引为 2 的元素

清空 std::vector ：

vec.clear(); // 清空 vector，此时 vec 为空

这些是一些 std::vector 的简单操作， std::vector 还支持更多的功能和方法，比如动态调整大小、查找元素、排序等等。在实际使用过程中，可以根据具体需求选择合适的操作函数来操作 std::vector 容器。

# 题目：木块问题

从左到右有 n 个木块，编号为 0 ~n-1 ，要求模拟以下 4 种操作（下面的 a 和 b 都是木块编号）。

move a onto b ：把 a 和 b 上方的木块全部归位，然后把 a 摞在 b 上面。
move a over b ：把 a 上方的木块全部归位，然后把 a 放在 b 所在木块堆的顶部。
pile a onto b ：把 b 上方的木块全部归位，然后把 a 及上面的木块整体摞在 b 上面。
pile a over b ：把 a 及上面的木块整体摞在 b 所在木块堆的顶部。

遇到 quit 时终止一组数据。a 和 b 在同一堆的指令是非法指令，应当忽略。
样例输入：
12 3 4
样例输出：
12 3 4 -> 3 0 8 7-> 8 35 2-> 617 4-> 617 4

# 分析

有确定的木块堆数 pile 但每个木块堆中的木块数量不确定，所以可以用动态数组 vector 来存。

# 代码

	#include <cstdio>
	#include <string>
	#include <vector>
	#include <iostream>
	using namespace std;

	const int maxn = 30;
	int n;
	vector<int> pile[maxn]; // 每个 pile [i] 是一个 vector

	// 找木块 a 所在的 pile 和 height，以引用的形式返回调用者
	void find_block(int a, int& p, int& h) {
	for(p = 0; p < n; p++)
	for(h = 0; h < pile[p].size(); h++)
	if(pile[p][h] == a) return;
	}

	// 把第 p 堆高度为 h 的木块上方的所有木块移回原位
	void clear_above(int p, int h) {
	for(int i = h+1; i < pile[p].size(); i++) {
	int b = pile[p][i];
	pile[b].push_back(b); // 把木块 b 放回原位
	}
	pile[p].resize(h+1); //pile 只应保留下标 0~h 的元素
	}

	// 把第 p 堆高度 h 及其上方的木块整体移动到 p2 堆的顶部
	void pile_onto(int p, int h, int p2) {
	for(int i = h; i < pile[p].size(); i++)
	pile[p2].push_back(pile[p][i]);
	pile[p].resize(h);
	}

	void print() {
	for(int i = 0; i < n; i++) {
	printf("%d:", i);
	for(int j = 0; j < pile[i].size(); j++) printf(" %d", pile[i][j]);
	printf("\n");
	}
	}

	int main() {
	int a, b;
	cin >> n;
	string s1, s2;
	for(int i = 0; i < n; i++) pile[i].push_back(i);
	while(cin >> s1 >> a >> s2 >> b) {
	int pa, pb, ha, hb;
	find_block(a, pa, ha);
	find_block(b, pb, hb);
	if(pa == pb) continue; // 非法指令
	if(s2 == "onto") clear_above(pb, hb);
	if(s1 == "move") clear_above(pa, ha);
	pile_onto(pa, ha, pb);
	}
	print();
	return 0;
	}

# 集合：set

在 C++ 中， std::set 是一个关联容器，它存储具有特定排序顺序的唯一元素集合。以下是对 std::set 的简单讲解以及一些常用的方法举例：

使用 std::set 需要包含头文件 <set> 。

创建和初始化 std::set ：

	std::set<int> mySet; // 创建一个空的 int 类型的 set
	std::set<int> mySet2 = {1, 2, 3, 4, 5}; // 创建并初始化一个包含元素的 set

插入元素：

	mySet.insert(42); // 插入单个元素
	mySet.insert({1, 2, 3}); // 插入多个元素

删除元素：

	mySet.erase(42); // 根据元素值删除元素
	mySet.clear(); // 清空 set 中所有的元素

访问元素：

	for (const auto& element : mySet) {
	std::cout << element << " ";
	}
	std::cout << std::endl;

查找元素：

	auto it = mySet.find(42); // 返回指向元素为 42 的迭代器，如果不存在则返回 end ()
	if (it != mySet.end()) {
	std::cout << "Element found: " << *it << std::endl;
	} else {
	std::cout << "Element not found" << std::endl;
	}

获取集合大小和判断集合是否为空：

	int size = mySet.size(); // 返回 set 中元素的个数
	bool isEmpty = mySet.empty(); // 判断 set 是否为空

std::set 中的元素会自动按照升序排序，并且每个元素在 set 中是唯一的，不会出现重复值。这使得 std::set 常用于需要快速查找、插入和删除元素，并且要求元素有序的场景。

# 题目：安迪的第一个字典

输入一个文本，找出所有不同的单词（连续的字母序列），按字典序从小到大输出。
单词不区分大小写。
样例输入：
Adventures in DisneyIand
Two blondes were going to Disney1and when they came to a fork in the
road ， The sign read: "Disney1and Left."
So they went home .
样例输出（为了节约篇幅只保留前 5 行）：
adventures
blondes
C ame
disneyland

# 分析

利用 set 的有序和唯一性，挨个把字符串输入到 set 内，然后输出。需要注意输入时把非字母转行成空格，然后利用 stringstream 得到各个单词。

# 代码

	#include<iostream>
	#include<string>
	#include<set>
	#include<sstream>
	using namespace std;

	set<string> dict;
	string s, buf;

	int main() {
	while(cin >> s) {
	for(int i = 0; i < s.length(); i++)
	if(isalpha(s[i])) s[i] = tolower(s[i]); else s[i] = ' ';
	stringstream ss(s);
	while(ss >> buf) dict.insert(buf);// 从 ss 中读取到 buf 中，然后插入到 dict 中
	}
	// 迭代器遍历，分别为迭代器类型，元素，遍历头，遍历尾（条件是头不等于尾，即全部遍历）
	for(set<string>::iterator it = dict.begin(); it != dict.end(); ++it)
	cout << *it << "\n";
	return 0;
	}

# 映射：map

在 C++ 中， std::map 是一个关联容器，它提供了一种将键和值进行关联的方式。 std::map 中的元素是按照键的顺序进行排序的，并且每个键都是唯一的。下面我将为您讲解一下 std::map 的基本用法，并举例一些常用的方法。

# 基本用法

首先，您需要包含相应的头文件：

#include <map>

然后，您可以使用 std::map 来定义一个键 - 值关联的容器：

std::map<int, std::string> myMap;

上述代码定义了一个以整数为键、字符串为值的 std::map 。

接下来，我将为您列举一些常用的方法：

# 插入元素

您可以使用 insert 方法向 std::map 中插入元素：

	myMap.insert(std::make_pair(1, "One"));
	myMap[2] = "Two";

# 访问元素

使用键来访问对应的值：

std::string value = myMap[1];

# 遍历元素

使用迭代器来遍历整个 std::map ：

	for (auto it = myMap.begin(); it != myMap.end(); ++it) {
	std::cout << it->first << ": " << it->second << std::endl;
	}

# 查找元素

使用 find 方法来查找特定的键：

	auto it = myMap.find(2);
	if (it != myMap.end()) {
	std::cout << "Found key 2, value is " << it->second << std::endl;
	} else {
	std::cout << "Key 2 not found" << std::endl;
	}

# 删除元素

使用 erase 方法来删除特定的键值对：

myMap.erase(1);

以上是 std::map 的一些基本用法和方法示例。希望能帮助到您理解并使用 std::map 。

# 题目：反片语

输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文本中的另外一个单词。在判断是否满足条件时，字母不分大小写，但在输出时应保留输入中的大小写，按字典序进行排列（所有大写字母在所有小写字母的前面）。

# 分析

这道题目的意思是读取一系列单词，并输出其中只出现一次的单词（按字典序排序）。

可以利用 map 的键值特点，先将每个单词按字典顺序重排，然后输入到 map 中利用值计数，再存储只出现一次的单词，最后按原顺序输出即可

# 代码

	// 题意：输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排得到输入文本中的另外一个单词
	// 算法：把每个单词 “标准化”，即全部转化为小写字母然后排序，然后放到 map 中进行统计
	#include<iostream>
	#include<string>
	#include<cctype>
	#include<vector>
	#include<map>
	#include<algorithm>
	using namespace std;

	map<string,int> cnt;
	vector<string> words;

	// 将单词 s 进行 “标准化”
	// 将单词转换为小写并按字母顺序排序，返回转换后的结果。
	string repr(string s) {
	string ans = s;
	for(int i = 0; i < ans.length(); i++)
	ans[i] = tolower(ans[i]);
	sort(ans.begin(), ans.end());
	return ans;
	}

	int main() {
	int n = 0;
	string s;
	while(cin >> s) {
	if(s[0] == '#') break;
	words.push_back(s);
	string r = repr(s);
	if(!cnt.count(r)) cnt[r] = 0;//map 里没有，加入并把对应值设为 0
	cnt[r]++;
	}
	vector<string> ans;// 用来存储只存在一次的单词
	for(int i = 0; i < words.size(); i++)
	//word 中标准格式存在一次的将其原型加入 ans
	if(cnt[repr(words[i])] == 1) ans.push_back(words[i]);
	sort(ans.begin(), ans.end());
	for(int i = 0; i < ans.size(); i++)
	cout << ans[i] << "\n";
	return 0;
	}

# 栈、队列、优先队列

C++ 中的栈（Stack）和队列（Queue）是两种最基本的数据结构，而优先队列（Priority Queue）则是一种较为特殊的队列。

栈（Stack）

栈是一种后进先出（LIFO）的数据结构，即最后进入的元素最先弹出。在 C++ 中可以使用 std::stack 模板实现栈的功能。常用的方法及其作用如下：

push() ：向栈中压入一个元素；
pop() ：从栈顶弹出一个元素；
top() ：返回栈顶的元素；
empty() ：判断栈是否为空；
size() ：返回栈中元素的数量。

示例代码：

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    while (!s.empty()) {
        cout << s.top() << " "; // 输出 3 2 1
        s.pop();
    }
    return 0;
}

队列（Queue）

队列是一种先进先出（FIFO）的数据结构，即最先进入的元素最先弹出。在 C++ 中可以使用 std::queue 模板实现队列的功能。常用的方法及其作用如下：

push() ：向队列尾部插入一个元素；
pop() ：从队列头部弹出一个元素；
front() ：返回队列头部的元素；
back() ：返回队列尾部的元素；
empty() ：判断队列是否为空；
size() ：返回队列中元素的数量。

示例代码：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    while (!q.empty()) {
        cout << q.front() << " "; // 输出 1 2 3
        q.pop();
    }
    return 0;
}

优先队列（Priority Queue）

优先队列是一种可以自动排序的队列，每次弹出的元素都是队列中优先级最高的元素。在 C++ 中可以使用 std::priority_queue 模板实现优先队列的功能。常用的方法及其作用如下：

push() ：向优先队列中插入一个元素；
pop() ：从优先队列中弹出一个元素；
top() ：返回优先队列中优先级最高的元素；
empty() ：判断优先队列是否为空；
size() ：返回优先队列中元素的数量。

示例代码：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq; // 默认降序排列
    pq.push(1);
    pq.push(3);
    pq.push(2);
    while (!pq.empty()) {
        cout << pq.top() << " "; // 输出 3 2 1
        pq.pop();
    }
    return 0;
}

在默认情况下， std::priority_queue 是一个降序排列的容器。如果要使用升序排列的优先队列，则需要指定其比较函数：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq; // 升序排列
    pq.push(1);
    pq.push(3);
    pq.push(2);
    while (!pq.empty()) {
        cout << pq.top() << " "; // 输出 1 2 3
        pq.pop();
    }
    return 0;
}

上述代码中，第一个参数 int 表示优先队列的元素类型，第二个参数 vector<int> 表示底层容器的类型，第三个参数 greater<int> 表示使用升序比较函数。

# 题目：集合栈计算机

有一个专门为了集合运算而设计的 “集合栈” 计算机。该机器有一个初始为空的栈，并且支持以下操作：

PUSH：将空集 {} 入栈

DUP：把当前栈顶元素复制一份后再入栈

UNION：出栈两个集合，然后把两者的并集入栈

INTERSECTION：出栈两个集合，然后把两者的交集入栈

ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈

每次操作后，输出栈顶集合的大小（即元素个数）

# 分析

假设有以下输入数据：

2
5
PUSH
ADD
UNION
DUP
INTERSECT
3
PUSH
ADD
DUP

根据上面的代码，对于第一组数据，操作流程如下：

栈：[空集]
- PUSH 操作：栈变为 [空集，空集]
- ADD 操作：将两个空集取并集得到空集，栈变为 [空集]
- UNION 操作：栈变为 [空集，空集]
- DUP 操作：栈变为 [空集，空集，空集]
- INTERSECT 操作：将栈顶的两个空集取交集得到空集，栈变为 [空集]
栈：[空集]
- PUSH 操作：栈变为 [空集，空集]
- ADD 操作：将两个空集取并集得到空集，栈变为 [空集]

因此，根据每次操作后输出当前栈顶元素对应的集合大小，输出结果为：

0
0
***

# 代码

	// UVa12096 The SetStack Computer
	// Rujia Liu
	#include<iostream>
	#include<string>
	#include<set>
	#include<map>
	#include<stack>
	#include<vector>
	#include<algorithm>
	using namespace std;

	#define ALL(x) x.begin(),x.end()
	#define INS(x) inserter(x,x.begin())

	typedef set<int> Set;
	map<Set,int> IDcache; // 把集合映射成 ID
	vector<Set> Setcache; // 根据 ID 取集合

	// 查找给定集合 x 的 ID。如果找不到，分配一个新 ID
	int ID (Set x) {
	if (IDcache.count(x)) return IDcache[x];
	Setcache.push_back(x); // 添加新集合
	return IDcache[x] = Setcache.size() - 1;
	}

	int main () {
	int T;// 测试数据
	cin >> T;
	while(T--) {
	stack<int> s; // 题目中的栈
	int n;// 操作数
	cin >> n;
	for(int i = 0; i < n; i++) {
	string op;
	cin >> op;
	if (op[0] == 'P') s.push(ID(Set()));
	else if (op[0] == 'D') s.push(s.top());
	else {
	Set x1 = Setcache[s.top()]; s.pop();
	Set x2 = Setcache[s.top()]; s.pop();
	Set x;
	if (op[0] == 'U') set_union (ALL(x1), ALL(x2), INS(x));
	if (op[0] == 'I') set_intersection (ALL(x1), ALL(x2), INS(x));
	if (op[0] == 'A') { x = x2; x.insert(ID(x1)); }
	s.push(ID(x));
	}
	cout << Setcache[s.top()].size() << endl;
	}
	cout << "***" << endl;
	}
	return 0;
	}

# 题目：团队队列

有 t 个团队的人正在排一个长队。每次新来一个人时，如果他有队友在排队，那么这个新人会插队到最后一个队友的身后。如果没有任何一个队友排队，则他会排到长队的队尾。

输入要求支持如下指令：
ENQUEUE x y：x 团队编号为 y 的人进入长队。
DEQUEUE：长队的队首出队。
STOP：停止模拟
对于每个 DEQUEUE 指令，输出出队的人的编号。

# 分析

直接举例

假设有两个团队和每个团队有三个成员，他们的编号分别如下：

团队 1：成员编号为 1、2、3
团队 2：成员编号为 4、5、6

现在，我们将按照以下命令进行模拟排队操作：

首先，程序会读入一个整数 t ，表示场景中团队的数量。在此例中， t 的值为 2。

然后，程序会读入每个团队的成员信息，并将他们的团队编号保存到 team 中。根据上述信息，团队 1 的成员编号为 1、2、3，团队 2 的成员编号为 4、5、6。

接下来，程序进入无限循环，在每次循环中读入一个命令，并根据命令执行相应的操作。

命令 'E 1' 表示成员 1 到达，将其加入团队 1 的队列 q2[1] 中。此时 q2[1] 的队列中有成员 1。
命令 'E 2' 表示成员 2 到达，将其加入团队 2 的队列 q2[2] 中。此时 q2[2] 的队列中有成员 2。
命令 'E 3' 表示成员 3 到达，将其加入团队 3 的队列 q2[3] 中。由于团队 3 并不存在，因此需要将团队 3 加入团队队列 q 中，并将成员 3 加入团队 3 的队列 q2[3] 中。此时 q 的队列中有团队 3， q2[3] 的队列中有成员 3。
命令 'D' 表示队首的团队成员出队，并输出该成员的编号。由于 q2[1] 的队列中有成员 1，所以成员 1 出队，并输出编号 1。此时 q2[1] 的队列为空。
再次执行命令 'D'，由于 q2[2] 的队列中有成员 2，所以成员 2 出队，并输出编号 2。此时 q2[2] 的队列为空。
再次执行命令 'D'，由于 q2[3] 的队列中有成员 3，所以成员 3 出队，并输出编号 3。此时 q2[3] 的队列为空，同时团队 3 也会从团队队列 q 中移除。
最后执行命令 'S'，表示当前场景模拟结束。输出一个空行。

这样，第一个场景的模拟就完成了。接下来，程序会进入下一个场景的模拟。

希望这个例子能够帮助您更好地理解代码的执行过程。如果还有其他问题，请随时提问。

# 代码

	// UVa540 Team Queue
	// Rujia Liu
	#include<cstdio>
	#include<queue>
	#include<map>
	using namespace std;

	const int maxt = 1000 + 10;

	int main() {
	int t, kase = 0;
	while(scanf("%d", &t) == 1 && t) {
	printf("Scenario #%d\n", ++kase);

	// 记录所有人的团队编号
	map<int, int> team; //team [x] 表示编号为 x 的人所在的团队编号第一个 int 表示人员的编号，第二个 int 表示团队的编号。
	for(int i = 0; i < t; i++) {
	int n, x;
	scanf("%d", &n);// 团队人数
	while(n--) { scanf("%d", &x); team[x] = i; }
	}

	// 模拟
	queue<int> q, q2[maxt]; //q 是团队的队列，而 q2 [i] 是团队 i 成员的队列
	for(;;) {
	int x;
	char cmd[10];
	scanf("%s", cmd);
	if(cmd[0] == 'S') break;// 停止
	else if(cmd[0] == 'D') {// 队首出队
	int t = q.front();
	printf("%d\n", q2[t].front()); q2[t].pop();
	if(q2[t].empty()) q.pop(); // 团体 t 全体出队列
	}
	else if(cmd[0] == 'E') {// 入队
	scanf("%d", &x);
	int t = team[x];//x 所在团队的编号
	if(q2[t].empty()) q.push(t); // 团队 t 进入队列
	q2[t].push(x);
	}
	}
	printf("\n");
	}

	return 0;
	}

# 题目丑数

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 1500 个丑数。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。

# 分析

从小到大生成丑数，对应的 x，2x，3x，5x，也是丑数，将对应的丑数存入优先队列（从小到大排列），这里可以用 set 保证元素唯一

# 代码

	#include<iostream>
	#include<vector>
	#include<queue>
	#include<set>
	using namespace std;
	typedef long long LL;
	const int coeff[3] = {2, 3, 5};

	int main() {
	priority_queue<LL, vector<LL>, greater<LL> > pq;
	set<LL> s;
	pq.push(1);
	s.insert(1);
	for(int i = 1; ; i++) {
	LL x = pq.top(); pq.pop();
	if(i == 1500) {
	cout << "The 1500'th ugly number is " << x << ".\n";
	break;
	}
	for(int j = 0; j < 3; j++) {
	LL x2 = x * coeff[j];
	if(!s.count(x2)) { s.insert(x2); pq.push(x2); }
	}
	}
	return 0;
	}

算法 STL

# 排序与检索

# 题目：大理石在哪里？

# 分析

# 代码

# 不定长数组

# 题目：木块问题

# 分析

# 代码

# 集合：set

# 题目：安迪的第一个字典

# 分析

# 代码

# 映射：map

# 基本用法

# 插入元素

# 访问元素

# 遍历元素

# 查找元素

# 删除元素

# 题目：反片语

# 分析

# 代码

# 栈、队列、优先队列

# 题目：集合栈计算机

# 分析

# 代码

# 题目：团队队列

# 分析

# 代码

# 题目 丑数

# 分析

# 代码

hexo使用指南

数据结构

# 题目丑数