这里是paoxiaomo，一个现役ACMer，之后将会持续更新算法笔记系列以及笔试题题解系列
本文章面向想打ICPC/蓝桥杯/天梯赛等程序设计竞赛，以及各个大厂笔试的选手
感谢大家的订阅➕ 和 喜欢💗
有什么想看的算法专题可以私信博主
（本文题面由清隆学长收集）
01.K小姐的魔法药水
问题描述
K小姐是一位魔法师，她最近在研究一种神奇的魔法药水。这种药水由一系列魔法材料制成，每种材料都有一个正整数的魔法值。K小姐按照特定的规则将这些材料混合：每次她加入一种新的材料时，如果这种材料的魔法值与当前药水最上层材料的魔法值相同，她会取出这两种材料，将它们的魔法值相加后乘以 2 2 2，然后放回一种新的材料。此外，如果最上层材料的魔法值等于下面连续几种材料魔法值之和，她同样会取出这些材料，进行相同的操作。如果这两个条件都不符合，她就会简单地将新的材料加入到药水的最上层。
现在，K小姐按照一定顺序加入了一系列材料，请你计算最终药水中从上到下各层材料的魔法值。
输入格式
输入为一行，包含若干个由空格分隔的正整数，表示K小姐按顺序加入药水中的材料的魔法值。
输出格式
输出为一行，包含若干个由空格分隔的正整数，表示最终药水中从上到下各层材料的魔法值。
样例输入
55 66 121 5 5
样例输出
10 242
数据范围
- 每个正整数的范围为 1 1 1 到 2 31 − 1 2^{31}-1 231−1。
- 正整数的个数范围为 1 1 1 到 1000 1000 1000。
【题目解析】
我们使用栈来模拟药水的层叠过程。
1，依次读取输入的魔法值，如果当前魔法值与栈顶元素不相同，则将其压入栈中。
2，如果当前魔法值与栈顶元素相同，则取出栈顶元素，将其魔法值乘以2，直到栈顶元素与当前魔法值不相同或栈为空。
最后，依次从栈中取出元素，按照从上到下的顺序输出它们的魔法值。
cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
stack<int> magicStack;
int magic;
while (cin >> magic) {
if (magicStack.empty() || magic != magicStack.top()) {
magicStack.push(magic);
} else {
int currentMagic = magicStack.top();
magicStack.pop();
while (!magicStack.empty() && magicStack.top() == currentMagic) {
currentMagic *= 2;
magicStack.pop();
}
magicStack.push(currentMagic);
}
}
vector<int> result;
while (!magicStack.empty()) {
result.push_back(magicStack.top());
magicStack.pop();
}
for (int i = result.size() - 1; i >= 0; --i) {
cout << result[i];
if (i != 0) {
cout << " ";
}
}
return 0;
}
02.K小姐安排座位
题目描述
K小姐是一名列车长，她负责管理一列从北京开往上海的列车。这列火车共有 m m m 个座位，途径 n n n 个站点（编号从 0 0 0 到 n − 1 n-1 n−1）。在发车前，已经有 x x x 名乘客预定了座位。
为了让列车的运营效率最大化，K小姐需要合理安排乘客的座位。她定义了一个指标叫做"座位利用数"，即每个座位被使用的站数之和。例如，某列车有 2 2 2 个座位，第一个座位从第 0 0 0 站到第 10 10 10 站都有人坐（即从第 0 0 0 站上车，第 10 10 10 站下车，第 10 10 10 站本身不占座，利用数为 10 − 0 = 10 10-0=10 10−0=10），第二个座位从第 1 1 1 站到第 9 9 9 站都有人坐，则总的座位利用数为 ( 10 − 0 ) + ( 9 − 1 ) = 18 (10-0)+(9-1)=18 (10−0)+(9−1)=18。
现在，K小姐希望设计一个算法，计算出如何分配座位，才能使得座位利用数最大。同时，她需要保证在任意时刻，列车上的乘客数都不超过座位数 m m m。乘客下车后，其他乘客可以立即使用该座位，不用考虑换座的问题。
你能帮助K小姐完成这个任务吗？
输入格式
第一行包含三个正整数 m , n , x m,n,x m,n,x，分别表示列车的座位数、经停站点数和预定乘客数。
接下来 x x x 行，每行包含两个整数 u i , v i u_i,v_i ui,vi，表示第 i i i 位乘客的上车站点编号和下车站点编号。
输出格式
输出一个整数，表示最大的座位利用数。
样例输入
2 11 4
0 1
1 9
0 10
3 8
样例输出
19
数据范围
- 1 ≤ m ≤ 9 1 \le m \le 9 1≤m≤9
- 2 ≤ n ≤ 20 2 \le n \le 20 2≤n≤20
- 1 ≤ x ≤ 9 1 \le x \le 9 1≤x≤9
- 0 ≤ u i < v i ≤ n − 1 0 \le u_i < v_i \le n-1 0≤ui<vi≤n−1
【题目解析】
这道题的目标是设计一个算法，以最大化列车座位的利用数。具体要求是在保证任意时刻列车上的乘客数不超过座位数的前提下，安排乘客的座位。我们需要一个数据结构来记录每个座位的使用情况。由于座位是按顺序的，可以使用一个数组或向量来表示每个座位的利用情况。然后，我们可以遍历每位乘客的上车和下车站点，更新座位的利用情况。首先读取输入的列车座位数、经停站点数和预定乘客数。然后，它创建一个长度为座位数的向量 seatUtilization 来记录每个座位的利用情况，并将其初始化为全 0。接下来，它遍历每位乘客的上车和下车站点，更新每个座位在乘客乘坐期间的利用情况。最后，它计算总的座位利用数并输出。
cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int m, n, x;
cin >> m >> n >> x;
// 记录每个座位的利用情况，初始化为 0
vector<int> seatUtilization(m, 0);
// 输入每位乘客的上车和下车站点
for (int i = 0; i < x; ++i) {
int u, v;
cin >> u >> v;
// 更新每个座位的利用情况
for (int j = u; j < v; ++j) {
seatUtilization[j]++;
}
}
// 计算总的座位利用数
int totalUtilization = 0;
for (int utilization : seatUtilization) {
totalUtilization += utilization;
}
cout << totalUtilization << endl;
return 0;
}
03.K小姐的魔法材料
问题描述
K小姐是一位魔法师，她正在研究一些魔法材料。这些材料之间存在着一些依赖关系，一种材料可以依赖于多种其他材料（不包括自己，被依赖的材料不会重复），一种材料也可以被多种材料所依赖。
在这些依赖关系中，总是存在唯一的循环依赖。K小姐想要找出这个循环依赖，你能帮助她吗？
输入格式
第一行包含一个正整数 N N N，表示依赖关系的个数。
接下来 N N N 行，每行表示一个依赖关系，包含若干个由空格分隔的正整数。第一个数 n n n 表示后面有 n n n 个材料，第二个数为材料编号 a a a，后面 n − 1 n-1 n−1 个数为 a a a 所依赖的材料编号。任意材料编号 i i i 满足 0 < i < 10000 0 < i < 10000 0<i<10000。
输出格式
输出一行，包含若干个由空格分隔的正整数，表示找到的循环依赖。从最小的材料编号开始，按照依赖关系顺序输出，以最小的材料编号结束。
样例输入
3
3 1 2 5
3 2 3 4
2 3 1
样例输出
1 2 3 1
数据范围
- 1 ≤ N ≤ 10000 1 \le N \le 10000 1≤N≤10000
- 0 < i < 10000 0 < i < 10000 0<i<10000
【题目解析】
这个问题可以使用拓扑排序来解决。我们可以先构建一个有向图，其中材料之间的依赖关系可以表示为有向边。然后，我们对这个有向图进行拓扑排序，找到循环依赖的起点。首先读取输入的依赖关系个数 N，并读入每个依赖关系。然后，它构建一个有向图，表示材料之间的依赖关系，并找到起点节点。接下来，它对这个有向图进行拓扑排序，找到循环依赖的起点，并输出循环依赖路径。
cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
// 有向图的节点
struct Node {
int val;
vector<Node*> neighbors;
Node(int x) : val(x) {}
};
// 构建有向图
Node* buildGraph(unordered_map<int, Node*>& graph, vector<vector<int>>& dependencies) {
for (auto& dependency : dependencies) {
int dependent = dependency[0];
for (int i = 1; i < dependency.size(); ++i) {
int dependee = dependency[i];
if (!graph.count(dependent)) graph[dependent] = new Node(dependent);
if (!graph.count(dependee)) graph[dependee] = new Node(dependee);
graph[dependee]->neighbors.push_back(graph[dependent]);
}
}
return graph[dependencies[0][0]]; // 返回任意一个节点作为起始节点
}
// 拓扑排序
vector<int> topologicalSort(Node* start) {
vector<int> result;
queue<Node*> q;
unordered_map<Node*, int> indegree;
// 计算每个节点的入度
q.push(start);
while (!q.empty()) {
Node* node = q.front();
q.pop();
for (Node* neighbor : node->neighbors) {
indegree[neighbor]++;
q.push(neighbor);
}
}
// 拓扑排序
q.push(start);
while (!q.empty()) {
Node* node = q.front();
q.pop();
result.push_back(node->val);
for (Node* neighbor : node->neighbors) {
if (--indegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
return result;
}
int main() {
int N;
cin >> N;
// 读入依赖关系
vector<vector<int>> dependencies(N);
for (int i = 0; i < N; ++i) {
int n;
cin >> n;
vector<int> dependency(n);
for (int j = 0; j < n; ++j) {
cin >> dependency[j];
}
dependencies[i] = dependency;
}
// 构建有向图并找到起点
unordered_map<int, Node*> graph;
Node* startNode = buildGraph(graph, dependencies);
// 拓扑排序
vector<int> result = topologicalSort(startNode);
// 输出循环依赖
for (int val : result) {
cout << val << " ";
}
cout << endl;
return 0;
}
整理试题不易，你的关注是我更新的最大动力！关注博主 带你看更多面试及竞赛试题和实用算法。