LightSummary

基础数据结构

数组 (Array) 占据一块连续的内存，索引和遍历速度快 (O(1)O(1))，但其他操作就慢了（插入、删除的时间复杂度是 O(n)O(n)），大小也不能伸缩

动态数组 (Dynamic Array) 可以随着数据量的增加而扩展（但理论上不能缩小），C++ 的 vector<T> 实现了这个数据结构。但是插入和删除依然很慢。

Note

可以参照一般数组使用，因此在使用下标访问时，请确保 vector 已经分配内存。圆括号用于指定空间大小，如果需要追加数据，请使用 push_back() 方法。

链表 (linked List) 基于节点 (node) 组成，在内存中一般不连续，C++ 的 list<T> 实现了这个数据结构（双向链表）。链表可以在 O(1)O(1) 复杂度下实现插入和删除操作，但访问操作又退化到 O(n)O(n) 了，所以很多时候也挺慢 😦

双向链表的定义
1
2
3
4
5
6
struct Node
{
	int data;
	Node* pNext;
	Node* pPrev;
};

数组的下标只能是非负整数，而散列表 (Hash Table) 可以以任意标识访问元素，因为它是键值对 (key-value pair) 组成的。散列表的查询、插入和删除速度都很快 (理论上是 O(1)O(1))。C++ 的 unordered_map<T, P> 和 unordered_set<T> 实现了这个数据结构。两者的不同在于 map 有键值对，是标准的散列表；而 set 没有，更像数学中的 “集合” 概念（既然是集合，那么 set 中的元素都是不重复的）。

注意到 “unordered” 了吗？散列表是不能排序的

先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为桶 (bucket)，每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value。

如何基于 key 定位对应的桶呢？这是通过散列函数 (hash function) 实现的。换句话说，我们通过散列函数为每个 key 分配（唯一的）桶位。

一个简单的散列函数
1
2
3
4
size_t hash(int key)
{
	return key % n; // n 为桶的数量
}

散列函数本身也是有运行成本的！

使用上面的散列函数，我们很快遇到一个问题：有好几个 key 指向同一个桶位！我们称之为散列冲突 (Hash Collision)。

散列冲突的一个解决方法是链式地址 (separate chaining)。我们将冲突的键值对通过链表（有时也用 vector<T>）连接起来，输入 key 后先遍历桶，再遍历桶下的冲突链。

队列 (Queue) 和栈 (Stack) 都是关于 push（推入）和 pop（弹出）的数组 / 队列，区别在于队列是先进先出 (FIFO) 的，栈是后进先出 (LIFO) 的。C++ 分别用 queue<T> 和 stack<T> 实现

二叉树 (Binary Tree) 是一个树状数据结构，用于快速搜索、插入和删除。它经常作为散列表的替代，速度稍慢 (O(log⁡N)O(\log{N}))，但使用时是排序好的

堆 (Heap) 是一种二叉树的特例，用数组实现，常用于优先队列 (priority queue)

实践部分

有些算法和数据结构可以直接用标准库的，毕竟这篇是 “功利性质” 的，就没有重复造轮子的必要了。

注意 “数据保证 XX”，这说明我们不需要考虑判断输入的数据是否符合 XX 条件，因为已经保证它符合这个 XX 条件了（系统不会在酒吧里点炒饭的）

考 FZU DS 原题，分为栈、队列、排序、二叉搜索树以及图和路径

CPP “万能” 文件头：<bits/stdc++.h>

下面是 DS 题目与配套的 AC 代码（感谢 LuminaryDawn 整理提供 😃）

另附 .pbs 文件，你可以导入小熊猫 C++ 实现本地自动判题：FZU DS.pbs

如果你想 “背诵”，建议背关键算法的描述，除非你认为自己真的能像背课文那样把一行行代码背下来

实际考试为了降低难度，较简单题的分数是比较高的。
注意 PTA 的补全提示很少，复习时不要依赖 IDE 的补全
如果想通过，总分应该在 50 分以上

表

亚克星上的军队

★实验任务

亚克星上住着许多神奇的生物。其中有聪慧的人族、优雅的精灵、彪悍的野蛮猪、粗鲁的首任驻….有一天，住在湛蓝球上的恶魔们突破空间的封锁入侵这个美丽的星球。为了保卫共同的家园，亚克星各族不得不摒弃前嫌，组成联盟。为了更有利的反击恶魔们的入侵，他们建立了统一的军事指挥中心。在前期，指挥中心会不停的发布军队调动命令，可是，麻烦来了。为了更好的做出决策，指挥中心必须迅速了解己方的各地区的军事力量详情。你能否帮帮这些可怜的种族呢？

每个地区有一个编号（从 1 到 N），如果一个地区有军队的话，这些军队将组成一个军团。指挥中心将发布的命令如下：

U a b:将 b 地区军团的调到 a 地区，从而组成一个新的军团。为了便于管理，每次新加入的军队将按顺序加入到 a 军团后面。数据保证 a 与 b 不相同。

I a x:将一支人数为 x 的军队调到 a 地区。为了便于管理，每次新加入的军队将加入到 a 军团前面。

D a x:将 a 地区中军队人数为 x 的调走。若不存在，则不执行。

Q a：询问 a 地区的具体军事信息（即按顺序输出该军团中每个军队的人数）。

★数据输入

输入第一行为两个正整数 N ,M (2 <= N,M <= 1000)。

接下来 N 行，每行第一个数 K 表示该地区军队的个数 K (1<=K<=100)，接下来 K 个数, 表示各个军队的人数信息 (0<=a_i < 2^31)。

接下来 M 行，每行一个操作。

★数据输出

对于每个询问操作，输出一行表示 a 地区具体军事信息，每两个数之间空格隔开，行末无空格。若 a 内无元素，输出 - 1。

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
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	// 基于流的 I/O 优化
	// std::cin.tie(nullptr); // 解除关联
	// std::ios::sync_with_stdio(false); // 关闭同步
	
	ll n,m; // n: 区域数；m: 操作数
	cin >> n >> m;
	
	vector<list<ll>> listt(n); // 存储各区域的军事信息
	
	for (ll i = 0; i < n; i++) {
		ll t;
		cin >> t; // t: 军队个数
		for (ll j = 0; j < t; j++) {
			ll temp;
			cin >> temp; // temp: 各军队人数
			listt[i].push_back(temp);
		}
	}
	
	for (ll i = 0; i < m; i++) {
		char type;
		cin >> type;
		
		if (type == 'U') {
			ll a,b;
			cin >> a >> b;
			a--;
			b--; // 编号从 1 到 N，减 1 和数组下标对齐
			listt[a].splice(listt[a].end(), listt[b]); // splice(a, b) 将 b 的内容转移到 this*，位置为 a
		}
		else if (type == 'I') {
			ll a,x;
			cin >> a >> x;
			a--;
			listt[a].push_front(x); // list 的向前插入
		}
		else if (type == 'D') {
			ll a,x;
			cin >> a >> x;
			a--;
			listt[a].remove(x); // remove() 移除符合特定条件的元素
		}
		else if (type == 'Q') {
			ll y;
			cin >> y;
			y--;
			
			if (listt[y].empty()) {
				cout << "-1\n";
			}
			else {
				bool first = true;
				for (auto j : listt[y]) {
					if (!first) cout << " ";
					cout << j;
					first = false;
				}
				cout << "\n";
			}
		}
	}
	
	return 0;
}

洗盘子

★实验任务

猪妈妈有很多小猪仔，每次吃完饭洗盘子是一个很大的问题。这天猪妈妈想出了一个方法。她让小猪们排成一队，从 2 开始给他们编号。每次排在最前面的不用洗盘子（假设它的编号是 i ），但是，排在它后面的第 i 只 ，2 i 只，3 i 只… 的小猪要洗盘子。让排在最前面以及要洗盘子的小猪出队，然后重复上述过程。那些不用洗盘子的小猪被称为幸运猪（lucky pigs），把它们的编号从小到大排序，现在要问第 n 个幸运猪的编号是多少。

比如说一开始，在最前面的小猪编号是 2，那么它不用洗盘子，出队。在它后面的第 2 只小猪，就是编号为 4 的小猪要洗盘子，编号为 6, 8, 10… 的小猪都要洗盘子，然后它们都出队。其中编号为 2 的小猪就是第一只幸运猪了。接下排在最前面的小猪编号是 3，它是幸运猪，出队。在它后面的第 3 只，就是编号为 9 的小猪要洗盘子，出队。以此类推。

★数据输入

输入第一行为 T ，代表接下去有 T 个询问， 0 < T <=300

接下去有 T 行，每行一个数 n ，0 < n <=3000

★数据输出

对于每个询问输出一行，为第 n 个幸运猪的编号。

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
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int T;
	cin >> T;
	
	vector<int> luckyPigs;
	vector<int> pigs;
	
	for (int i = 2; i <= 100000; i++) {
		pigs.push_back(i); // 初始化猪仔编号向量
	}
	
	while (luckyPigs.size() < 3000 && !pigs.empty()) { // 限制求解规模
		int lucky = pigs[0]; // 每次排在最前面的不用洗盘子
		luckyPigs.push_back(lucky); // 编号推入 luckyPigs 向量
		
		vector<int> keep; // 没被叫去洗盘子
		
		for (int j = 1; j < pigs.size(); j++) {
			if ((j % lucky) != 0) {
				keep.push_back(pigs[j]);
			}
		}
		
		pigs = keep;
	}
	
	while (T--) {
		int n;
		cin >> n;
		cout << luckyPigs[n - 1] << endl;
	}
	
	return 0;
}

队列

Rescue the princess

★实验任务

有一天，公主被一个魔王抓走关在一个城堡里面，城堡可以用 N * M 的矩阵来描述，1 < N, M <= 200。监狱由 N * M 个方格组成，每个方格中可能为墙壁，空地，怪物，公主或者是勇士。

现在勇士想去营救公主。他的任务是找到公主。约定，“找到公主” 的意思是到达公主被关的位置。如果勇士想到达某个方格，但方格中有怪物，那么必须杀死怪物，才能到达这个方格。假设勇士只能向上，下，左，右四个方向移动一步。移动一步的需要花费 1 个单位的时间，杀死怪物也需要一个单位的时间。

试着计算勇士找到公主需要多长时间。只能上，下，左，右移动，而且墙壁不能通过。

★数据输入

输入第一行包含 2 个整数 N，M，接下来 N 行，每行 M 个字符：. 代表空地，a” 表示公主，r 表示勇士， # 代表墙壁， x 表示怪物。（测试数据中 a 和 r 只有一个）。

★数据输出

输出一个整数，表示找到公主所需要最短的时间。如果无法找到公主，输出 - 1。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>

using namespace std;

struct Node {
	int x, y, time;
	// 重载大于运算符，比较两个 Node 等价于比较两个 Node.time
	bool operator>(const Node& other) const {
		return time > other.time;
	}
};

int main()
{
	int n, m;
	cin >> n >> m;
	vector<string> grid(n);
	int start_x=-1, start_y =-1, end_x=-1, end_y=-1;
	
	// 读入地图，初始化坐标
	for(int i=0;i< n;i++){
		cin >> grid[i];
		for(int j=0;j<m;j++){
			if(grid[i][j] == 'r'){
				start_x = i;
				start_y = j;
			}
			if(grid[i][j] == 'a'){
				end_x = i;
				end_y = j;
			}
		}
	}
	
	// 方向向量，表示移动方式
	int dx[4] = {0, 0, 1, -1}; // 上：-1，下：1
	int dy[4] = {1, -1, 0, 0}; // 左：-1，右：1
	
	// 每个格子相对于起点的路径距离（时间成本），初始化为“无穷大”
	vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
	dist[start_x][start_y] = 0;
	
	// 定义最小堆，堆顶元素必定最小。great 表示大于队尾元素的插入元素进入队尾，否则插入队尾元素之前。最大堆用 less
    // 存储待探索的点，按距离升序排序
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	
	// 起点作为第一个待探索点
	pq.push({start_x, start_y, 0});
	
	while(!pq.empty())
	{
		Node curr = pq.top(); // 当前位置
		pq.pop(); // 将该点弹出待探索堆。之后此点不再探索
		int x = curr.x;
		int y = curr.y;
		int time = curr.time;
        // 剪枝。这说明你是从较远路径来到这个点的，而根据我们的走法，已经有“人”探索接下来的路了，因此不要重复探索。
		if(time > dist[x][y]){
			continue;
		}
		// 向 4 个方向探索
		for(int i=0;i<4;i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			// 探测边界和墙壁
			if(nx < 0 || nx >= n || ny < 0 || ny > m || grid[nx][ny] == '#'){
				continue;
			}
			int new_time = time + 1; // 前进 1 步
			// 遇怪增加时间
			if(grid[nx][ny] == 'x'){
				new_time ++;
			}
			// 如果找到更短路径，则更新路径距离
			if(new_time < dist[nx][ny]){
				dist[nx][ny] = new_time;
				pq.push({nx, ny, new_time}); // 把点推入待探索堆中
			}
		}
	}
	if(dist[end_x][end_y] != INT_MAX){
		cout << dist[end_x][end_y] << "\n";
	}
	else
	{
		cout << "-1" << "\n";
	}
}

交易

考了

★实验任务

作为炉石传说的发牌员，你的任务就是发牌。从上到下有 n 张牌，编号 1~n。因为你和选手进行了一次 “交易”，所以当至少还剩两张牌时，发出最上面的牌，第二张牌放到最下面，重复这个过程直到只剩下一张牌。输出发牌的序列和最后剩下的牌。

★数据输入

第一行 1 个正整数 n (1=<n < 1000)

★数据输出

输出一行为发牌的序列，一行为最后剩下的牌。两个数字之间用空格隔开，末尾没有空格。

★Hint

第一个样例 n = 1, 只输出一行。

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 <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	queue<int> card;
    // 初始化牌堆
	for(int i=1;i<=n;i++){
		card.push(i);
	}
	bool isFirst = true;
	do
	{
		if(!isFirst){
			cout << " ";
		}
        // 输出第一张牌
		cout << card.front();
		card.pop();
		isFirst = false;
        // 第二张牌排到队尾
		if(!card.empty()){
			int second = card.front();
			card.pop();
			card.push(second);
		}
	}
	while(card.size() >= 2);
	cout << endl;
	if(!card.empty()){
		cout << card.front();
	}		
}

栈

火车

考了

★实验任务

TonyY 等火车无聊的时候，会去观察火车的排列，有一天他思考这么一个问题，火车总站的火车只能进站，要出站的话只能先出最后进站的那辆车，那么知道火车的进站顺序，能不能把它的出站顺序调整成火车站想要的呢？

★数据输入

输入第一行为一个正整数 n 表示火车辆数 (编号 1-n)（1<=n<=9）。

然后为两个长度为 n 的序列，表示火车的进站顺序和出站顺序。每辆火车刚好进出站各一次。

★数据输出

如果可以调整，输出 Yes 和出入站顺序。

如果不能，输出 No。

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

int main() {
	int n;
	cin >> n;
	
	string in_seq, out_seq;
	cin >> in_seq >> out_seq;
	
	stack<int> station;
	int out_index = 0;  // 当前应该出站的元素索引
	bool possible = true;
	
	// 模拟过程判断是否可能，并记录操作序列
	string operations[20]; // 最多 2 * 9 = 18 次操作
	int op_count = 0;
	
	for (int i = 0; i < n; i++) { // 由于出入站是单行的，因此每列列车有且只有一次进站和出站操作
		// 入站
		station.push(in_seq[i] - '0');
		operations[op_count++] = "in";
		
		// 检查能否出站，while 应对连续出站情况
		while (!station.empty() && station.top() == out_seq[out_index] - '0') {
			station.pop();
			operations[op_count++] = "out";
			out_index++;
		}
	}
	
	// 检查是否所有元素都正确出栈
	if (out_index != n) {
		possible = false;
	}
	
	if (possible) {
		cout << "Yes" << endl;
		// 输出缓存的操作序列
		for (int i = 0; i < op_count; i++) {
			cout << operations[i] << endl;
		}
	} else {
		cout << "No" << endl;
	}
	
	return 0;
}

价值

★实验任务

K 神最近喜欢上了刷题，一天不刷浑身难受。最近他研究发现，自己的人生价值在于他某段时间内的刷题总数乘上这几天刷题数的最小值，现在 K 神很寂寞（无敌是多么寂寞），想知道他人生价值最高的时候究竟有多高（krz）

★数据输入

第一行为总天数 N (1<=N<=100000)

接下来一行 N 个整数 ai（1<=ai<=100000），表示 K 神第 i 天的刷题数。

★数据输出

输出 K 神在连续一段时间内可能的最高价值 W。

对每个元素 a[i]，把它当作 “区间最小值”，看它能控制的最大区间，然后计算 a[i] * (这个区间的元素和)，取最大值。

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
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int num=n+5;
	vector<int>a(num), left(num), right(num);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}

	// 求前缀和，便于求区间和，例如区间 [a,b) 内的和为 sums[b-1] - sums[a]
	vector<long long>sums(n+1,0);
	for(int i=1;i<=n;i++){
		sums[i]=sums[i-1]+a[i];
	}

	// 求区间和就需要求上下边界
    // 将刷题数序列的每一个值都认为是属于某个区间的最小值，现在就是求最大的区间。

    // 使用单调栈排序下标
	stack<int>st;

    // 左边界，从左到右选择
	for(int i=1;i<=n;i++){
        // 如果当前栈顶的元素不小于要插入的元素，则弹出栈顶元素。注意一定要带等号，不然会出错
		while(!st.empty() && a[st.top()]>=a[i]){
			st.pop(); 
		}
		left[i]=st.empty()?0:st.top();
		st.push(i);
	}
    // 清空栈
	while(!st.empty())
		st.pop();
    // 右边界，从右到左选择
	for(int i=n;i>=1;i--){
        // 如果当前栈顶的元素小于要插入的元素，则弹出栈顶元素
		while(!st.empty() && a[st.top()]>a[i]){
			st.pop();
		}
		right[i]=st.empty()?(n+1):st.top();
		st.push(i);
	}
	long long maxx=0;
	for(int i=1;i<=n;i++){
		long long sum=sums[right[i]-1]-sums[left[i]];
		long long cur=a[i]*sum;
		maxx=max(maxx, cur);
	}
	cout<<maxx<<endl;
	return 0;
}

排序与选择

魔音吉他

考了

★问题描述

少年甲很喜欢音乐，有一天他来到了少年乙的村落。少年甲一曲高山流水，寻觅到了乙这位知音。然而，天下没有不散的宴席，少年甲要回村杀猪了，离别在即，少年乙拿出了自己珍藏多年的吉他，作为离别的礼物。就在少年甲欣喜之际，少年乙说，这把吉他变幻莫测，每次你拿起它的时候，它会有 n 根弦，每根弦可以演奏出 1018+110^{18}+1 个音符，而这 1018+110^{18}+1 个音符是连续的，取决于它每根弦的第一个音符（请看样例说明）。
此时，少年甲提出了一个疑问，如果给定一个区间 l，r（包括端点），里面共有几种不同的音符呢？少年乙对此谙熟于心，但是他想考验一下你，于是将这个问题抛给了你。

★数据输入

第一行一个正整数 n (1<=n<=100,000)，表示吉他有几根弦。
第二行共 n 个数 x，即代表对应弦的第一个音符 (0<=x<=101810^{18})。
第三行一个正整数 q (1<=q<=100,000)，表示少年甲的询问次数。
接下来 q 行，每行两个数 l，r (0<=l, r<=1018+110^{18}+1)，表示少年甲想要询问的区间。

★数据输出

输出共 q 个数，表示对应 q 个询问的答案。即询问区间内有多少个不同的音符。以空格隔开。

★样例说明

对应弦的第一个音符：3 1 4 1 5 9

列下标：0 1 2 3 4 5 ……
弦一： 3 4 5 6 7 8 ……
弦二： 1 2 3 4 5 6 ……
弦三： 4 5 6 7 8 9 ……
弦四： 1 2 3 4 5 6 ……
弦五： 5 6 7 8 9 10 ……
弦六： 9 10 11 12 13 14 ……

在第一根弦（最低音为 1）遇到的音符为 1、2、3，一共 3 个新音符。
在第二根弦（最低音为 3）遇到的音符为 3、4、5，一共 2 个新音符。
在第三根弦（最低音为 4）遇到的音符为 4、5、6，一共 1 个新音符。
在第四根弦（最低音为 5）遇到的音符为 5、6、7，一共 1 个新音符。
在第五根弦（最低音为 9）遇到的音符为 9、10、11，一共 3 个新音符。
区间 [0,2] 内有 1、2、3、4、5、6、7、9、10、11，共 10 个不同的音符。

★Hint

（1）询问区间 l，r 即为样例说明中的列下标。
（2）所谓不同音符个数，即区间 l，r 内 n 行内不同的数字个数。
（3）由于 l，r 的范围巨大，请思考其与每行第一个数字的关系（即给出的第一个音符）。

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
// 由“样例说明”可知，从第二根弦开始每根弦遇到的新音符数量受其与上一跟弦的差值影响即 a[i] - a[i-1]（比如 a[2] - a[1] = 3 - 1 =2, a[3] - a[2] = 4 - 3 = 1)，但如果其差值大于询问的区间长度 (r-l+1)，其增长的值就为其区间范围的值
// 则总的音符数为基弦的音符数（区间长度）+ 后面弦的新增音符数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> first(n);
    for (int i = 0; i < n; i++) {
        cin >> first[i];
    }
    //把弦的起始音符排个序
    sort(first.begin(), first.end());
    //求出相邻弦之间的差值
    vector<long long> diff;
    for (int i = 1; i < n; i++) {
        diff.push_back(first[i] - first[i - 1]);
    }
    sort(diff.begin(), diff.end());
    //计算前缀和（为了后面快速求和）
    vector<long long> pre(diff.size() + 1, 0);
    for (int i = 0; i < (int)diff.size(); i++) {
        pre[i + 1] = pre[i] + diff[i];
    }
    int q;
    cin >> q;
    for (int t = 0; t < q; t++) {
        long long l, r;
        cin >> l >> r;
        // 区间长度（包括两端）
        long long len = (r >= l) ? (r - l + 1) : 0;
        // 找出 <= len 的差值数量
        int k=upper_bound(diff.begin(),diff.end(),len)-diff.begin();
        // 计算 sum(min(len, diff[i]))
        long long summin = pre[k] + (long long)(diff.size() - k) * len;
        // 最终结果（音符总数）
        long long ans = len + summin;
        cout << ans; // 输出
        if (t != q - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

Just Sort

★实验任务

给定两个序列 a, b，序列 a 原先是一个单调递增的正数序列，但是由于某些原因，使得序列乱序了，并且一些数丢失了（用 0 表示）。经过数据恢复后，找到了正数序列 b ，且序列 a 中 0 的个数等于序列 b 的个数，打算使用序列 b 恢复序列 a。

对于序列 a 来说，我们可以交换两个位置上的非零的数，并且可以交换任意次。序列 b 同样也可以进行任意次交换。

现在要将序列 b 填充到序列 a 中的值丢失的位置上，序列 b 中的每个数只能填充一次，问最后构成的序列是否是单调递增的，如果是，则输出填充后的序列，否则输出 - 1。

★数据输入

输入给定 N, M，表示序列 a 和序列 b 的长度。

第一行为序列 a，第二行为序列 b。题目保证除了 0 以外的数，在序列 a 和 b 中只出现一次。

数据保证:

80% 的数据，N, M <= 100

100% 的数据，N, M <= 100000, 0 <= a [i] <= 100000, 0 < b [i] <= 100000

★数据输出

如果最后序列 a 是单调递增的，输出该序列，否则输出 -1。

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int a[N], b[N], c[N], vis[N];

void solve()
{
	int n, m;
	cin >> n >> m;
	int idx = 0;
	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		if(x==0){
			vis[i] = 1; // 标记序列 a 中缺失元素的位置
		}
		else
		{
			a[++idx] = x; // 收集 a 中非 0 的数
		}
	}
	for(int i = 1; i <= m; i++)
	{
		cin >> b[i];
	}
    // 允许任意交换意味着原始位置已经不重要了，只剩下“数的集合”重要
    // 问题变成：能否把“a 的非零数和 b 中的数”重新排列，按原位置规则放回（形成新序列），使整个序列严格递增？
	sort(a + 1, a + idx + 1); // std::sort(container.begin(), container.end());
	sort(b + 1, b + m + 1);
	int idx1 = 0, idx2 = 0;
	for(int i=1;i<=n;i++){
		if(vis[i]){
			c[i] = b[++idx1]; // 如果此位置是 a 中缺失的元素位置，那么用序列 b 填充
		}
		else
		{
			c[i] = a[++idx2]; // 如果没缺失，则用 a 中原本没缺失的元素填充
		}
		
		if(i > 1){
            // 发现填充违规，说明当前最小可用的数都不够大，而换用更大的数会把这个较小数留给后面更大的数，更难实现递增
			if(c[i] <= c[i - 1]){
				cout << "-1" << "\n";
				return;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(i != 1){
			cout << " ";
		}
		cout << c[i];
	}
	cout << "\n";
}

int main()
{
	solve();
}

树

文件管理器

好难 QAQ

背景

操作系统具有对计算机硬件资源管理和调度的功能。文件是对占用了硬盘一定空间的对象的描述和抽象。考虑一般的文件具有文件名、大小和创建时间。文件管理在任何操作系统中都是必不可少的。文件管理器是用户用来观察和操作文件的一个软件。考虑一个简易的文件管理器，用户可以通过这个简易的文件管理器对某个目录下文件最大/小、文件名 (字符串) 字典序最大/最小的一些文件，即按 XX 排序功能，此外文件管理器具有删除和添加文件的功能。输入保证目录只有一级，操作随机。

输入及输出格式

第 1 行输入一个 Q (1<=Q<=100000)，表示操作的次数。

第 2 - Q + 1 行输入一行操作序列

操作序列的格式为 op args

当 op = 1, 即第一种操作时，args 的格式为 folder name size，表示将要在某个 folder 目录 (1<=folder<=5 的整数) 下添加文件名为 name (1<=name<=100000 的整数) 的文件，文件大小为 size (1<=size<=100000 的整数)，如果文件名重复，就先删除原来的文件再进行 1 操作；

当 op = 2, 即第二种操作时，args 的格式为 folder name，表示将要在某个 folder 目录 (1<=folder<=5 的整数) 下删除文件名为 name (1<=name<=100000 的整数) 的文件，如果文件名不存在，操作不执行；

当 op = 3, 即第三种操作时，args 的格式为 folder k，表示输出某个目录下文件大小最大至第 k 大的文件名，如果大小相同按文件名数字从小到大输出，如果不满 k 个文件只需要输出已有的文件名，如果文件夹为空或不存在则输出一个空行；

当 op = 4, 即第四种操作时，args 的格式为 folder k，表示输出某个目录下文件名数字大小最小至第 k 小的文件名，如果不满 k 个文件只需要输出已有的文件名，如果文件夹为空或不存在则输出一个空行；

保证 1<= k <=10

备注

输出文件名以空格隔开，不输出多余的换行和空格

样例说明

样例输出为 8 个空行

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>
using namespace std;

struct node{
	int name,size;
};

class cmp{
	public:
		
		bool operator()(const node&x,const node&y)const{
			if(x.size!=y.size){
				return x.size>y.size;
			}else{
				return x.name<y.name;
			}
		}
};

map<int,int>folder[7];
set<node,cmp>s1[7];
//set<string>s2[7];

void solve()
{
	int op,idx,name,size,k;
	
	cin>>op>>idx;
	
	switch(op){
		case 1:
			cin>>name>>size;
			node t;
			t.name=name,t.size=size;
			
			if(folder[idx].count(name)){			
				s1[idx].erase(s1[idx].find({name,folder[idx][name]}));
			}
/*			else{
				s2[idx].insert(to_string(name));
			}*/
			
			s1[idx].insert(t);			
			folder[idx][name]=size;	
					
			break;
						
		case 2:
			cin>>name;
			
			if(folder[idx].count(name)){
				auto it=s1[idx].find({name,folder[idx][name]});

				s1[idx].erase(it);					

//				s2[idx].erase(to_string(name));	
				folder[idx].erase(name);							
			}
			
			break;
			
		case 3:
			cin>>k;
			
			if(!s1[idx].empty()){
				int cnt=0;
				for(auto el:s1[idx]){
					if(cnt){
						cout<<' ';
					}
					cout<<el.name;
					cnt++;
					if(cnt==k){
						break;
					}
				}
				
			}
			
			cout<<'\n';
			
			break;
			
		case 4:
			cin>>k;
			
/*			if(!s2[idx].empty()){
				int cnt=0;
				for(auto el:s2[idx]){
					if(cnt){
						cout<<' ';
					}					
					cout<<el;
					cnt++;
					if(cnt==k){
						break;
					}
				}
				
			}*/
	
			if(!folder[idx].empty()){
				int cnt=0;
				for(auto el : folder[idx]){
					if(cnt){
						cout<<' ';
					}					
					cout<<el.first;
					cnt++;
					if(cnt==k){
						break;
					}
				}
				
			}	
			
			cout<<'\n';
			
			break;			
	}	
	
}

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int t=1;
	
	cin>>t;
	
	while(t--){
		solve();
	}
    
    return 0;
}

鼹鼠报数

考了

★实验任务

Winder 养了一群会报数的鼹鼠，而且 Winder 喜欢用数字给他的鼹鼠们编号，如 “311”、“1048” 等。当然，为了不混淆，鼹鼠们的编号都是不同的。为了锻炼鼹鼠们的身体健康，Winder 决定让鼹鼠们进行掘土训练，顺便提高鼹鼠们的挖掘能力。
鼹鼠们排成一列，由第一个开始向下挖洞，并待在洞中。第二只与第一只相比，若编号值大的鼹鼠，则向右下方挖洞，否则向左下方。接下来的鼹鼠们以此类推，若比洞中所在鼹鼠编号值大，则向右下方走，否则向左下方。
训练结束后，Winder 会让他的鼹鼠们报数（既报出各自的编号）。通过报数的序列 Winder 想知道经过训练之后，鼹鼠们的位置是怎样的。
报数规则为：如果 A 鼹鼠的下方分别存在 ALeft 鼹鼠和 ARight 鼹鼠，则 ALeft 鼹鼠在 ARight 鼹鼠之前报数，ARight 鼹鼠在 A 鼹鼠之前报数。
位置表达式规则为：“根节点 <左子树表达式><右子树表达式>”,如左子树不存在, 则只输出 “根节点 <右子树表达式>”，右子树同理。

★数据输入

第一行为 N（2 < N<=1000），表示有 N 只鼹鼠。
第二行为 N 个整数 bi（0 < bi < 10000），表示报数顺序。

★数据输出

输出鼹鼠们的位置表达式。

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
// 报数过程就是二叉树的后序遍历
// 问题转化成：已知一棵 BST 的后序遍历序列，输出它的 “位置表达式”（先根 + 左右子树）

#include <iostream>
using namespace std;
const int MAX = 10000;
int a[MAX], n;
void dfs(int * a, int begin, int end) {
	bool l = 1;
	bool r = 1;
	cout << a[end]; // 后序遍历的最后一个一定是根
	int i = begin;

    // [ begin ... i-1 ] < root → 左子树
    // [ i ... end-1 ] > root → 右子树
	while (i < end && a[i]<a[end]) {
        i++;
    }
	if (i==begin) {
        l=0;
    }
	if (i==end) {
        r=0;
    }
	if (l) {
		cout << "<";
		dfs(a, begin, i - 1);
		cout << ">";
	}
	if (r) {
		cout << "<";
		dfs(a, i, end - 1);
		cout << ">";
	}
}
int main () {
	cin >> n;
	for (int i=1; i<=n; i++){
        cin>>a[i];
    }
	dfs(a, 1, n);	
	return 0;
}

散列表

Sins of a Solar Empire P7

★实验任务

正如你所知道 sins 是一个贪玩的不得了的小 P 孩（如果你非常讨厌他可以直接跳到第二段），你也知道他最近很喜欢玩一个叫做太阳帝国的原罪的策略游戏我向你保证这是太阳帝国原罪系列的第七章了。
现在 sins 拥护 N 个星球，每个星球 m 种不同的资源，每个资源都拥有一个编号 A，对于 sins 来说 N 个星球都有的资源才是最宝贵的，他想知道这样的资源有哪些？

★数据输入

第 1 行是正整数 N（1<=N<=1000）。
第 2~N + 1 行各有一个正整数 m 和 m 个正整数编号 A (有重复)，（0 < m<=1000, 0 <= A <=10^9）.

★数据输出

第一行一个整数 S，表示 N 个星球都拥有的资源个数。
如果 S 不等于 0 输出第二行，按照升序输出 S 个整数表示资源编号 (无重复)，资源编号之间有空格，结尾没有空格。

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 <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N;
    cin >> N;
    unordered_map<int, int> Count;
    for (int i = 0; i < N; ++i) {
        int m;
        cin >> m;
        unordered_set<int> only;
        for (int j = 0; j < m; ++j) {
            int A;
            cin >> A;
            only.insert(A);
        }
        for (int res : only) {
            Count[res]++;
        }
    }
    vector<int> common;
    for (const auto& pair : Count) {
        if (pair.second == N) {
            common.push_back(pair.first);
        }
    }
    sort(common.begin(), common.end());
    cout << common.size() << endl;
    if (!common.empty()) {
        for (int i = 0; i < common.size(); ++i) {
            if (i > 0) {
                cout << " ";
            }
            cout << common[i];
        }
        cout << endl;
    }
    return 0;
}

特殊匹配 R

★实验任务

定义一种语言 L，L 语言中所有的字符串只能由 abc 三个字母组成。
在语言 L 之上定义一种特殊匹配规则 R，R 的定义如下：假设有两个字符串 x 和 y，x 和 y 等长，且 x 与 y 有且只有一个位置上的字符不同。
例如字符串 x 为 “abc”：
（1）若字符串 y 为” abb”，这 x 与 y 符合 R 匹配；
（2）若 y 为” abc” 或” bbb” 或” abcc”，则 x 与 y 不符合 R 匹配。
现给定一个由 n 个 x 字符串构成的匹配表 r，然后进行 m 次询问。每次询问输入一个 y 字符串，然后判断 r 表中是否存在与 y 符合 R 匹配的 x 字符串，若有输出” YES”，否则输出” NO”。

★数据输入

输入中第一行给出一整数 n，m（1<=n,m<=1000）。
接下来 n 行给出 n 个 x 字符串。
接下来 m 行，每行输入一个 y 字符串进行询问。
题目保证每一个字符串的长度在 1000 以内。

★数据输出

对于 m 个询问，每个询问输出在 x 个字符串中是否有与 y 字符串符合 R 匹配的字符串，若有输出” YES”，否则输出” NO”。

★提示
60% 的数据 n<=100,m<=100
100% 的数据 n<=1000,m<=1000

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

int main() {
    int n, m;
    cin >> n >> m;
    unordered_set<string> x_set;
    vector<string> x_list;
    for (int i = 0; i < n; i++) {
        string x;
        cin >> x;
        x_set.insert(x);
        x_list.push_back(x);
    }
    for (int i = 0; i < m; i++) {
        string y;
        cin >> y;
        int len = y.length();
        bool found = false;
        for (const string& x : x_list) {
            if (x.length() != len) continue;
            int diff_count = 0;
            for (int j = 0; j < len; j++) {
                if (x[j] != y[j]) {
                    diff_count++;
                    if (diff_count > 1) break;
                }
            }  
            if (diff_count == 1) {
                found = true;
                break;
            }
        }
        cout << (found ? "YES" : "NO") << endl;
    }
    return 0;
}

优先队列

哈夫曼问题

★问题描述

对于给定的一个数列，求出用该数列构造 Huffman 树的总费用。

给出一列数 {pi}=p0,p1,…,pn−1\{p_i\}=p_0, p_1, …, p_{n-1}，用这列数构造 Huffman 树的过程如下：

  1. 找到 {pi}\{p_i\} 中最小的两个数，设为 pap_a和 pbp_b，将 pap_a和 pbp_b 从 {pi}\{p_i\} 中删除掉，然后将它们的和加入到 {pi}\{p_i\} 中。这个过程的费用记为 pa+pbp_a + p_b。
  2. 重复步骤 1，直到 {pi}\{p_i\} 中只剩下一个数。

在上面的操作过程中，把所有的费用相加，就得到了构造 Huffman 树的总费用。

例如，对于数列 {pi}\{p_i\}={5, 3, 8, 2, 9}，Huffman 树的构造过程如下：

  1. 找到 {5, 3, 8, 2, 9} 中最小的两个数，分别是 2 和 3，从 {pi}\{p_i\} 中删除它们并将和 5 加入，得到 {5, 8, 9, 5}，费用为 5。
  2. 找到 {5, 8, 9, 5} 中最小的两个数，分别是 5 和 5，从 {pi}\{p_i\} 中删除它们并将和 10 加入，得到 {8, 9, 10}，费用为 10。
  3. 找到 {8, 9, 10} 中最小的两个数，分别是 8 和 9，从 {pi}\{p_i\} 中删除它们并将和 17 加入，得到 {10, 17}，费用为 17。
  4. 找到 {10, 17} 中最小的两个数，分别是 10 和 17，从 {pi}\{p_i\} 中删除它们并将和 27 加入，得到 {27}，费用为 27。
  5. 现在，数列中只剩下一个数 27，构造过程结束，总费用为 5 + 10 + 17 + 27 = 59。

★数据输入

输入的第一行包含一个正整数 n（n<=100）。

接下来是 n 个正整数，表示 p0,p1,…,pn−1p_0, p_1, …, p_{n-1}，每个数不超过 1000。

★数据输出

用这些数构造 Huffman 树的总费用。

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

int main()
{
    int n;
    cin>>n;
    int a[100];
    for (int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int len=n;
    int total=0;
    while(len>1)
    {
        int min1=0,min2=1;
        if (a[min1]>a[min2])
            swap(min1,min2);
        for (int i=2;i<len;i++)
        {
            if (a[i]<a[min1])
            {
                min2=min1;
                min1=i;
            }
            else if(a[i]<a[min2])
            {
                min2=i;
            }
        }
        int sum=a[min1]+a[min2];
        total+=sum;
        a[min1]=sum;
        a[min2]=a[len-1];
        len--;
    }
    cout<<total<<endl;
    return 0;
}

森林冰火人

★实验任务

火人喜欢堆雪人。

已知火人在接下来的 N 天中，每天早上都会堆一个大小为 vi 的雪人。

但是火人的温度太高了！每天晚上，所有已存在的雪人的体积都会由于融化而减少 ti（若雪人体积不足 ti，则雪人体积融化至 0）。

问，每天融化的总体积为多少？

★数据输入

输入第一行为正整数 N (1<=N<=10^5)

第二行为 N 个正整数 vi (1<=vi<=10^5)，代表每天堆的雪人的体积。

第三行为 N 个正整数 ti (1<=ti<=10^5)，表示每天雪人融化的体积。

对于 80% 的数据， 1<=N<=100

对于 100% 的数据， 1<=N<=10^5

★数据输出

输出 N 个整数，代表每天融化的体积。（整数间以空格分隔）

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 <bits/stdc++.h> 
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >>N;
    vector<ll> v(N),t(N);
    for (int i=0;i<N;i++) 
        cin>>v[i];
    for (int i=0;i<N;i++) 
        cin>>t[i];
	struct compare {
    bool operator()(ll a,ll b) {
        return a>b; 
    }
};
    priority_queue<ll,vector<ll>,compare> pq_min;//最小堆
    ll sum=0;
    for (int i=0;i<N;i++) {
        pq_min.push(v[i]+sum);
        ll melt=0;
        while(!pq_min.empty() &&pq_min.top()<=sum+t[i]){
            melt+=pq_min.top()-sum;
            pq_min.pop();
        }
        melt+=pq_min.size()*t[i];
        sum+=t[i];
        cout<<melt<<" ";
    }
    cout<<endl;
    return 0;
}


并查集

转移炸弹

★实验任务

A 国有 N 个城市，这些城市编号为 1 到 N，有一天，他们调查出恐怖分子在每个城市中都安放了炸弹，于是他们给炸弹也编上了序号，第 i 个城市里的炸弹编号为 i。现在他们想把这些炸弹转移，以便于销毁炸弹。

由于炸弹是通过不同人转移的，所以需要一个指挥部门来记录转移炸弹的信息，以便于有些人要查询这些信息。我们有两个操作：

1. 将 a 炸弹目前所在城市中所有的炸弹转移到 b 炸弹所在的城市。

2. 询问 a 炸弹目前在哪个城市编号和这个城市中有炸弹个数。

★数据输入

输入第一行包含两个数 N,Q（1<=N<=500000 , 1<=Q<=120000）。分别表示城市的个数和操作数。

接下来有 Q 行，每行表示一个操作，第一种操作输入格式为 1 a b，第二种操作输入格式为 2 a。（1<=a,b<=N）

★数据输出

对于第一个操作，如果两个炸弹在同一个城市里，输出 “ERROR”，并不执行此操作。否则执行操作并不输出任何东西。

对于第二种操作，输出一行两个数表示炸弹所在的城市编号和该城市中炸弹个数，用一个空格分开。

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
#include <stdio.h>
#include <stdlib.h>

#define MAXN 500005

int parent[MAXN];  // 父节点
int city[MAXN];    // 炸弹当前所在的城市编号
int size[MAXN];    // 城市中的炸弹数量

// 查找根节点（带路径压缩）
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

int main() {
    int N, Q;
    scanf("%d %d", &N, &Q);
    
    // 初始化
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
        city[i] = i;    // 初始时炸弹i在城市i
        size[i] = 1;    // 每个城市初始有1个炸弹
    }
    
    while (Q--) {
        int op, a, b;
        scanf("%d", &op);
        
        if (op == 1) {
            scanf("%d %d", &a, &b);
            int ra = find(a);
            int rb = find(b);
            
            if (ra == rb) {
                printf("ERROR\n");
            } else {
                // 把a所在城市的所有炸弹转移到b所在城市
                // 合并集合，以rb为新的根
                parent[ra] = rb;
                size[rb] += size[ra];
                size[ra] = 0;
                // 更新城市编号：整个集合现在都在city[rb]城市
                city[rb] = city[rb]; // 保持不变
                // 注意：这里不需要更新city[ra]，因为ra不再是根节点
            }
        } else {
            scanf("%d", &a);
            int root = find(a);
            printf("%d %d\n", city[root], size[root]);
        }
    }
    
    return 0;
}

道路

★实验任务

某省调查城镇交通状况，得到现有城镇道路统计表，现给出每条道路连接的城镇编号，问当前的道路设计方案是否合理。

合理的方案为任意两个城镇之间可以相互到达，有且只有一条通路。

★数据输入

输入 a b (1<=a,b<=10,000)，表示城镇 a 和城镇 b 连通。输入包含多组数据，每组数据以 0 0 结束。

整个文件以 -1 -1 结尾

★数据输出

如果方案合法，输出 "Yes",否则输出 "No"。

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
67
68
69
#include<iostream>
#include<unordered_set>
using namespace std;
const int MAXN = 10005;
int parent[MAXN];
unordered_set<int> nodes;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void init() {
    for (int i = 1; i < MAXN; ++i) {
        parent[i] = i;
    }
    nodes.clear();
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        if (a == -1 && b == -1) break;
        init();
        bool has_cycle = false;
        int edge_count = 0;
        while (a != 0 || b != 0) {
            nodes.insert(a);
            nodes.insert(b);
            edge_count++;
            int rootA = find(a);
            int rootB = find(b);
            if (rootA == rootB) {
                has_cycle = true;
            }
			else {
                parent[rootA] = rootB;
            }
            cin >> a >> b;
        }
        if (has_cycle) {
            cout << "No\n";
        }
		else {
            if (nodes.empty()) {
                cout << "Yes\n";
            }
			else {
                int root = find(*nodes.begin());
                bool connected = true;
                for (int node : nodes) {
                    if (find(node) != root) {
                        connected = false;
                        break;
                    }
                }
                if (connected && edge_count == nodes.size() - 1) {
                    cout << "Yes\n";
                }
				else {
                    cout << "No\n";
                }
            }
        }
    }
    return 0;
}

图

图论难题

好难 QAQ
考了

★问题描述

数据结构与算法课程里面有各种求解最短路的算法，比如 floyd 算法、dijkstra 算法、bellman 算法。但该难题需要求解的不是最短路，而是求最短路的路径条数。

★实验任务

我们定义从 source 到达 target 的路径：source → u → v → target 是最短路，当且仅当该路径里面的所有边 (u，v) 满足：存在一条从 v 出发到终点的路径长度小于任意一条从 u 出发到终点的路径长度。

对于给定的一个无向无自环的图给你一个起点和一个终点，求出从起点到终点的最短路的路径条数。

★数据输入

第一行有两个正整数 N (1<=N<=1000), M (0<=M<=N(N−1)2\frac{N(N-1)}{2})。N 代表图 G 的顶点个数, M 代表图 G 有 M 条边。

接下来一共有 M 条边的描述，每条边的描述有三个整数 u (1<=u<=N), v (1<=v<=N), len (1<=len<=1000)。代表从 u 点到 v 点有一条边，且边的长度为 len。数据保证 u!=v 且不会出现重边。

最后一行有两个整数 S (1<=S<=N), T (1<=T<=N)，分别表示起点和终点。

★数据输出

输出一行为从 S 到 T 的最短路条数，如果 S 根本就走不到 T 就输出 - 1

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int N, M, S, T;
vector<pair<int, int>> graph[MAXN];
int dist[MAXN];
bool visited[MAXN];
vector<int> dag[MAXN];

void dijkstra(int start) {
    memset(dist, 0x3f, sizeof(dist));
    memset(visited, false, sizeof(visited));
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        for (auto &e : graph[u]) {
            int v = e.first;
            int w = e.second;
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        graph[u].push_back({v, len});
        graph[v].push_back({u, len});
    }
    cin >> S >> T;

    // 计算从T到所有点的最短距离
    dijkstra(T);

    if (dist[S] == INF) {
        cout << -1 << endl;
        return 0;
    }

    // 构建DAG：只包含从距离大的点指向距离小的点的边
    for (int u = 1; u <= N; u++) {
        for (auto &e : graph[u]) {
            int v = e.first;
            // 只添加满足条件的边：dist[u] > dist[v]
            if (dist[u] > dist[v]) {
                dag[u].push_back(v);
            }
        }
    }

    // 按到T的距离升序排序所有顶点（距离小的先处理）
    vector<int> nodes;
    for (int i = 1; i <= N; i++) {
        if (dist[i] < INF) {
            nodes.push_back(i);
        }
    }
    sort(nodes.begin(), nodes.end(), [](int a, int b) {
        return dist[a] < dist[b];
    });

    // 动态规划计算路径条数
    vector<ll> dp(N + 1, 0);
    dp[T] = 1;
    
    for (int v : nodes) {
        if (v == T) continue;
        for (int u : dag[v]) {
            dp[v] += dp[u];
        }
    }

    // 输出路径条数
    cout << dp[S] << endl;

    return 0;
}

最小生成树

★问题描述

给定平面上的 n 个点，添加一些边使得任何两个点之间都能相互到达，求添加的边的长度总和最小为多少

★数据输入

第一行一个正整数 n (1<=n<=5000)，表示序列有 n 个点，
接下来有 n 行，每行两个整数 xi 和 yi，（-1000000≤xi,yi≤1000000），表示 n 个点的坐标

★数据输出

添加的边的长度总和的最小值，四舍五入保留两位小数

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
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 5005;
double x[N], y[N]; // 坐标
double dist[N]; // 边长
bool vis[N]; // 树

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];

    for (int i = 1; i <= n; i++)
        dist[i] = 1e18;

    dist[1] = 0;        // 从第 1 个点开始做 Prim
    double ans = 0;

    for (int i = 1; i <= n; i++) {
        int u = -1;

        // 找当前未加入 MST 的最近点
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == -1 || dist[j] < dist[u]))
                u = j;
        }

        vis[u] = true;
        ans += dist[u];

        // 用 u 更新其他点的最小连边
        for (int v = 1; v <= n; v++) {
            if (!vis[v]) {
                double dx = x[u] - x[v];
                double dy = y[u] - y[v];
                double d = sqrt(dx*dx + dy*dy);
                if (d < dist[v]) dist[v] = d;
            }
        }
    }

    printf("%.2f\n", ans);
    return 0;
}

理论部分

破防了！弃坑！

参考资料
许可协议

本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。详见 版权协议

分享文章

想说些什么呢~