这里是paoxiaomo，一个现役ACMer，之后将会持续更新算法笔记系列以及笔试题题解系列
本文章面向想打ICPC/蓝桥杯/天梯赛等程序设计竞赛，以及各个大厂笔试的选手
感谢大家的订阅➕ 和 喜欢💗
有什么想看的算法专题可以私信博主

（本文题面由清隆学长收集）

01.K小姐的魔法药水

问题描述

K小姐是一位魔法师，她最近在研究一种神奇的魔法药水。这种药水由一系列魔法材料制成，每种材料都有一个正整数的魔法值。K小姐按照特定的规则将这些材料混合：每次她加入一种新的材料时，如果这种材料的魔法值与当前药水最上层材料的魔法值相同，她会取出这两种材料，将它们的魔法值相加后乘以 $2$，然后放回一种新的材料。此外，如果最上层材料的魔法值等于下面连续几种材料魔法值之和，她同样会取出这些材料，进行相同的操作。如果这两个条件都不符合，她就会简单地将新的材料加入到药水的最上层。

现在，K小姐按照一定顺序加入了一系列材料，请你计算最终药水中从上到下各层材料的魔法值。

输入格式

输入为一行，包含若干个由空格分隔的正整数，表示K小姐按顺序加入药水中的材料的魔法值。

输出格式

输出为一行，包含若干个由空格分隔的正整数，表示最终药水中从上到下各层材料的魔法值。

样例输入

55 66 121 5 5

样例输出

10 242

数据范围

• 每个正整数的范围为 $1$ 到 $2^{31}-1$。
• 正整数的个数范围为 $1$ 到 $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$ 个座位，途径 $n$ 个站点（编号从 $0$ 到 $n-1$）。在发车前，已经有 $x$ 名乘客预定了座位。

为了让列车的运营效率最大化，K小姐需要合理安排乘客的座位。她定义了一个指标叫做"座位利用数"，即每个座位被使用的站数之和。例如，某列车有 $2$ 个座位，第一个座位从第 $0$ 站到第 $10$ 站都有人坐（即从第 $0$ 站上车，第 $10$ 站下车，第 $10$ 站本身不占座，利用数为 $10-0=10$），第二个座位从第 $1$ 站到第 $9$ 站都有人坐，则总的座位利用数为 $(10-0)+(9-1)=18$。

现在，K小姐希望设计一个算法，计算出如何分配座位，才能使得座位利用数最大。同时，她需要保证在任意时刻，列车上的乘客数都不超过座位数 $m$。乘客下车后，其他乘客可以立即使用该座位，不用考虑换座的问题。

你能帮助K小姐完成这个任务吗？

输入格式

第一行包含三个正整数 $m,n,x$，分别表示列车的座位数、经停站点数和预定乘客数。

接下来 $x$ 行，每行包含两个整数 $u_i,v_i$，表示第 $i$ 位乘客的上车站点编号和下车站点编号。

输出格式

输出一个整数，表示最大的座位利用数。

样例输入

2 11 4
0 1
1 9
0 10
3 8

样例输出

19

数据范围

• $1\le m\le 9$
• $2\le n\le 20$
• $1\le x\le 9$
• $0\le u_i<v_i\le n-1$

【题目解析】

这道题的目标是设计一个算法，以最大化列车座位的利用数。具体要求是在保证任意时刻列车上的乘客数不超过座位数的前提下，安排乘客的座位。我们需要一个数据结构来记录每个座位的使用情况。由于座位是按顺序的，可以使用一个数组或向量来表示每个座位的利用情况。然后，我们可以遍历每位乘客的上车和下车站点，更新座位的利用情况。首先读取输入的列车座位数、经停站点数和预定乘客数。然后，它创建一个长度为座位数的向量 seatUtilization 来记录每个座位的利用情况，并将其初始化为全 0。接下来，它遍历每位乘客的上车和下车站点，更新每个座位在乘客乘坐期间的利用情况。最后，它计算总的座位利用数并输出。

cpp

#include <iostream>
#include <vector>using namespace std;int main() {int m, n, x;cin >> m >> n >> x;// 记录每个座位的利用情况，初始化为 0vector<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$ 个材料，第二个数为材料编号 $a$，后面 $n-1$ 个数为 $a$ 所依赖的材料编号。任意材料编号 $i$ 满足 $0<i<10000$。

输出格式

输出一行，包含若干个由空格分隔的正整数，表示找到的循环依赖。从最小的材料编号开始，按照依赖关系顺序输出，以最小的材料编号结束。

样例输入

3
3 1 2 5
3 2 3 4
2 3 1

样例输出

1 2 3 1

数据范围

• $1\le N\le 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;
}

整理试题不易，你的关注是我更新的最大动力！关注博主 带你看更多面试及竞赛试题和实用算法。