本文写的比较快，旨在帮助刚刚接触、不太了解STL的同学

如有任何问题或错误，欢迎使用个人主页的联系方式联系我，也可以评论留言（需登录GitHub）

程序设计实训 — 题目解析

写在前面

本文把每题的思路与关键代码逐段结合讲解，并在每题末尾内嵌了完整参考实现，便于复制运行。

提供完整的代码是方便大家自己学习，任何情况下你都不应该直接复制然后粘贴来完成作业！

下面对 6 道题目逐一讲解。为了避免路径不可见的问题，本文在每题讲解结束后都直接内嵌了完整的参考实现代码（可直接复制编译）。讲解中我们会把关键代码片段逐段说明，重复的通用部分（比如头文件、常见约定）会在下面统一说明一次。

---

常见头文件与约定（统一说明）

• #include <iostream>：标准输入输出（cin / cout / endl）。
• #include <string>：字符串类型 std::string。
• #include <vector>、#include <map>、#include <set>、#include <queue>、#include <stack>：常用 STL 容器，分别用于动态数组、关联映射、有序集合、队列和栈。
• #include <algorithm>：常用算法（排序、去重等）。
• using namespace std;：方便书写标准库符号（示例代码里普遍使用）。
• #define int long long：在这些参考实现中经常用来把 int 替换为 64 位整数以防止溢出；这是一个快捷写法，但在较大工程中不推荐滥用，优先明确使用 long long。
• signed的意思是"带符号的"，大多数情况下，signed 、 signed int 、 int 三者等价

#define A B 的意思是：在这个代码里，凡是出现 A 的地方，编译之前全部帮我偷偷换成 B。

所以，当你写了： #define int long long

编译器在处理你的代码时，会发生下面的变化：

• 你写的 int a; 变成了 long long a;（这是你的目的，为了防止数据溢出）。
• 你写的 vector<int> v; 变成了 vector<long long> v;。
• 但是！ 你写的 int main() 也会变成 long long main()。 由于C++要求main函数的返回值只能是int，而且我们直接把int的含义改成了long long，所以这里我们只好写signed main()，用一个和int意义相同但是名字不同的signed

以上头文件只讲解一次，后续涉及到的代码段会直接引用这些类型和容器，讲解重点放在逻辑与控制流程上。

---

题目 1：约瑟夫环（Josephus Problem）

相关知识：queue

1. 核心逻辑：先来后到 (FIFO)

queue 遵循的最基本原则是 FIFO (First In, First Out)，即先进先出。

想象你在超市排队结账：

• 第一个排队的人，第一个结账离开。
• 新来的人只能排在队尾。
• 你不能插队，也不能从中间离开。

---

2. 核心操作（只有这四招）

在 C++ 中，操作一个 queue 主要就这四个函数：

动作	C++ 函数名	形象理解
入队	push()	新人来到队尾排队。
查看队首	front()	看看现在轮到谁结账了（但他还没走）。
出队	pop()	队首的人结完账，离开了。
判空	empty()	看看队伍里还有没有人。

---

题目要点

n 个人围成一圈，从 1 开始报数，报到 m 的人出局，重复直到只剩一人，输出该人的编号。

思路与代码讲解（逐段）

• 头文件：

#include <iostream>
#include <queue>

• 初始化与读入：

queue<int> q;
int n, m;
cin >> n >> m;

说明：使用 queue<int> 来模拟环上的顺序，读入 n, m。queue 支持 push/pop/front，很方便实现“从头拿出并放回”的操作。

• 建立初始队列（编号 1..n）：

for (int i = 1; i <= n; ++i) {
    q.push(i);
}

说明：把编号按顺序入队，队列的顺序即为报数顺序，出局时直接 pop() 即可。

• 主循环：按 m 进行“旋转 + 出局”操作：

while (q.size() > 1) {
    for (int i = 1; i < m; ++i) {
        int x = q.front();
        q.pop();
        q.push(x);
    }
    q.pop();
}

• 输出：

cout << q.front() << "\n";

说明：内层循环把前 m-1 个人从队首移到队尾，队首变为第 m 人，直接 pop() 出局。直到队中只剩 1 个元素，输出队首即可。

参考实现

#include <iostream>
#include <queue>

#define int long long

using namespace std;

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	queue<int> q;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		q.push(i);
	}
	while (q.size() > 1) {
		for (int i = 1; i < m; ++i) {
			int x = q.front();
			q.pop();
			q.push(x);
		}
		q.pop();
	}
	cout << q.front() << "\n";
	return 0;
}

---

题目 2：颜色计数（按出现顺序统计）

核心知识：map

1. 核心逻辑：键值对 (Key-Value Pair)

在普通的数组（Array）或向量（Vector）里，你是通过数字下标（0, 1, 2...）来找东西的。 而在 map 里，你可以用任何你喜欢的东西来找东西。

map 的每一条数据都由两部分组成：

• 键 (Key)：相当于“名字”或“单词”，必须是唯一的。
• 值 (Value)：相当于“电话号码”或“解释”，是与键对应的内容。

---

2. 核心操作

使用 map 需要包含头文件 #include <map>。

动作	代码写法	形象理解
插入/更新	m["张三"] = 138...	在通讯录里新建一个联系人或修改号码。
查找	m["张三"]	翻开通讯录，看张三的号码是多少。
擦除	m.erase("张三")	删掉这个联系人。
大小	m.size()	看看通讯录里一共存了多少人。

---

⚠️ 重点注意：

• 中括号 [ ] 的副作用

在 map 中，如果你尝试用 [] 去访问一个根本不存在的键，比如：

std::cout << ageMap["不存在的人"];

map 会非常“热心”地帮你把这个键新建出来，并给它一个默认值（比如 0）。 建议：如果你只是想查询而不希望乱改 map，先用 .count() 检查一下，或者使用 .find()。

---

题目要点

对每组样例读取 n 个由小写字母组成的颜色字符串，统计每种颜色出现次数，并按颜色第一次出现的先后顺序输出。

思路与代码讲解（逐段）

• 头文件：

#include <iostream>
#include <map>
#include <string>
#include <vector>

• 大循环：

int N; cin >> N;
for (int I = 0; I < N; ++I) {
	//......
}

• 初始化、每组数据的输入输出：

map<string, int> m;
vector<string> order;
m.clear();
order.clear();

int n;
cin >> n;

说明：这里使用 map<string,int> 存储计数，vector<string> order 记录颜色第一次出现的顺序。可以用 unordered_map 提高常数性能，但 map 已能满足题目要求。

• 主循环与计数逻辑：

for (int i = 0; i < n; ++i) {
	string s; cin >> s;
	if (m.count(s) == 0) {
		m[s] = 1;
		order.push_back(s);
	} else {
		m[s]++;
	}
}

说明：读到新颜色时在 order 中记录，这样最后按 order 输出时可以保持原始出现次序。

• 输出：

for (const auto& s : order) {
	cout << s << " " << m[s] << "\n";
}

参考实现（可复制运行）

#include <iostream>
#include <map>
#include <string>
#include <vector>

#define int long long

using namespace std;

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int N;
	cin >> N;
	for (int I = 0; I < N; ++I) {
		map<string, int> m;
		vector<string> order;
		m.clear();
		order.clear();
		int n;
		cin >> n;
		for (int i = 0; i < n; ++i) {
			string s;
			cin >> s;
			if (m.count(s) == 0) {
				m[s] = 1;
				order.push_back(s);
			} else {
				m[s]++;
			}
		}
		for (const auto& s : order) {
			cout << s << " " << m[s] << "\n";
		}
	}
	return 0;
}

---

题目 3：去重并排序

核心知识：set

1. 核心逻辑：去重与排序

想象你正在收集球星卡：

• 去重：如果你已经有一张“梅西”了，再拿到一张同样的，你不会把它放进珍藏册，因为册子里只需要一个梅西。
• 排序：当你把卡片放进 set 时，它会自动按顺序（比如从小到大）帮你摆好。

---

2. 核心操作

使用 set 需要包含头文件 #include <set>。

动作	代码写法	形象理解
插入	s.insert(10)	往集合里丢一个数。如果已经有了，它就进不去。
查找	s.count(10)	检查集合里有没有 10（有返回 1，没返回 0）。
删除	s.erase(10)	把 10 从集合里踢出去。
清空	s.clear()	把集合全部清空。

---

题目要点

给定 N 个整数（范围 1..1000），去重后按升序输出不相同的数字及其个数。

思路与代码讲解（逐段）

• 头文件：

#include <algorithm>
#include <iostream>
#include <set>

• 关键容器：

set<int> s;

• 主要流程（输入）：

int n; cin >> n;
for (int i = 0; i < n; ++i) {
	int temp;
	cin >> temp;
	s.insert(temp);//插入的同时，set自动完成去重与排序
}

• 输出：

cout << s.size() << "\n";
for (auto x : s) cout << x << " ";

set<int> 自动去重并维持有序集合，代码简洁直观。

参考实现（可复制运行）

#include <algorithm>
#include <iostream>
#include <set>

#define int long long

using namespace std;

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int temp;
	set<int> s;
	for (int i = 0; i < n; ++i) {
		cin >> temp;
		s.insert(temp);
	}
	cout << s.size() << "\n";
	for (auto x : s) {
		cout << x << " ";
	}
	return 0;
}

---

题目 4：合并果堆（最小体力）

相关知识：priority_queue

1. 核心逻辑：权重最高者先出

在一个优先队列里，元素会被自动排序：

• 默认情况下：数值最大的元素排在最前面（大顶堆）。
• 特殊设置下：数值最小的元素排在最前面（小顶堆）。

---

2. 核心操作

使用它需要包含头文件 #include <queue>（没错，和普通队列同一个头文件）。

动作	代码写法	形象理解
入队	pq.push(x)	把一个元素丢进队列，它会自动找准自己的位置。
看最优先	pq.top()	注意！这里是用 top 而不是 front。
出队	pq.pop()	让优先级最高的那个人离开。

---

3. 小顶堆的实现

这是大顶堆的代码： priority_queue<int> pq;

这是小顶堆的代码： priority_queue<int, vector<int>, greater<int>> pq;

我们把它拆成三部分来看：

1. int：告诉它里面装的是整数。
2. vector<int>：这是“底层容器”。优先队列需要一个地方来存数据，默认就是 vector。这一项通常是固定的。
3. greater<int>：这是灵魂！ * 如果不写这一项，默认是 less<int>，即“大的优先”（大顶堆）。
   • 写了 greater<int>，就变成了“小的优先”（小顶堆）。

为什么多了第2部分：vector<int>？ C++里，priority_queue里存在着这样两个定义：

1. priority_queue< T > ，直接创建一个类型为T的优先队列
2. priority_queue< A , B , C > ，创建一个数据类型为A、底层实现为B、规则为C的优先队列

其实，我们并不需要B，但是编译器规定只能写priority_queue< A , B , C > ，并没有priority_queue< A , C > 这种定义

所以我们为了用规则C来实现小顶堆，就必须用priority_queue< A , B , C >，而B就需要填vector<int>

---

题目要点

给定若干堆果子，每次合并两堆消耗等于两堆之和，求使总消耗最小的合并顺序的最小代价。

思路与代码讲解（逐段）

• 头文件：

#include <iostream>
#include <queue>
#include <vector>

• 输入部分（使用小顶堆为下面自动处理做准备）：

int n; cin >> n;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; ++i) { 
	int weight; 
	cin >> weight; 
	pq.push(weight); 
}

• 关键步骤：借助小顶堆来每次取最小的两堆合并

long long ans = 0;
while (pq.size() > 1) {
	int a = pq.top(); pq.pop();
	int b = pq.top(); pq.pop();
	ans += (long long)a + b;
	pq.push(a + b);
}
cout << ans << endl;

说明：每次合并最小的两堆能使得后续合并的权重也尽可能小，贪心正确。

参考实现（可复制运行）

#include <iostream>
#include <queue>
#include <vector>

#define int long long

using namespace std;

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;

	priority_queue<int, vector<int>, greater<int>> pq;

	for (int i = 0; i < n; ++i) {
		int weight;
		cin >> weight;
		pq.push(weight);
	}

	long long ans = 0;

	while (pq.size() > 1) {
		int first = pq.top();
		pq.pop();
		int second = pq.top();
		pq.pop();
		int combined = first + second;
		ans += combined;
		pq.push(combined);
	}

	cout << ans << endl;

	return 0;
}

---

题目 5：平衡括号序列判断

关键知识：stack

1. 核心逻辑：后进先出 (LIFO)

stack 遵循的最基本原则是 LIFO (Last In, First Out)，即后进先出。

想象你在洗碗，洗好的碗一个接一个叠在一起：

• 你最后放上去的那个碗，一定是在最上面的。
• 当你要用碗时，你拿走的也是最上面那个（也就是最后放进去的那个）。
• 除非你把上面的碗都拿走，否则你拿不到最底下的碗。

---

2. 核心操作

使用 stack 需要包含头文件 #include <stack>。

动作	C++ 函数名	形象理解
压栈	push()	往碗堆最上面放一个新碗。
查看栈顶	top()	看看最上面的碗是什么样子的。
弹栈	pop()	把最上面的那个碗拿走。
判空	empty()	看看还有没有碗可以拿。

---

题目要点

给定只包含括号的字符串，判断是否为平衡括号序列（例如 ()[]、([]) 是平衡的）。

思路与代码讲解（逐段）

• 头文件：

#include <iostream>
#include <stack>
#include <string>

• 变量声明、输入：

string s;
cin >> s;
stack<char> st;

• 关键容器：stack<char> 用来保存未匹配的左括号：

for (auto c : s) {
	if (c == '(' || c == '[' || c == '{') {
		st.push(c);
	} else {
		if (st.empty()) { 
			cout << "No\n"; 
			return 0; 
		}
		char top = st.top(); st.pop();
		if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
			cout << "No\n"; 
			return 0;
		}
	}
}
cout << (st.empty() ? "Yes" : "No");   // 注意只有最后栈为空时才证明完美匹配
									   // 若栈不为空则说明还有左括号：( [ { 尚未匹配

说明：每遇到右括号就检查栈顶是否为对应左括号，否则立即返回 No；遍历结束栈为空则 Yes。

参考实现（可复制运行）

#include <iostream>
#include <stack>
#include <string>

#define int long long

using namespace std;

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	int l = s.length();
	stack<char> st;
	for (auto c : s) {
		if (c == ('(') || c == ('[') || c == ('{')) {
			st.push(c);
		} else {
			if (st.empty()) {
				cout << "No\n";
				return 0;
			}
			char top = st.top();
			st.pop();
			if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
				cout << "No\n";
				return 0;
			}
		}
	}
	if (st.empty()) {
		cout << "Yes";
	} else {
		cout << "No";
	}
	return 0;
}

---

题目 6：序列展开协议（p1,p2,p3 参数控制）

感觉此题对STL的学习意义不大，大家当作一道思维难度不大但要求多的题随便做做就好

题目要点

根据 p1,p2,p3 对压缩串中形如 a-c 或 3-7 的片段做展开（填充不同形式、重复次数、顺序控制），并处理若干异常情况（相邻直接删除 -、类型不一致或稳态保留 - 等）。

思路与代码讲解（逐段）

• 程序先读三个参数并读入字符串，然后从左到右逐字符处理：当遇到 - 时，根据其左右字符类型（字母或数字）和 ASCII 比较决定是否执行展开或直接输出 -。

核心循环片段说明（节选并讲解逻辑分支）：

int p1, p2, p3; cin >> p1 >> p2 >> p3;
string s; cin >> s;
cout << s[0];
for (int i = 1; i < (int)s.length(); i++) {
	if (s[i] == '-') {
		// 当且仅当两侧同为小写字母或同为数字且右侧字符大于左侧，才尝试展开
		if (s[i - 1] >= 'a' && s[i - 1] <= 'z' && s[i + 1] >= 'a' && s[i + 1] <= 'z' && s[i - 1] < s[i + 1]) {
			// 根据 p1 决定填充：小写 / 大写 / 星号；p2 决定重复次数；p3 决定升序或降序输出
		}
		else if (s[i - 1] >= '0' && s[i - 1] <= '9' && s[i + 1] >= '0' && s[i + 1] <= '9' && s[i - 1] < s[i + 1]) {
			// 数字区间处理（p1 对数字无影响）
		} else {
			cout << '-'; // 非法或稳态情况原样输出 '-'
		}
	} else {
		cout << s[i];
	}
}

说明：实现细节包括字符到字符之间按 ASCII 遍历并根据 p1/p2/p3 输出不同内容，代码分支较多但逻辑清晰。注意在严格部署到不可信输入时要保证对 s[i+1] 的访问不越界（题目数据通常保证 - 不在首尾）。

参考实现（可复制运行）

#include <iostream>
#include <stack>
#include <string>

#define int long long

using namespace std;

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int p1, p2, p3;
	cin >> p1 >> p2 >> p3;
	string s;
	cin >> s;
	int l = s.length();
	cout << s[0];
	for (int i = 1; i < l; i++) {
		if (s[i] == '-') {
			if (s[i - 1] >= 'a' && s[i - 1] <= 'z' && s[i + 1] >= 'a' && s[i + 1] <= 'z' && s[i - 1] < s[i + 1]) {
				if (p1 == 1) {
					if (p3 == 1) {
						for (char c = s[i - 1] + 1; c < s[i + 1]; ++c) {
							for (int j = 0; j < p2; ++j) {
								cout << c;
							}
						}
					} else {
						for (char c = s[i + 1] - 1; c > s[i - 1]; --c) {
							for (int j = 0; j < p2; ++j) {
								cout << c;
							}
						}
					}
				} else if (p1 == 2) {
					if (p3 == 1) {
						for (char c = s[i - 1] + 1; c < s[i + 1]; ++c) {
							for (int j = 0; j < p2; ++j) {
								cout << (char)(c - 'a' + 'A');
							}
						}
					} else {
						for (char c = s[i + 1] - 1; c > s[i - 1]; --c) {
							for (int j = 0; j < p2; ++j) {
								cout << (char)(c - 'a' + 'A');
							}
						}
					}
				} else if (p1 == 3) {
					for (char c = s[i - 1] + 1; c < s[i + 1]; ++c) {
						for (int j = 0; j < p2; ++j) {
							cout << '*';
						}
					}
				}
			} else if (s[i - 1] >= '0' && s[i - 1] <= '9' && s[i + 1] >= '0' && s[i + 1] <= '9' &&
					   s[i - 1] < s[i + 1]) {
				if (p1 == 3) {
					for (char c = s[i - 1] + 1; c < s[i + 1]; ++c) {
						for (int j = 0; j < p2; ++j) {
							cout << '*';
						}
					}
				} else {
					if (p3 == 1) {
						for (char c = s[i - 1] + 1; c < s[i + 1]; ++c) {
							for (int j = 0; j < p2; ++j) {
								cout << c;
							}
						}
					} else {
						for (char c = s[i + 1] - 1; c > s[i - 1]; --c) {
							for (int j = 0; j < p2; ++j) {
								cout << c;
							}
						}
					}
				}

			} else {
				cout << '-';
			}
		} else {
			cout << s[i];
		}
	}
	return 0;
}

---

统一注意事项与调试建议（精简）

• 统一约定：参考实现中使用 #define int long long 是为了简单防止整型溢出；理解其副作用并酌情使用，推荐在真实项目中显式使用 long long。
• 建议养成习惯：写小样例并手动跟踪变量变化（尤其涉及下标、栈、队列操作时），遇到 WA 时先打印关键状态（例如队列长度、栈顶、当前索引）快速定位。

结语

STL是C++里比较重要的内容，学会了STL后再写代码会方便很多。

后期我们程序设计课也会有所涉及

这部分新的语法可能比较多，但希望大家一定要尽力理解