程序设计实习报告
程序设计实习报告 桂林理工大学 GUILIN UNIVERSITY OF TECHNOLOGY
程序设计实践课程
实习报告
学 院： 计算机科学与工程学院 #
班 级： ##
组 长：
组 员：
组 员：
组 员：
指导教师：
评 分/价：
1.基础实践部分
1.1. 编写程序，求n！ 1.1.1题目内容 编写程序，求n！(n的值要能大于13)，其结果用一个不超过64位的十进制数输出。
1.1.2题目要求 【输入格式】 输入一个非负整数，其值介于2到49之间的数。 【输出格式】 对每一个输入的整数，在一行中输出相应的阶乘值，输出结果的高位用0填充。 【输入样例】 在这里给出一组输入。例如： 7 结尾无空行 【输出样例】 5040
1.1.3设计思想 deepseek_mermaid_20260108_2d339a.png
1.1.4算法分析
时间复杂度：O(n² log n)
空间复杂度：O(n log n)
1.1.5核心代码
// 编写程序,求n!
#include
string calculate(int n) { if (n == 0 || n == 1) { return “1”; }
vector<int> result;
result.push_back(1);
for (int i = 2; i <= n; i++) {
int carry = 0;
// 将每个结果乘以i
for (int j = 0; j < result.size(); j++) {
int product = result[j] * i + carry;
result[j] = product % 10;
carry = product /= 10;
}
// 处理剩余进位
while (carry > 0) {
result.push_back(carry % 10);
carry /= 10;
}
}
// 高位填充0
for (int i = 0 ; i < 64 - result.size(); i++) {
result.push_back(0);
}
// 转换为0
string res;
reverse(result.begin(),result.end());
for (int i = 0; i < result.size(); i++) {
res += to_string(result[i]);
}
return res;
}
int main() { int n; cin » n;
string result = calculate(n);
cout << result << endl;
}
1.1.6测试数据或截图 image.png
1.1.7心得体会 在本次程序设计实习中，我通过实现大数阶乘计算，深入理解了数组模拟高精度运算的原理和实现细节，锻炼了问题分解和逻辑思维能力。
1.2 找最大数和最小数 1.2.1题目内容 本题目要求读入n个整数，找到最大数和最小数，并输出结果。
1.2.2题目要求 【输入格式】 例如当n=4时，输入给出4个绝对值不超过1000的整数A、B、C、D，以空格分隔。 【输出格式】 最大数和最小数，“max=?,min=?”。 【输入样例】 在这里给出一组输入。例如： 18 98 59 25 【输出样例】 在这里给出相应的输出。例如： max=98, min=18
1.2.3设计思想
deepseek_mermaid_20260108_33f2cf.png
1.2.4算法分析 时间复杂度：O(n) 空间复杂度：O(n)
1.2.5核心代码
// 找最大数和最小数
#include
int main() {
int n;
cin » n;
vector
cout << "max_num=" << max_num << "min_num=" << min_num;
}
1.2.6测试数据或截图 image.png
1.2.7心得体会 初次编写查找最值程序时，我意识到在循环中同时更新最大最小值能有效减少遍历次数，对时间复杂度有了更直观的理解，也学会了注意数组边界等细节
1.3 统计字母出现频率 1.3.1题目内容 输入一段文字（以回车结束），统计其中每个字母出现的频率。
1.3.2题目要求 【输入格式】 一段文字（以回车结束） 【输出格式】 统计结果（包括次数和百分比，并显示条状图，参见输出样例） 【输入样例】 This is a pen. That is a pencil. 【输出样例】 A: 3 13.0% ************* C: 1 4.3% **** E: 2 8.7% ********* H: 2 8.7% ********* I: 4 17.4% ***************** L: 1 4.3% **** N: 2 8.7% ********* P: 2 8.7% ********* S: 3 13.0% ************* T: 3 13.0% *************
1.3.3设计思想 deepseek_mermaid_20260108_bb824e.png
1.3.4算法分析 时间复杂度：O(n) 空间复杂度：O(1)
1.3.5核心代码
// 统计字母出现频率
#include
int main() {
string str_input;
cin » str_input;
vector
// 输出百分比
double temp = (cnt[i] * 100) / (double)total;
// 限制小数点两位
cout << fixed << setprecision(2) << temp << "%";
// 输出条状图
int each = (cnt[i] * 100) / total ;
if ((cnt[i] * 100) / total > 0) {
each += 1;
}
for (int i = 0; i < each; i++) {
cout << "*";
}
cout << endl;
}
}
1.3.6测试数据或截图 image.png
1.3.7心得体会 通过这次字母频率统计程序的编写，我学会了如何将抽象的数据统计需求转化为具体代码逻辑，掌握了数组映射和格式化输出的技巧，意识到程序不仅要关注正确性，输出格式的可读性也同样重要。
1.4最小公倍数 1.4.1题目内容 请编写程序，输入两个整数，计算并输出它们的输出最小公倍数。
1.4.2题目要求 【输入格式】 两个整数 【输出格式】 最小公倍数(正整数) 说明：两个整数可以是正数、零和负数。最小公倍数必须是自然数。题目保证两个整数及其最小公倍数的绝对值都小于2(63) 。 【输入样例】 935761 -5128800173759 【输出样例】 4799331179396895599
1.4.3设计思想 deepseek_mermaid_20260108_05f056.png
1.4.4算法分析 时间复杂度：O(log(min(a, b))) 空间复杂度：O(1)
1.4.5核心代码
// 最小公倍数
// 辗转相除法:
// lcm: 最小公倍数 gcd: 最大公约数
// LCM(a, b) = |a × b| ÷ GCD(a, b)
#include
// 求解最大公约数 long long gcd(long long a, long long b) { // 反复用余数替换原数相除，直至整除，最后的除数即为最大公约数。 while(b != 0) { long long temp = b; b = a % b; a = temp; } return a; }
// 求解最小公约数 long long lcm(long long a, long long b) { // 防止溢出: 先除最大公约数再乘 return a / gcd(a, b) * b; }
int main() { long long num1,num2; cin » num1 » num2; long long gcd_num = gcd(num1,num2); long long lcm_num = lcm(num1,num2); cout « lcm_num « endl; }
1.4.6测试数据或截图 image.png
1.4.7心得体会 通过这个程序，我明白了数学算法在编程中的重要性。辗转相除法求最大公因数的方法简洁高效，而最小公倍数与最大公因数的数学关系让我领略到算法设计的巧妙。同时，先除后乘的顺序处理让我注意到整数溢出的预防，这些都是很实用的编程经验。
1.5学车费用 1.5.1题目内容 小华学开车后，才发现他的教练对不同的学员收取不同的费用。小华想分别对他所了解到的学车同学的各项费用进行累加求出总费用，然后按下面的排序规则排序并输出，以便了解教练的收费情况。排序规则： 先按总费用从多到少排序，若总费用相同则按姓名的ASCII码序从小到大排序，若总费用相同而且姓名也相同则按编号（即输入时的顺序号，从1开始编）从小到大排序。
1.5.2题目要求 【输入格式】 测试数据有多组，处理到文件尾。每组测试数据先输入一个正整数n（n≤20），然后是n行输入，第i行先输入第i个人的姓名（长度不超过10个字符，且只包含大小写英文字母），然后再输入若干个整数（不超过10个），表示第i个人的各项费用，数据之间都以一个空格分隔，第i行输入的编号为i。输入数据和结果均在32位int型范围之内。 【输出格式】 对于每组测试，在按描述中要求的排序规则进行排序后，按顺序逐行输出每个人费用情况，包括：费用排名（从1开始，费用相同则排名也相同）、编号、姓名、总费用。每行输出的数据之间留1个空格。 【输入样例】 3 Tim 2800 900 2000 500 600 Lucy 3800 400 1500 300 Tim 6700 100
【输出样例】 1 1 Tim 6800 1 3 Tim 6800 3 2 Lucy 6000
1.5.3设计思想 deepseek_mermaid_20260108_9eac00.png
1.5.4算法分析 时间复杂度接近O(n × m) 空间复杂度高：O(n × m)
1.5.5核心代码
// 学车费用 // 排序规则： 先按总费用从多到少排序，若总费用相同则按姓名的ASCII码序从小到大排序， // 若总费用相同而且姓名也相同则按编号（即输入时的顺序号，从1开始编）从小到大排序。
/*
知识点补充:
stringstream 是C++中一个强大的流类,用于字符串的输入输出操作
#include
stringstream 是一个字符串流，它把字符串当作一个连续的字符序列，
并维护一个内部指针来跟踪当前读取位置。
提取运算符 >>：根据目标类型读取数据
*/
#include
class Student {
public:
string m_name;
vector
static bool compare(Student stu1, Student stu2) { // 如果费用相等,按照姓名排序 if (stu1.m_total == stu2.m_total) { // 如果姓名也相同,按照输入顺序排序 if (stu1.m_name == stu2.m_name) { return stu1.m_id < stu2.m_id; } return stu1.m_name < stu2.m_name; } else { // 费用由多到少排序 return stu1.m_total > stu2.m_total; } }
int main() { int n; cin » n; cin.ignore(); // 忽略第一行后面的换行符
// 读取并且创建学生类
vector<Student> students(n);
for (int i = 0; i < n; i++) {
string line;
getline(cin, line); // 读取整行
stringstream ss(line);
// 读取id
students[i].m_id = i + 1;
// 读取姓名
string name;
ss >> name;
students[i].m_name = name;
// 读取各个费用
// 这里读取到回车就终止
int price;
while(ss >> price) {
students[i].m_prices.push_back(price);
}
// 计算费用总和
int total = 0;
for (int j = 0; j < students[i].m_prices.size(); j++) {
total += students[i].m_prices[j];
}
students[i].m_total = total;
}
sort(students.begin(),students.end(),compare);
for (int j = 0; j < students.size(); j++) {
// 输出排名
cout << j+1 << " ";
// 输出姓名
cout << students[j].m_name << " ";
// 输出总费用
cout << students[j].m_total << endl;
}
}
1.5.6测试数据或截图 image.png
1.5.7心得体会 通过编写学车费用统计排序程序，我掌握了多条件自定义排序的设计方法。学会了使用stringstream处理混合数据类型的输入，理解了类设计在组织复杂数据时的优势。最重要的是，意识到程序不仅要实现功能，还要考虑数据的完整性和排序的精确性。
1.6求n个整数的平均值与中位数 1.6.1题目内容 从键盘接收一个整数n，假定用户输入的n一定是满足3 <= n <= 100。接下来，从键盘接收n个整数存入数组。用户输入的整数，大小是杂乱无序的。 计算这n个数的平均值和中位数。中位数就是数组元素升序排列后，最中间的一个数(奇数个元素)，或中间两个元素平均值(偶数个元素)。
1.6.2题目要求 【输入格式】 第一个整数4告诉计算机要输入4个数字。第二行输入这四个数字，数字之间用空格分开。 4 3 1 2 9 【输出格式】 平均值保留2位小数，中位数保留1位小数。两项信息之间用纯英文逗号隔开，整个输出信息中不含空格。 mean=3.75, median=2.5
1.6.3设计思想 deepseek_mermaid_20260108_a9e34f.png
deepseek_mermaid_20260108_43a706.png
1.6.4算法分析 需要存储n个整数的数组：O(n) 其他变量占用常数空间：O(1)
1.6.5核心代码
// 求n个整数的平均值与中位数
#include
int main() {
int n;
cin » n;
vector
double avg = (double)total / (double)n;
cout << "mean=" << avg << "median=" << mid_num << endl;
}
1.6.6测试数据或截图 image.png
1.6.7心得体会 通过编写这个求平均值和中位数的程序，我掌握了数据统计的基本方法。排序函数的使用让我明白了预处理数据的重要性，同时也注意到整数除法和浮点数除法的区别。程序虽然简单，但让我对数组操作和条件判断有了更深的理解。
1.7天才婴儿 1.7.1题目内容 育婴室里有从1到n编号的n个婴儿。有一天，有一个科研团队来到育婴室，科研团队认为某个婴儿的编号的值减去这个编号每一位数字的和代表一个婴儿的智商，他们同时有个智商衡量标准k，若某个婴儿的智商不小于k，那么科研团队就认为这个婴儿是天才。例如，编号为12的婴儿，他的智商应为12−(1+2)，即为9。科研团队想请你求出育婴室里有多少天才婴儿。
1.7.2题目要求 【输入格式】 输入包含两个整数n,k，分别表示婴儿的个数和科研团队的智商衡量标准。 【输出格式】 输出一个整数，表示育婴室里天才婴儿的数量。 【输入样例】 23 8 【输出格式】 14 【评测数据规模】 对于所有评测数据，1≤n，k≤10(9)。
1.7.3设计思想 deepseek_mermaid_20260108_39a1da.png
1.7.4算法分析 空间复杂度：O(1)（常数空间） 时间复杂度：O(n log n) 或更精确地说 O(n × d)，其中 d 是 n 的位数
1.7.5核心代码
// 天才婴儿
#include
int main() {
int n,k;
cin » n » k;
int cnt = 0;
for (int i = 1; i <= n; i++) {
int num = i;
int temp = 0;
while(num > 0) {
temp += num%10;
num /= 10;
}
int k0 = i - temp;
if (k0 > k) {
cnt++;
}
}
cout « cnt;
}
1.7.6测试数据或截图 image.png
1.7.7心得体会 通过这个数字特性统计程序，我掌握了数字分离求和的技巧。在遍历1到n的过程中，不仅学会了用取余和整除逐位提取数字，也加深了对条件判断的理解。虽然题目简单，但让我意识到细心处理边界情况的重要性。
1.8金币支付 1.8.1题目内容 小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。输入数据仅一行，包含两个正整数a和b，它们之间用一个空格隔开，表示小凯手中金币的面值。其中，1≤a，b≤109
1.8.2题目要求 【输入格式】 输出仅一行，一个正整数N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。 【输入样例】 3 7 【输出样例】 11
1.8.3设计思想 deepseek_mermaid_20260108_e5415c.png
1.8.5核心代码
// 金币支付 -> 用a和b的线性组合不能被表示的最大整数
// 由于a和b互质,
// 任何大于等于(a-1)(b-1)的整数都可以表示为a和b的非负整数线性组合
// 而ab - a - b正好等于(a-1)*(b-1) - 1,无法被表示,且是最大的这样的数
// 两个互质数，不能凑出的最大数 = 两数乘积减去两数之和
#include
int main() { int a,b; cin » a » b;
cout << a*b - a - b;
}
1.8.6测试数据或截图 image.png
1.8.7心得体会 通过这道题，我深刻体会到数学思维在编程中的重要性。看似复杂的线性组合问题，运用互质数的性质只需一个简洁公式就能解决，这让我认识到算法优化往往源于对问题本质的深入理解。
1.9鱼 1.9.1题目内容 在平面坐标系上给定 n 个不同的整点（也即横坐标与纵坐标皆为整数的点）。我们称从这 n 个点中选择 6 个不同的点所组成的有序六元组 <A,B,C,D,E,F> 是一条「鱼」，当且仅当：AB=AC,BD=CD,DE=DF（身形要对称），并且 ∠BAD,∠BDA 与 ∠CAD,∠CDA 都是锐角（脑袋和屁股显然不能是凹的），∠ADE,∠ADF 大于 90°（也即为钝角或平角，为了使尾巴不至于翘那么别扭）。 image.png
其中点的组成相同，但顺序不同的鱼视为不同的鱼，即 <A,B,C,D,E,F> 和 <A,C,B,D,E,F> 视为不同的两条鱼（毕竟鱼也有背和肚子的两面），同理 <A,B,C,D,E,F> 和 <A,B,C,D,F,E> 也可以视为不同的两条鱼（假设鱼尾巴可以打结）。 问给定的 n 个点可以构成多少条鱼。注意：数据保证 n 个点互不重复。
1.9.2题目要求 【输入格式】 第一行一个正整数 n ，代表平面上点的个数。 接下来 n 行每行两个整数 x,y ，代表点的横纵坐标。 【输出格式】 输出一行一个非负整数，代表鱼的个数。 【输入样例】 8 -2 0 -1 0 0 1 0 -1 1 0 2 0 3 1 3 -1 【输出样例】 16
1.9.3设计思想 deepseek_mermaid_20260108_2376e4.png
1.9.4算法分析 最坏时间复杂度：O(n⁶) 最坏空间复杂度：O(n⁶)（结果存储）
1.9.5核心代码
// 鱼
#include
class Point { public: Point() {} Point(int x,int y) : m_x(x),m_y(y){} int m_x,m_y; };
// 计算两个向量的平方距离 int get_distance_sqrt(Point a, Point b) { int abx = b.m_x - a.m_x; int aby = b.m_y - a.m_y; return abxabx + abyaby; }
int dotProduct(Point A, Point B, Point C) { // 计算向量BA与向量BC的点积 int BAx = A.m_x - B.m_x; int BAy = A.m_x - B.m_x; int BCx = C.m_x - B.m_x; int BCy = C.m_x - B.m_x; return BAx * BCx + BAy * BCy; }
int main() {
int n;
cin » n;
vector
vector<unordered_map<char,Point>> result;
// 暴力查找每一个可以构成鱼的六元组
for (int a = 0; a < n; a++) {
for (int b = 0; b < n; b++) {
if (b == a) {
continue;
}
for (int c = 0; c < n; c++) {
if (c == a || c == b) {
continue;
}
if (get_distance_sqrt(Points[a],Points[b]) != get_distance_sqrt(Points[a],Points[c])) {
continue;
}
for (int d = 0; d < n; d++) {
if (d == a || d == b || d == c){
continue;
}
if (get_distance_sqrt(Points[b],Points[d]) != get_distance_sqrt(Points[c],Points[d])) {
continue;
}
for (int e = 0; e < n; e++) {
if (e == a || e == b || e == c || e == d) {
continue;
}
for (int f = 0; f < n; f++) {
if (f == a || f == b || f == c || f == d || f == e) {
continue;
}
if (get_distance_sqrt(Points[d],Points[e]) != get_distance_sqrt(Points[d],Points[f])) {
continue;
}
// 角BAD,角BDA,角CAD,角CDA都是锐角
// 角ADE,角ADF大于90度
if (dotProduct(Points[b],Points[a],Points[d]) > 0 &&
dotProduct(Points[b],Points[d],Points[a]) > 0 &&
dotProduct(Points[c],Points[a],Points[d]) > 0 &&
dotProduct(Points[c],Points[d],Points[a]) > 0 &&
dotProduct(Points[a],Points[d],Points[e]) < 0 &&
dotProduct(Points[a],Points[d],Points[f]) < 0
) {
// 维护可以构成鱼的六元组
unordered_map<char,Point> umap;
umap.insert(make_pair('A',Points[a]));
umap.insert(make_pair('B',Points[b]));
umap.insert(make_pair('C',Points[c]));
umap.insert(make_pair('D',Points[d]));
umap.insert(make_pair('E',Points[e]));
umap.insert(make_pair('F',Points[f]));
result.push_back(umap);
}
}
}
}
}
}
}
cout << result.size();
}
1.9.6测试数据或截图 image.png
1.9.7心得体会 通过这个复杂的几何形状检测程序，我深刻体会到暴力枚举算法的局限性。六重循环虽然直观但效率低下，这让我意识到必须寻找更优化的算法设计。同时，向量点积计算几何角度的方法让我对数学在图形处理中的应用有了新认识，也学会了如何通过条件剪枝减少不必要的计算。
1.10迷你搜索引擎 1.10.1题目内容 实现一种简单的搜索引擎功能，快速满足多达10 (5)
1.10.2题目要求 【输入格式】 输入首先给出正整数 N（≤ 100），为文件总数。随后按以下格式给出每个文件的内容：第一行给出文件的标题，随后给出不超过 100 行的文件正文，最后在一行中只给出一个字符 #，表示文件结束。每行不超过 50 个字符。在 N 个文件内容结束之后，给出查询总数 M（≤10(5)），随后 M 行，每行给出不超过 10 个英文单词，其间以空格分隔，每个单词不超过 10 个英文字母，不区分大小写。 【输出格式】 针对每一条查询，首先在一行中输出包含全部该查询单词的文件总数；如果总数为 0，则输出 Not Found。如果有找到符合条件的文件，则按输入的先后顺序输出这些文件，格式为：第1行输出文件标题；随后顺序输出包含查询单词的那些行内容。注意不能把相同的一行重复输出。 【输入样例】 4 A00 Gold silver truck
A01 Shipment of gold damaged in a fire
A02 Delivery of silver arrived in a silver truck
A03 Shipment of gold arrived in a truck
2 what ever silver truck 【输出样例】 0 Not Found 2 A00 silver truck A02 of silver a silver truck
1.10.3设计思想 deepseek_mermaid_20260108_e3ba21.png
1.10.4算法分析 时间复杂度：
N: 文件数量 L: 每个文件的平均行数 W: 每行的平均单词数（去重后） C: 每个单词的平均长度 M: 查询数量 Q: 每个查询的平均词数 R: 每个查询的平均结果文件数 P: 每个文件中的平均相关行数
索引构建： O(N×L×W)
查询处理： 平均: O(Q×R + P log P) 最坏: O(Q×N + L log L)
空间复杂度：
索引构建： O(T)
单个查询： O(N+Q+P)
内存使用： O(N×L×C + T)
1.10.5核心代码
// 迷你搜索引擎
#include
class File{
public:
string title;
vector
File() {}
// 逐行添加文件内容
void addLine(const string& line) {
text.push_back(line);
}
// 返回文件总行数
int getLineCount() const {
return text.size();
}
// 获取指定行的内容
string getLine(int lineNum) const {
if (lineNum >= 0 && lineNum < text.size()) {
return text[lineNum];
}
return "";
}
};
// 将大写转换为小写 string toLower(const string& s) { string result = s; transform(result.begin(),result.end(),result.begin(),::tolower); return result; }
// 分割一行文本为单词
vector
int main() { // 读取N个文件文件 int N; cin » N; cin.ignore(); // 忽略换行符
vector<File> Files(N);
// 建立倒排索引
// 索引结果: 单词 -> 文件索引集合
unordered_map<string, unordered_map<int, unordered_set<int>>> invertedIndex;
// 读取每个文件
for (int fileIdx = 0; fileIdx < N; fileIdx++) {
// 读取文件标题
string name;
getline(cin,name);
Files[fileIdx].title = name;
// 读取文件内容
int lineNum = 0; // 当前行号
while(true) {
string line;
getline(cin,line);
if (line == "#") {
break;
}
// 逐行存储文件内容
Files[fileIdx].addLine(line);
// 处理当前行的单词,建立索引
vector<string> words = splitLine(line);
// 去重: 同一行的同一个单词只记录一次
unordered_set<string> uniqueWords(words.begin(), words.end());
// 更新倒排索引
for (const string& word : uniqueWords) {
invertedIndex[word][fileIdx].insert(lineNum);
}
lineNum++;
}
}
// 读取M个查询
int M;
cin >> M;
cin.ignore(); // 忽略换行符
// 处理每个查询
for (int i = 0; i < M; i++) {
string query;
getline(cin, query);
// 分割查询词
vector<string> queryWords = splitLine(query);
if (queryWords.empty()) {
cout << "0\nNot Found\n";
continue;
}
// 1.找到包含所有查询词的文件
unordered_set<int> commonFiles; // 包含所有查询词的文件索引
// 初始化: 用第一个查询词的文件集合
if (invertedIndex.count(queryWords[0])) {
for (const auto& entry : invertedIndex[queryWords[0]]) {
commonFiles.insert(entry.first); // entry.first是文件索引
}
}
// 取交集: 确保文件包含所有查询词
for (size_t i = 1; i < queryWords.size(); i++) {
const string& word = queryWords[i];
if (!invertedIndex.count(word)) {
// 如果某个词在任何文件中都不存在，交集为空
commonFiles.clear();
break;
}
unordered_set<int> currentFiles;
for (const auto& entry : invertedIndex[word]) {
currentFiles.insert(entry.first);
}
// 取交集
unordered_set<int> newCommonFiles;
for (int fileIdx : commonFiles) {
if (currentFiles.count(fileIdx)) {
newCommonFiles.insert(fileIdx);
}
}
commonFiles = newCommonFiles;
}
// 2. 输出符合条件的文件数
cout << commonFiles.size() << endl;
// 如果没有符合条件的文件则输出未找到
if (commonFiles.empty()) {
cout << "Not Found\n";
}
else {
// 如果有符合条件的文件: 按文件输入顺序输出（0到N-1）
for (int fileIdx = 0; fileIdx < N; fileIdx++) {
if (commonFiles.count(fileIdx)) {
// 输出文件标题
cout << Files[fileIdx].title << endl;
//收集相关行号
unordered_set<int> relevantLines;
for (const string& word : queryWords) {
if (invertedIndex.count(word) &&
invertedIndex[word].count(fileIdx)) {
const unordered_set<int>& lines = invertedIndex[word][fileIdx];
relevantLines.insert(lines.begin(), lines.end());
}
}
// 将行号转换为向量并排序（按行号顺序输出）
vector<int> sortedLines(relevantLines.begin(), relevantLines.end());
sort(sortedLines.begin(), sortedLines.end());
// 输出包含查询词的行
for (int lineNum : sortedLines) {
cout << Files[fileIdx].getLine(lineNum) << endl;
}
}
}
}
}
}
1.10.6测试数据或截图 image.png
1.10.7心得体会 通过这次迷你搜索引擎的实现，我掌握了倒排索引这一核心数据结构的设计与应用。从文本预处理、大小写转换到多关键词交集查询，每个环节都锻炼了我的工程能力。更重要的是，我体会到设计一个高效检索系统需要综合考虑数据结构、算法效率和实际应用场景的平衡。
2.进阶实践部分 2.1整数因子分解问题 2.1.1题目内容 大于1的正整数n可以分解为： 转word后抄 例如若n=12，共用8种不同的分解式： 转word后抄 对于给定的正整数n，编程计算n有多少种不同的分解式。
2.1.2题目要求 【输入】：数据有多行，给出正整数n 1 <= n <= 2000000000; 【输出】：每个数据输出一行，是正整数n的不同的分解式数量。 【输入样例】： 12 35 【输入样例】 8 3
2.1.3设计思想 deepseek_mermaid_20260108_5fc30e.png
2.1.4算法分析 时间复杂度：O(n * sqrt(n)) 空间复杂度：O(sqrt(n))
2.1.5核心代码
// #include
// map<int, int> memo; // 记忆化，避免重复计算 // int solve(int num) { // if (num == 1) return 1;
// // 如果已经计算过，直接返回 // if (memo.find(num) != memo.end()) return memo[num];
// int count = 1; // n本身是一种分解
// for (int i = 2; i <= num / 2; i++) { // if (num % i == 0) { // count += solve(i); // } // }
// // 保存结果到记忆化表 // memo[num] = count; // return count; // }
// int main() { // int n; // while(cin » n) { // cout « solve(n) « endl; // } // return 0; // }
// 记忆化搜索
// 终止条件: 当num递归到1时,当num是质数时
// 递推表达式: f(n) = 1 sum(f(n / i))
// 整数因子分解问题
#include
map<int,int> memo; int solve(int num) { if (num == 1) return 1;
if (memo.find(num) != memo.end()) return memo[num];
int count = 1;
for (int i = 2; i <= num / 2; i++) {
if (num % i == 0) {
count += solve(num / i);
}
}
memo[num] = count;
return count;
}
int main() { int n; while(cin » n) { cout « solve(n) « endl; } }
2.1.6测试数据或截图 image.png
2.1.7心得体会 通过这次整数因子分解问题的实现，我深刻理解了记忆化搜索在递归算法中的重要作用。将大问题分解为子问题并存储中间结果，不仅大幅提升了效率，还让我对动态规划和递归的关系有了更直观的认识。
2.2选择问题 2.2.1题目内容 给定的n个元素数组a[0: n-1]，要求找出第k小的元素。
2.2.2题目要求
【输入】：数据有多行，给出正整数n
转word后抄
【输出】：每个数据输出一行，是正整数n的不同的分解式数量。
【输入样例】：
12
35
【输入样例】
8
3
2.2.3设计思想 deepseek_mermaid_20260108_2d5195 (1).png
2.2.4算法分析 时间复杂度：O(n log n) 空间复杂度：O(n)
2.2.5核心代码
#include
// (2) 选择问题 给定的n个元素数组a[0: n-1]，要求找出第k小的元素。
int main() {
// 只能按住ctrk + c等退出
int n = 0,k = 0;
while(cin » n » k) {
set
vector<int> nums;
for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
nums.push_back(*it);
}
// sort(nums.begin(),nums.end()); set已经是有序了不需要排序
cout << nums[k -1] << endl;
}
}
2.2.6测试数据或截图 image.png
2.2.7心得体会 使用set自动去重排序，注意原数组可能有重复元素，需根据题意判断是否允许去重。
2.3凑零钱 2.3.1题目内容 凑零钱 韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有 10 (4) 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。
2.3.2题目要求 【输入格式】 输入第一行给出两个正整数：N（≤10(4) ）是硬币的总个数，M（≤10(2) ）是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。 【输出格式】 在一行中输出硬币的面值 V(1)≤V(2) ≤⋯≤V(k) ，满足条件 V(1) +V(2) +…+V(k) =M。数字间以 1 个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出 No Solution。 注：我们说序列{ A[1],A[2],⋯ }比{ B[1],B[2],⋯ }“小”，是指存在 k≥1 使得 A[i]=B[i] 对所有 i<k 成立，并且 A[k]<B[k]。
2.3.3设计思想 deepseek_mermaid_20260108_453da0.png
2.3.4算法分析 时间复杂度：O(N log N + NM) 空间复杂度：O(NM)
2.3.5核心代码
// 动态规划
#include
int main() {
int N,M; // N枚硬币总数,M付款金额
cin » N » M;
vector
sort(coins.begin(),coins.end()); // 从小到大排序
// dp[i][j] 表示第i+1个物品在背包为j的空格下的最大价值
vector<vector<int> > dp(N,vector<int>(M + 1)); // 老编译器版本
int bagweight = M;
// 路径记录
vector<vector<bool> > choice(N,vector<bool>(M + 1,false));
// 初始化
for (int i = 0; i <= bagweight; i++) {
if (i >= coins[0]) {
dp[0][i] = coins[0];
choice[0][i] = true; // 选择第一个硬币
}
}
// 动态规划方程
// 先遍历物品,再遍历背包重量
for (int i = 1; i < N; i++) {
for (int j = 0; j <= bagweight; j++) {
// cout << "debug: " << dp[i][j] << endl;
if (j >= coins[i] && coins[i] + dp[i-1][j - coins[i]] > dp[i-1][j]) {
dp[i][j] = coins[i] + dp[i-1][j - coins[i]];
choice[i][j] = true; // 选择了第i个硬币
}
else {
// cout << "debug: 大小不够" << endl;
dp[i][j] = dp[i-1][j];
}
// cout << dp[i][j] << endl;
}
}
// 判断是否能够凑出
// 当背包的最大价值刚好等于自己的最大容量的时候
// 说明此时刚好能够凑出
// cout << dp[N-1][M] << endl;
if (dp[N-1][M] == M) {
cout << "Yes" << endl;
}
else {
cout << "No Solution" << endl;
}
// // debug
// for (int i = 0; i < N; i++) {
// for (int j = 0; j <= bagweight; j++) {
// cout << choice[i][j] << " ";
// }
// cout << endl;
// }
// 回溯构造序列
// 题目指的的最小序列指的是字典序
vector<int> result;
int i = N - 1,j = M;
while(i >= 0 && j > 0) {
if (choice[i][j]) {
result.push_back(coins[i]);
j -= coins[i];
}
i--;
}
sort(result.begin(), result.end());
for (int k = 0; k < result.size(); k++) {
if (k != 0) cout << " ";
cout << result[k];
}
cout << endl;
}
2.3.6测试数据或截图 image.png
2.3.7心得体会 通过这个动态规划硬币找零问题，我深入理解了0-1背包问题在实际场景中的应用。从状态定义、递推公式到路径回溯，整个过程让我体会到动态规划的精妙之处。特别是字典序最小序列的构造，让我认识到算法不仅要解决问题，还要考虑输出结果的优化和规范化。
2.4多处最优服务次序问题 2.4.1题目内容 假设n个顾客同时等待一项服务，顾客i需要的服务时间为 （转word后添加） ，共有s处可以提供此服务。应如何安排n个顾客的服务次序才能使得平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。 对于给定的n个顾客需要的服务时间和s的值，编程计算最优的服务次序。
2.4.2题目要求 【输入】 第一行有两个正整数n和s，表示n个顾客和s处可以为顾客提供需要的服务。 接下来的一行中，有n个正整数，表示n个顾客需要的服务时间。 【输出】 最小平均等待时间，保留三位小数 【输入样例】 10 2 56 12 1 99 1000 234 33 55 99 812 【输出样例】 336.00
2.4.3设计思想 deepseek_mermaid_20260108_9cc952.png
2.4.4算法分析 时间复杂度：O(n log n + n*s) 空间复杂度：O(n + s)
2.4.5核心代码
// 5.3
// 贪心算法
// 多处最优服务次序问题
#include
int main() {
int n,s; // n个顾客 s处服务地点
cin » n » s;
vector
// 先服务耗时短的(贪心 -> 局部最优堆叠全局最优)
sort(clinets.begin(),clinets.end());
// // debug
// for (int i = 0; i < clinets.size(); i++) {
// cout << clinets[i] << endl;
// }
// 每个服务点维护一个当前的工作时间,表示该服务点已经工作了多长时间
// 每当一个顾客被分配了一个服务点,该服务点的工作时间就会增加该顾客的服务时间
// 为什么服务时间要把自己也算上 -> 如果这样子的话题目表述应该为题目逗留时间
for (int i = 0; i < clinets.size(); i++) {
// if (s1 <= s2) {
// s1 += clinets[i];
// result[i] += s1;
// }
// else {
// s2 += clinets[i];
// result[i] += s2;
// }
// 将只能适配两个服务点的代码升级成适配多喝服务点的代码
// 选择已经服务时间最小的等待点
int min_services = 0;
int min_services_index = 0;
for (int j = 1; j < services.size(); j++) {
// 更新最小值
min_services = min(services[min_services_index],services[j]);
// 更新最小下标
if (services[min_services_index] >= services[j]) {
min_services_index = j;
}
}
services[min_services_index] += clinets[i];
result[i] += services[min_services_index];
}
// 计算等待时间
double avg;
double total = 0;
for (int i = 0; i < result.size(); i++) {
total += result[i];
}
avg = total / result.size();
cout << fixed << setprecision(3) << avg << endl;;
}
2.4.6测试数据或截图 image.png
2.4.7心得体会 排序后优先分配给当前耗时最少的服务点，贪心策略有效减少了总体等待时间。
2.5最长公共子串问题 2.5.1题目内容 假设有两个字符串（可能包含空格），找出其中最长的公共连续子串，并输出其长度。 2.5.2题目要求 输入描述: 输入为两行字符串（可能包含空格），长度均小于等于50 输出描述: 输出为一个整数，表示最长公共连续子串的长度 输入例子: abcde abgde 输出例子: 2 ab de
2.5.3设计思想 deepseek_mermaid_20260108_8d0fa8.png
2.5.4算法分析 时间复杂度：O(m × n × min(m, n)) 空间复杂度：O(m × n × min(m, n))
2.5.5核心代码
#include
// 回溯法与分支定界法 // 最长公共子串问题
int main() {
// // // 维护区间的暴力解法 -> 失败(只能处理相同长度字串的操作)
// string str1;
// string str2;
// cin >> str1;
// cin >> str2;
// set<string> result; // 存储找到的最长子串
// int max_sub_len = 0;
// for (int i = 0; i < str1.size(); i++) {
// for (int j = i; j < str1.size(); j++) {
// int each = i;
// int sub_len = 0;
// string str_sub = "";
// while(each <= j) {
// if (str1[each] == str2[each]) {
// sub_len++;
// str_sub += str1[each];
// }
// // max_sub_len = max(max_sub_len,sub_len);
// if (sub_len > max_sub_len) {
// // 如果有更长的最长字串就清除掉旧的,放入新的
// result.clear();
// result.insert(str_sub);
// max_sub_len = sub_len;
// }
// else if (max_sub_len == sub_len) {
// // 如果有相同的最长子串就放入
// result.insert(str_sub);
// }
// else {
// // 没有的话,不做更新
// }
// // 类似于减枝
// if (str1[each] != str2[each]) {
// break;
// }
// each++;
// }
// }
// }
// // 输出结果
// cout << max_sub_len << endl;
// for (set<string>::iterator it = result.begin(); it != result.end(); ++it) {
// cout << *it << endl;
// }
// // 遍历开头的暴力解法 -> 正确
// string str1;
// string str2;
// cin >> str1;
// cin >> str2;
// int max_sub_len = 0;
// set<string> result;
// for (int i = 0; i < str1.size(); i++) {
// for (int j = 0; j < str2.size(); j++) {
// int x = i, y = j;
// string str_sub = "";
// while (x < str1.size() && y < str2.size() && str1[x] == str2[y]) {
// str_sub += str1[x];
// x++;
// y++;
// }
// int sub_len = (x+1) - i - 1;
// // max_sub_len = max(max_sub_len,sub_len);
// if (sub_len > max_sub_len) {
// // 如果有更长的最长字串就清除掉旧的,放入新的
// result.clear();
// result.insert(str_sub);
// max_sub_len = sub_len;
// }
// else if (max_sub_len == sub_len) {
// // 如果有相同的最长子串就放入
// result.insert(str_sub);
// }
// else {
// // 没有的话,不做更新
// }
// }
// }
// // 输出结果
// // cout << max_sub_len << endl;
// // for (string sub : result) { // c98
// // cout << sub << endl;
// // }
// cout << max_sub_len << endl;
// for (set<string>::iterator it = result.begin(); it != result.end(); ++it) {
// cout << *it << endl;
// }
// 动态规划解法 && 分支定界法
/*
二维数组可以比较好的记录所有比较情况
dp[i-1][j-1] // 以下标i-1为结尾的A,以下表j-1为结尾的B -> 方便初始化
// dp[i][0] 和 dp[0][j] 没有意义
*/
string str1;
string str2;
cin >> str1;
cin >> str2;
int max_sub_len = 0;
vector<vector<int> > dp(str1.size() + 1, vector<int>(str2.size() + 1,0));
set<string> result;
for (int i = 1; i <= str1.size(); i++) {
for (int j = 1; j <= str2.size(); j++) {
if (str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
if (dp[i][j] > max_sub_len) {
max_sub_len = dp[i][j];
result.clear();
result.insert(str1.substr((i + 1) - max_sub_len - 1, max_sub_len));
}
else if (dp[i][j] == max_sub_len) {
result.insert(str1.substr((i + 1) - max_sub_len - 1, max_sub_len));
}
}
}
cout << max_sub_len << endl;
for (set<string>::iterator it = result.begin(); it != result.end(); ++it) {
cout << *it << endl;
}
}
2.5.6测试数据或截图 image.png
2.5.7心得体会 动态规划记录子串匹配状态，高效求解最长公共子串，避免重复比较。
2.6哈夫曼编码译码 2.6.1题目内容 编写一个哈夫曼编码译码程序。 按词频从小到大的顺序给出各个字符（不超过30个）的词频，根据词频构造哈夫曼树，给出每个字符的哈夫曼编码，并对给出的语句进行译码。 为确保构建的哈夫曼树唯一，本题做如下限定： （1）选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。 （2）若多棵二叉树根结点权值相等，按先后次序分左右，先出现的作为左子树，后出现的作为右子树。 生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。
2.6.2题目要求 【输入格式】 第一行输入字符个数n； 第二行到第n行输入相应的字符及其词频(可以是整数，与可以是小数）； 最后一行输入需进行译码的串。 【输出格式】 首先按树的先序顺序输出所有字符的编码，每个编码占一行； 最后一行输出需译码的原文，加上original:字样。 输出中均无空格 【样例输入】 3 m1 n1 c2 10110 【样例输出】 c:0 m:10 n:11 original:mnc
2.6.3设计思想 deepseek_mermaid_20260108_5c150b.png
2.6.4算法分析 时间复杂度：O(n² + n log n + L) 空间复杂度：O(n log n)
2.6.5核心代码
#include
// 回溯法与分支定界法 // 哈夫曼编码译码
// 哈夫曼树节点
class HFNode {
public:
int weight; // 权重域
char ch; // 数据域,保存字符信息
vector
// 哈夫曼树类 class HFTree { public:
// 构造函数
HFTree(int n) {
num = n; // 设置叶子节点数量
int m = 2 * n - 1; // 设置哈夫曼节点数量 // 总节点数 = 叶子节点数 + 内部节点数 = n + (n-1) = 2n - 1
nodes.resize(m); // 为节点数组分配空间
root = -1; // 初始化根节点索引为-1
}
// 构建哈夫曼树
void createHFTree() {
/*
节点索引分配
索引0到n-1: 分配给原始叶子节点
索引0到2n-2: 分配给新创建的内部节点
*/
int m = 2 * num - 1;
// 逐个创建内部节点
for (int i = num; i < m; i++) {
// 选择两个权值最小的节点
int min1 = -1 , min2 = -1;
// 我们已经创建了i个节点(包括原始节点和之间创建的内部节点)
// 我们需要从这i个节点中找出两个还没有被合并的（parent == -1）且权重最小的节点
// 第一次遍历: 找到第一个最小的
for (int j = 0; j < i; j++) {
if (nodes[j].parent == -1) {
if (min1 == -1 || nodes[j].weight < nodes[min1].weight) {
min1 = j;
}
else if (nodes[j].weight == nodes[min1].weight) {
// 权值相等时,按照出现先后顺序,下标小的优先
if (j < min1) {
min1 = j;
}
}
}
}
// 第二次遍历: 找到第二个最小的
for (int j = 0; j < i; j++) {
if (nodes[j].parent == -1 && j != min1) { // 不等于最小的最小就是第二个最小的 且 还没有被合并
if (min2 == -1 || nodes[j].weight < nodes[min2].weight) {
min2 = j;
}
else if (nodes[j].weight == nodes[min2].weight) {
// 权值相等时,按照出现先后顺序,下标小的优先
if (j < min2) {
min2 = j;
}
}
}
}
// 确保左子树的权值不大于右子树
if (nodes[min1].weight > nodes[min2].weight) {
swap(min1, min2);
}
// 创建新节点
nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
nodes[i].lchild = min1;
nodes[i].rchild = min2;
nodes[i].parent = -1;
// 更新子节点的父节点
nodes[min1].parent = i;
nodes[min2].parent = i;
// 最后一个创建的节点是根节点
if (i == m - 1) {
root = i;
}
}
}
// 先序遍历输出编码
// 输入: 根节点序号
void preOrderHelper(int node, vector<pair<char,vector<char>>>& result) {
if (node == -1) return;
// 如果是叶子节点,保存字符和编码
if (nodes[node].lchild == -1 && nodes[node].rchild == -1) {
result.push_back({nodes[node].ch, nodes[node].code});
}
preOrderHelper(nodes[node].lchild,result);
preOrderHelper(nodes[node].rchild,result);
}
// 先序遍历输出编码
void preOrder() {
vector<pair<char, vector<char>>> result;
preOrderHelper(root, result);
for (auto& p : result) {
cout << p.first << ":";
for (char c : p.second) {
cout << c;
}
cout << endl;
}
}
// 初始化叶子节点
void Initialization(const vector<pair<char, double>>& chars) {
for (int i = 0; i < num; i++) {
nodes[i].ch = chars[i].first; // 当前节点字符
nodes[i].weight = chars[i].second * 100; // 频率
nodes[i].lchild = -1;
nodes[i].rchild = -1;
nodes[i].parent = -1;
}
}
// 生成哈夫曼编码
void generateCode() {
// 对每个叶子节点生成编码
for (int i = 0; i < num; i++) {
int child = i;
int parent = nodes[child].parent;
vector<char> code;
// 从叶子节点回溯到根节点
while (parent != -1) {
if (nodes[parent].lchild == child) {
code.push_back('0'); // 左分支标记问0
}
else {
code.push_back('1'); // 右分支标记为1
}
child = parent;
parent = nodes[child].parent;
}
// 反转编码
reverse(code.begin(),code.end());
nodes[i].code = code;
}
}
// 译码
string Decoding(string encodedStr) {
string result = "";
int current = root;
for (char bit : encodedStr) {
// 如果当前读取位是'0'表示哈夫曼树中应该走左分支
if (bit == '0') {
current = nodes[current].lchild;
} // 如果当前不是'0'就走右分支
else {
current = nodes[current].rchild;
}
// 如果到达叶子节点
if (nodes[current].lchild == -1 && nodes[current].rchild == -1) {
result += nodes[current].ch;
current = root;
}
}
return result;
}
private:
vector
int main() { // 读取输入字符串个数 int n; cin » n;
// 读取输入的相应的字符及其词频
vector<pair<char,double>> chars(n);
for (int i = 0; i < n; i++) {
string line;
cin >> line;
char ch = line[0];
double freq = stod(line.substr(1)); // 提取字串(提取到末尾) // 返回从索引1到末尾的子串
chars[i] = {ch, freq};
}
// 输入译码
string encodedStr;
cin >> encodedStr;
// 构建哈夫曼树
HFTree hfTree(n); // 构造函数
hfTree.Initialization(chars); // 初始化
hfTree.createHFTree(); // 创建哈夫曼树
hfTree.generateCode(); // 生成哈夫曼编码
// 先序遍历输出编码
hfTree.preOrder();
// 译码并输出原文
string decodedStr = hfTree.Decoding(encodedStr);
cout << "original:" << decodedStr << endl;
}
2.6.6测试数据或截图 image.png
2.6.7心得体会 贪心构建哈夫曼树，从叶子到根反向生成编码，实现高效压缩与准确译码。
2.7奇怪的Andy，奇怪的旅行！ 2.7.1题目内容 在地球上有一个奇怪的国家，这个国家有 n 个城市，但却只有 n−1 条道路，但是每个城市之间都可以互相到达。 某天 Andy 来到了这个国家，但是他以前没有出去旅游，真是个奇怪的人呢。他来到了这个国家进行一次旅行，想花尽量少的钱走过更多的城市， 他不想走回头路，因为这样会多花钱，真是个抠门的人呢。已知的是 dh 可以任意选一个城市作为他旅行的起点。现在他找到你，他想知道他最多能走过多少个城市。
2.7.2题目要求 【输入格式】 第一行一个整数 n 表示这个国家的城市数量。 接下来 n−1行，每一行有两个整数 (u,v) 表示u,v之间有一条边。 tips: 1<=n<=100000 【输出格式】 输出一个数字，表示 Andy最多能走过多少个城市 【样例输入】 3 1 2 1 3 【样例输出】 3 tips: Andy可以按照城市2 −> 城市1 −> 城市3的路线进行旅行。
2.7.3设计思想 deepseek_mermaid_20260108_4a70ab.png
2.7.4算法分析 空间复杂度：O(n) 时间复杂度：O(n)
2.7.5核心代码
#include
// 回溯法与分支定界法 // 奇怪的Andy,奇怪的旅行 // 最多能走过多个城市 -> 任意点最远点是直径端点 /* u: 当前正在访问的节点 parent: 当前节点u的父节点 depth: 从起点到当前节点的距离 */
void dfs(int u, int parent ,int depth , vector
for (int i = 0; i < graph[u].size(); i++) { if (graph[u][i] != parent) { // 不允许访问同一个城市 dfs(graph[u][i], u, depth + 1, dist, graph); } } }
int main() {
// 邻接表构造图
int n;
cin » n;
vector
// 第一次dfs： 从任意节点开始,找到距离最远的节点
// (在树中,从任意节点出发,距离它最远的点一定是树直径的一个端点)
dfs(1, -1, 0,dist,graph); // 以这个节点为起点 那么其父节点为-1(不存在)
// 寻找距离原点距离最远的点
int farthest_first_Node = 0;
for (int i = 2; i < dist.size(); i++) { // 节点1是起点就不遍历了
if (dist[i] > farthest_first_Node) {
farthest_first_Node = i;
}
}
// 第二次dfs: 从第一次找到的最远节点开始(树直径的一个端点),找到直径的另一端
dist.assign(n+1, 0); // 将 vector 的所有元素设置为 0
dfs(farthest_first_Node, -1, 0,dist,graph);
// 查找两次端点的距离就是最大距离
int maxDist = 0;
for (int i = 1; i < dist.size(); i++) {
if (dist[i] > maxDist) {
maxDist = dist[i];
}
}
// 输出最多能走过多少个城市 (最大距离 + 1) - > 直径的节点数 = 边数 + 1
cout << maxDist + 1 << endl;
}
2.7.6测试数据或截图 image.png
2.7.7心得体会 两次DFS求解树直径，巧妙利用最远端点性质。代码简洁高效，个人觉得这种思路非常优雅。
2.8n皇后问题 2.8.1题目内容 给定一个nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋规则棋盘中有一些位置不能放皇后。问总共有多少种放法？使任意的两个皇后都不在同一行、同一列或同一条对角线上。 编程要求：当面向nn格的棋盘上放置彼此不受攻击的n个皇后，找出所有放置方案。
2.8.2题目要求 【输入】 【输入包含多组测试例】 对每个测试例，每行只有一个数字n，(4<=n<=12) 【输出】 对每组测试数据，输出所有可能的放置情况，最后一行是方案总数。 【输入样例】 5 【输出样例】 1 3 5 2 4 1 4 2 5 3 2 4 1 3 5 2 5 3 1 4 3 1 4 2 5 3 5 2 4 1 4 1 3 5 2 4 2 5 3 1 5 2 4 1 3 5 3 1 4 2 Total = 10
2.8.3设计思想 deepseek_mermaid_20260108_71f137.png
2.8.4算法分析 空间复杂度：O(S × n²) 时间复杂度：O(n!)（最坏情况，但实际有大量剪枝）
2.8.5核心代码
#include
// 回溯法与分支定界法 // n皇后问题
// 存储每个方案
vector<vector<vector
// 补充: 这里不需要遍历行,因为在单层搜索的过程中,每一层递归,只会选
// for循环里面的一个元素
// 满足n皇后就返回真,不满足n皇后就返回假
bool isValid(vector<vector
// 遍历135度
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--,j++) {
if (chessboard[i][j] == '*') {
return false;
}
}
return true;
}
// 回溯法暴搜索n皇后问题
void backtracking(int n,int row,vector<vector
for (int col = 0; col < n; col++) {
if (isValid(chessboard,col,row,n)) { // 如果同行同列同斜线存在就不继续搜索了
chessboard[row][col] = '*'; // 放入皇后
backtracking(n,row + 1,chessboard); // 继续递归
chessboard[row][col] = '.'; // 回溯
}
}
}
int main() {
// ‘‘表示放置皇后 ‘.‘表示不防止皇后
int n; // nn的棋盘
cin » n;
// 构造棋盘
vector<vector
// 存储方案总数
vector<vector<int> > count;
// 暴搜计算结果
backtracking(n,0,chessboard); // 先从第0行开始搜索
for (int i = 0; i < result.size(); i++) {
vector<int> temp;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (result[i][j][k] == '*') { // 如果第i个结果的第j行第k列示皇后则统计数据
temp.push_back(k);
}
}
}
count.push_back(temp);
}
// 打印数据
for (int i = 0; i < count.size(); i++) {
for (int j = 0; j < count[0].size() - 1; j++) {
cout << count[i][j] << " ";
}
cout << count[i][count[0].size()-1] << endl;
}
// 题目理解错误的代码
// // 统计结果
// for (int i = 0; i < result.size(); i++) {
// for (int j = 0; j < n; j++) {
// for (int k = 0; k < n; k++) {
// if (result[i][j][k] == '*') { // 如果第i个结果的第j行第k列示皇后则统计数据
// cnt[j][k]++;
// }
// }
// }
// }
// // 输出结果: 输出的是所有可能的放置情况,每一行代表一种方案
// // 该行的数字表示每一行的皇后所在的列号
// for (int i = 0; i < cnt.size(); i++) {
// for (int j = 0; j < cnt[0].size() - 1; j++) {
// cout << cnt[i][j] << " ";
// }
// cout << cnt[i][cnt[0].size() - 1] << endl;
// }
cout << "Total=" << result.size() << endl;
}
2.8.6测试数据或截图 image.png
2.8.7心得体会 回溯法逐行放置皇后，利用约束条件剪枝，输出时注意题目要求列编号从1开始。
3.蓝桥杯题目 3.1星球骑士 3.1.1题目内容 小明冒充 XX 星球的骑士，进入了一个奇怪的城堡。 城堡里边什么都没有，只有方形石头铺成的地面。 假设城堡地面是 n×nn×n 个方格。如下图所示。 按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 nn 个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。 本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
3.1.2题目要求 输入描述 第一行一个整数 NN (0≤N≤200≤N≤20)，表示地面有 N×NN×N 个方格。 第二行 NN 个整数，空格分开，表示北边的箭靶上的数字（自西向东） 第三行 NN 个整数，空格分开，表示西边的箭靶上的数字（自北向南） 输出描述 输出一行若干个整数，表示骑士路径。 为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3 ⋯⋯ 比如，上图中的方块编号为： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 输入输出样例 示例
输入 4 2 4 3 4 4 3 3 3 3.1.3设计思想 deepseek_mermaid_20260108_55fb64.png
3.1.4算法分析 时间复杂度: O(4^(N²)) - 每个位置最多尝试4个方向 空间复杂度: O(N²) - 存储地图、路径和递归栈
3.1.5核心代码
第一题#include
using namespace std;
struct Node { bool flag; int x, y; };
Node map[20][20];
vector
bool dfs(int x, int y) { if (x == N - 1 && y == N - 1) { for (int i = 0; i < N; i++) { if (X[i] || Y[i] || sum) return false; road.push_back(x * N + y); return true; } }
road.push_back(x * N + y);
map[x][y].flag = true;
for (int i = 0; i < 4; i++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (tx < 0 || tx > (N - 1) || ty < 0 || ty > (N - 1))
continue;
if (!map[tx][ty].flag && (X[tx] > 0 && Y[ty] > 0)) {
X[tx]--;Y[ty]--;sum -= 2;
if (dfs(tx, ty))
return true;
else {
X[tx]++;
Y[ty]++;
sum += 2;
}
}
}
map[x][y].flag = false;
road.erase(road.begin() + road.size() - 1);
return false;
}
int main() { cin » N; for (int i = 0; i < N; i++){ cin » Y[i]; sum += Y[i]; } for (int i = 0; i < N; i++) { cin » X[i]; sum += X[i]; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j].flag = false; map[i][j].x = i; map[i][j].y = j; } } X[0]–;Y[0]–;sum -= 2; dfs(0, 0); for (int i = 0; i < road.size(); i++) cout « road[i] « ’ ‘; return 0; } 3.1.6测试数据或截图 image.png
3.1.7心得体会 回溯剪枝巧妙，但指数复杂度不适合大规模问题。
3.2星球青蛙 3.2.1题目内容 X 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。 XX 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。 如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。 ∗WWWBBB∗WWWBBB 其中，WW 字母表示白色青蛙，BB 表示黑色青蛙，∗∗ 表示空杯子。 XX 星的青蛙很有些癖好，它们只做 3 个动作之一： 跳到相邻的空杯子里。 隔着 1 只其它的青蛙（随便什么颜色）跳到空杯子里。 隔着 2 只其它的青蛙（随便什么颜色）跳到空杯子里。 对于上图的局面，只要 1 步，就可跳成下图局面： WWW∗BBBWWW∗BBB 本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
3.2.2题目要求 输入描述 输入为 2 行，2 个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过 15。 输出描述 输出要求为一个整数，表示至少需要多少步的青蛙跳。 输入输出样例 示例
输入 WWBB WWBB
3.2.3设计思想 deepseek_mermaid_20260108_858ef9.png
3.2.4算法分析 时间复杂度: O(6^L) - 最坏情况下每个位置有6种移动选择，L为字符串长度 空间复杂度: O(L×N) - 存储队列中的状态和距离映射，N为状态
3.2.5核心代码
#include
using namespace std;
string start, endd;
queue
int bfs() { unordered_map<string, int> d;//存储该状态下的坐标 q.push(start);//将初始状态入队列 d[start] = 0;//初始状态距离为0 int dx[6] = {-3, -2, -1, 1, 2, 3};//6个向量左三、左二、左一、右一、右二、右三
while (q.size())//当队列为空时结束bfs算法
{
string t = q.front();//出队列,命名为状态t
q.pop();
int distance = d[t];//取出t状态的距离distance
if(t == endd) return distance;//如果t状态和终止状态相等,退出bfs,返回distance
int k = t.find('*');//找出空杯所在的位置
for (int i = 0; i < 6; i ++ )//枚举6个向量
{
int a = k + dx[i];//加上偏移量后点的坐标
if(a >= 0 && a < len)//如果没有越界
{
swap(t[a], t[k]);//交换位置,获取新的状态
if(!d.count(t))//如果该状态未被遍历则更新该状态的距离,入队列
{
d[t] = distance + 1;
q.push(t);
}
swap(t[a], t[k]);//还原现场,因为还有剩余的向量并没有被枚举过
}
}
}
return -1;//如果没有找到的话,返回-1
}
int main() { cin.tie(0);//cin加速器
cin >> start;//读入开始状态
cin >> endd;//读入终止状态
len = start.length();//获取状态的长度
cout << bfs();//输出答案
return 0;
} 3.2.6测试数据或截图 image.png
3.2.7心得体会 BFS求最短路径，状态转移巧妙，利用哈希表避免重复访问，效率较高。
3.3星球坦克 3.3.1题目内容 X 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。 某坦克需要从 A 区到 B 区去（ A，B 区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？ 已知的地图是一个方阵，上面用字母标出了 A，B 区，其它区都标了正号或负号分别表示正负能量辐射区。 例如： A + - + - +
B + - + - 坦克车只能水平或垂直方向上移动到相邻的区。
3.3.2题目要求 输入描述 第一行是一个整数 nn，表示方阵的大小， 4≤n<1004≤n<100。 接下来是 nn 行，每行有 nn 个数据，可能是 A，B，+，- 中的某一个，中间用空格分开。A，B 都只出现一次。 输出描述 输出一个整数，表示坦克从 A 区到 B 区的最少移动步数。 如果没有方案，则输出 -1。 输入输出样例 示例
输入 5 A + - + - +
B + - + - 3.3.3设计思想 deepseek_mermaid_20260108_046e8f.png
3.3.4算法分析 时间复杂度: O(N²) - 每个网格位置最多被访问两次（以’+‘结束和以’-‘结束各一次） 空间复杂度: O(N²) - visited数组和队列占用的空间
3.3.5核心代码
#include
const int MAX_N = 100;
struct Node { int x, y, steps; char last_sign; // 上一步经过的辐射区类型：’+’ 或 ‘-’ };
int n;
vector<vector
// 四个移动方向：下，上，右，左 int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int bfs() {
queue
// 从起点A开始，可以走任意相邻的辐射区
for (int d = 0; d < 4; d++) {
int nx = startX + dir[d][0];
int ny = startY + dir[d][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
char cell = grid[nx][ny];
if (cell == 'B') {
// A直接相邻B
return 1;
}
if (cell == '+' || cell == '-') {
int state = (cell == '+') ? 0 : 1;
if (!visited[nx][ny][state]) {
visited[nx][ny][state] = true;
q.push({ nx, ny, 1, cell });
}
}
}
while (!q.empty()) {
Node cur = q.front();
q.pop();
// 如果当前就是终点
if (cur.x == endX && cur.y == endY) {
return cur.steps;
}
// 尝试四个方向
for (int d = 0; d < 4; d++) {
int nx = cur.x + dir[d][0];
int ny = cur.y + dir[d][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
char next_cell = grid[nx][ny];
// 不能走回A
if (next_cell == 'A') continue;
// 规则：当前是'+'，下一步必须是'-'或B
// 当前是'-'，下一步必须是'+'或B
bool can_move = false;
if (cur.last_sign == '+') {
can_move = (next_cell == '-' || next_cell == 'B');
}
else if (cur.last_sign == '-') {
can_move = (next_cell == '+' || next_cell == 'B');
}
if (can_move) {
int state = 0;
char next_sign = cur.last_sign; // 占位
if (next_cell == '+') {
state = 0;
next_sign = '+';
}
else if (next_cell == '-') {
state = 1;
next_sign = '-';
}
else if (next_cell == 'B') {
// B可以接在任何符号后面，状态可以任意（这里用0）
state = 0;
next_sign = cur.last_sign;
}
if (!visited[nx][ny][state]) {
visited[nx][ny][state] = true;
q.push({ nx, ny, cur.steps + 1, next_sign });
}
}
}
}
return -1;
}
int main() {
cin » n;
grid.resize(n, vector
// 读取网格
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
if (grid[i][j] == 'A') {
startX = i;
startY = j;
}
else if (grid[i][j] == 'B') {
endX = i;
endY = j;
}
}
}
// 初始化visited数组
memset(visited, 0, sizeof(visited));
// 执行BFS
int result = bfs();
// 输出结果
cout << result << endl;
return 0;
} 3.3.6测试数据或截图 image.png
3.3.7心得体会 带状态的BFS解决交替路径问题，状态设计巧妙，避免重复访问相同位置的同种状态。
3.4星球电报 3.4.1题目内容 从 X 星截获一份电码，是一些数字，如下： 13 1113 3113 132113 1113122113 ⋯⋯ YY 博士经彻夜研究，发现了规律： 第一行的数字随便是什么，以后每一行都是对上一行"读出来” 比如第 2 行，是对第 1 行的描述，意思是：1 个 1，1 个 3，所以是：1113 第 3 行，意思是：3 个 1,1 个 3，所以是：3113 请你编写一个程序，可以从初始数字开始，连续进行这样的变换。 3.4.2题目要求 输入描述 第一行输入一个数字组成的串，不超过 100 位。 第二行，一个数字 nn，表示需要你连续变换多少次，nn 不超过 20。 输出描述 输出一个串，表示最后一次变换完的结果。 输入输出样例 示例
输入 5 7
3.4.3设计思想 deepseek_mermaid_20260108_456153.png
3.4.4算法分析 时间复杂度: O(n×k)，其中n为字符串长度，k为b次循环次数，字符串长度可能指数增长 空间复杂度: O(m)，m为最长字符串长度，需要存储中间结果
3.4.5核心代码 #include<bits/stdc++.h> using namespace std; string change(string str) { int i = 0; string ans; while(i < str.size()) { int cont = 0; while(i + cont < str.size() && str[i + cont] == str[i]) cont++; ans += to_string(cont) + str[i]; i = i + cont; } return ans; }
int main() { string a; int b; cin » a » b; while(b–) a = change(a); cout « a; return 0; }//by wqs 3.4.6测试数据或截图 image.png
3.4.7心得体会 外观数列的简洁实现，递归生成模式有趣，字符计数拼接巧妙。
3.5移动距离 3.5.1题目内容 题目描述 X 星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为 1,2,3,⋯⋯ 当排满一行时，从下一行相邻的楼往反方向排号。 比如：当小区排号宽度为 6 时，开始情形如下： 1 2 3 4 5 6 12 11 10 9 8 7 13 14 15 ⋯⋯ 我们的问题是：已知了两个楼号 m,nm,n，需要求出它们之间的最短移动距离（不能斜线方向移动） 3.5.2题目要求 输入描述 输入为 3 个整数 w,m,nw,m,n，空格分开，都在 1 到 10000 范围内，ww 为排号宽度，m,nm,n 为待计算的楼号。 输出描述 要求输出一个整数，表示 m,nm,n 两楼间最短移动距离。 输入输出样例 示例 1
输入 6 2 8
3.5.3设计思想 deepseek_mermaid_20260108_9c9b21.png
3.5.4算法分析 时间复杂度: O(1) - 只进行固定次数的算术运算和条件判断 空间复杂度: O(1) - 只使用固定大小的数组和变量
3.5.5核心代码
#include
3.5.7心得体会 曼哈顿距离的变体计算，楼号与坐标映射巧妙，注意奇偶行排列方向的差异处理。
3.6交换瓶子 3.6.1题目内容 题目描述 有 NN 个瓶子，编号 1 ~ NN，放在架子上。 比如有 5 个瓶子： 2 1 3 5 4 要求每次拿起 2 个瓶子，交换它们的位置。 经过若干次后，使得瓶子的序号为： 1 2 3 4 5 对于这么简单的情况，显然，至少需要交换 2 次就可以复位。 如果瓶子更多呢？你可以通过编程来解决。
3.6.2题目要求 输入描述 输入格式为两行： 第一行: 一个正整数 N (N<104)N (N<104), 表示瓶子的数目 第二行： NN 个正整数，用空格分开，表示瓶子目前的排列情况。 输出描述 输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。 输入输出样例 示例
输入 5 3 1 2 5 4
3.6.3设计思想 deepseek_mermaid_20260108_ff4632.png
3.6.4算法分析 时间复杂度：O(n) - 每个元素仅被访问一次 空间复杂度：O(n) - 使用两个大小为n的数组
3.6.5核心代码
#include
int cnt = 0; //记录初始环数
for (int i = 1; i <= n; i++) {
if (!st[i]) { //没有被标记，找到一个环的起点
cnt++;
for (int j = i; !st[j]; j = a[j]) { //访问这个环，将这个环中所有结点都进行标记
st[j] = true;
}
}
}
cout << n - cnt;
} 3.6.6测试数据或截图 image.png
3.6.7心得体会 通过计算排列中的环数求最小交换次数，思路巧妙，效率极高。
3.7会议描述 3.7.1题目内容 小蓝组织了一场算法交流会议，总共有 50 50 人参加了本次会议。在会议上，大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手 (且仅有一次)。但有 7 7 个人，这 7 7 人彼此之间没有进行握手 (但这 7 7 人与除这 7 7 人以外的所有人进行了握手)。请问这些人之间一共进行了多少次握手? 注意 A A 和 B B 握手的同时也意味着 B B 和 A A 握手了，所以算作是一次握手。
3.7.2题目要求 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
3.7.3设计思想 image.png
3.7.4算法分析 deepseek_mermaid_20260108_347dc0.png
3.7.5核心代码
#include
int main() { const int TOTAL_PEOPLE = 50; const int SPECIAL_GROUP_SIZE = 7;
// 假设编号0-6是那7个人
vector<int> is_special(TOTAL_PEOPLE, 0);
for (int i = 0; i < SPECIAL_GROUP_SIZE; i++) {
is_special[i] = 1;
}
int handshakes = 0;
// 遍历所有可能的握手对
for (int i = 0; i < TOTAL_PEOPLE; i++) {
for (int j = i + 1; j < TOTAL_PEOPLE; j++) {
// 如果两个人都属于特殊组，则不握手
if (is_special[i] && is_special[j]) {
continue;
}
handshakes++;
}
}
cout << handshakes << endl;
return 0;
} 3.7.6测试数据或截图 时间复杂度: O(n²)，其中n=50（固定规模，实际为常数操作） 空间复杂度: O(n)，使用了一个大小为n的标记数组
3.7.7心得体会 组合数学问题，双重循环模拟握手，排除特殊组，简单直接。
3.8庆祝生日 3.8.1题目内容 小橙子为了庆祝生日，买了 nn 种不同尺寸的的矩形蛋糕（可以认为每种蛋糕有无限个，因为小橙子很 rich），第 ii 种蛋糕的长为 aiai，宽为 bibi，一块蛋糕在旋转之后其长和宽将会变为 bi,aibi,ai。小橙子热衷于将一些蛋糕摆放在一条线上（她可以选择旋转蛋糕），并得到以下特殊的“橙线”。 橙线上任意相邻两块蛋糕不能是同一种形状。从第二块蛋糕开始，每一块蛋糕的长度必须等于前一块蛋糕的宽度（第一块蛋糕没有限制）。 请你计算对于长度为 lenlen 的“橙线”，小橙子有多少种不同的摆放方案。因为方案数可能很大，请对 109+7109+7 取模。 两个方案被认为是相同的,当且仅当蛋糕的类型顺序和旋转情况完全一致（正方形的蛋糕无论如何旋转都认为其是同一种情况）。
3.8.2题目要求 第一行两个整数 n,lenn,len，表示蛋糕种类的数量，橙线的长度。 接下来 nn 行，第 ii 行两个正整数 a,ba,b 表示第 i−1i−1 种蛋糕的长和宽。 数据范围保证：1≤n≤1001≤n≤100，1≤len≤20001≤len≤2000, 1≤ai,bi≤1051≤ai,bi≤105。 输出格式 输出一行整数，表示有几种摆放方法可以获得长度为 lenlen 的橙线，对 109+7109+7 取模。 样例输入 2 5 1 4 4 5 样例输出 2 样例说明 第一种：将第一种蛋糕竖着放，即长度贡献为 11，然后第二块蛋糕也竖着放。 第二种：将第二块蛋糕横着放，直接满足了条件。
3.8.3设计思想 deepseek_mermaid_20260108_5fced9.png
3.8.4算法分析 时间复杂度: O(n²)，其中n=50（固定规模，实际为常数操作） 空间复杂度: O(n)，使用了一个大小为n的标记数组
3.8.5核心代码
#include
const int MOD = 1e9 + 7; const int MAXL = 2005; const int MAXS = 205;
int n, L;
vector<pair<int, int» shapes; // (length, width)
vector
int main() { cin » n » L; for (int i = 0; i < n; i++) { int a, b; cin » a » b; shapes.push_back({ a, b }); cake_id.push_back(i); if (a != b) { shapes.push_back({ b, a }); cake_id.push_back(i); } } int S = shapes.size();
// 初始化：第一块蛋糕
for (int s = 0; s < S; s++) {
int len = shapes[s].first;
if (len <= L) {
dp[len][s] = 1;
}
}
// 转移
for (int l = 1; l <= L; l++) {
for (int s = 0; s < S; s++) {
if (dp[l][s] == 0) continue;
int w = shapes[s].second;
for (int t = 0; t < S; t++) {
if (cake_id[t] == cake_id[s]) continue; // 相邻不能是同一蛋糕类型
if (shapes[t].first != w) continue;
int nl = l + shapes[t].first;
if (nl > L) continue;
dp[nl][t] = (dp[nl][t] + dp[l][s]) % MOD;
}
}
}
int ans = 0;
for (int s = 0; s < S; s++) {
ans = (ans + dp[L][s]) % MOD;
}
cout << ans << endl;
return 0;
} 3.8.6测试数据或截图 image.png
3.8.7心得体会 组合数学问题，双重循环模拟握手，排除特殊组，简单直接。
3.9农场黄牛 3.9.1题目内容 小怂有一个超级大的农场，他在里面养了 nn 头黄牛，编号为 1,2,3,…,n1,2,3,…,n，而每头黄牛都有一个家。小怂创立了黄牛派对节，每年都会选择在某头牛的家中举行派对。 今年的黄牛派对节到了，小怂的 nn 头黄牛都要去参加一场在编号为 xx 的黄牛的家中举行的派对，共有 mm 条有向路，每条路都有一定的长度。 每头黄牛参加完派对后都必须回到各自的家中。小怂虽笨，但他养的黄牛很聪明，无论是去参加派对还是回家，每头黄牛都会选择最短路径，求这 nn 头黄牛走一个来回的最短路径中最长的一条路径长度。
3.9.2题目要求 输入格式 第一行有三个正整数 n,m,xn,m,x，分别表示牛的数量 nn，道路数 mm 和在编号为 xx 的黄牛家中举行派对。 接下来 mm 行，每行三个整数 u,v,wu,v,w，表示存在一条由 uu 到 vv 的长度为 ww 的道路。 数据保证：1≤x≤n≤10001≤x≤n≤1000，1≤m≤1051≤m≤105，1≤u,v≤n1≤u,v≤n，1≤w≤1001≤w≤100，保证从任何一个结点出发都能到达 xx 号结点，且从 xx 出发可以到达其他所有节点。 输出格式 输出共 11 行，一个整数，表示这 nn 头黄牛走一个来回的最短路径中最长的一条路径长度。 样例输入 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 样例输出 10 样例解释 对于第 11 头黄牛，1→2→11→2→1，所以它走一个来回的最短路径是 55。 对于第 22 头黄牛，在它这开派对，所以它的一个来回的最短路径是 00。 对于第 33 头黄牛，3→1→2→1→33→1→2→1→3，所以它的一个来回的最短路径是 99。 对于第 44 头黄牛，4→2→1→2→44→2→1→2→4，所以它的一个来回的最短路径是 1010。 所以，一个来回的最短路径中最长的一条路径长度是 1010
3.9.3设计思想 deepseek_mermaid_20260108_4859c6.png
3.9.4算法分析 时间复杂度: O(m log n)，其中n为顶点数，m为边数 空间复杂度: O(n + m)，存储图和距离数组
3.9.5核心代码
#include
typedef pair<int, int> pii; // (距离, 顶点)
void dijkstra(int start, const vector<vector
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, start});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (const pii& edge : graph[u]) {
int v = edge.first;
int w = edge.second;
int nd = d + w;
if (nd < dist[v]) {
dist[v] = nd;
pq.push({nd, v});
}
}
}
}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, x;
cin >> n >> m >> x;
vector<vector<pii>> graph(n + 1); // 原图
vector<vector<pii>> rev_graph(n + 1); // 反向图
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
rev_graph[v].push_back({u, w}); // 反向边
}
vector<int> dist_to(n + 1); // 从x到各点的距离（回家）
vector<int> dist_from(n + 1); // 从各点到x的距离（去派对）
dijkstra(x, graph, dist_to); // 计算回家的最短路径
dijkstra(x, rev_graph, dist_from); // 计算去派对的最短路径（使用反向图）
int ans = 0;
for (int i = 1; i <= n; i++) {
int total = dist_to[i] + dist_from[i];
ans = max(ans, total);
}
cout << ans << endl;
return 0;
} 3.9.6测试数据或截图 image.png
3.9.7心得体会 两次Dijkstra + 反向图，巧妙计算往返最大时间，图论思想精妙。
3.10雨林探险 3.10.1题目内容 小怂和小乐是好朋友，他们一起去到雨林中探险，突然雷风大作，紧接着豆大的雨点从天空中打落下来，然后一只大怪物出现了，小怂与小乐惊呆了，吓得抱在了一起。 瞬间，地上出现了一个 nn 行 mm 列的超大矩阵，矩阵的每个格子要么是空地 . 或者是障碍 #。 他们的起点在 (1,1)(1,1)，要逃到 (n,m)(n,m) 的出口。他们可以上下左右移动一格，这样算作一步。但是幸运的是，他们手上有一个一次性传送门，使用传送门可以瞬移到相对自己位置的 (D,R)(D,R) 向量，也就是说假设他们原来在 (x,y)(x,y)，使用传送门可以到 (x+D,y+R)(x+D,y+R)，这个也算作一步。当然，他们也可以不使用传送门；D,RD,R 可以为负数或零。 他们都很害怕，想要赶紧逃离，所以他们想要知道最小需要几步操作可以离开这个地方，当然他们也可能逃不出来，那就只能等死。
3.10.2题目要求 输入格式 第一行有 44 个正整数， n,m,D,Rn,m,D,R，具体意义已经在问题描述说明。 接下来 nn 行，每行长度是 mm，仅有 . 或者 # 的字符串。 数据保证：1≤n,m≤10001≤n,m≤1000，∣D∣<n∣D∣<n，∣R∣<m∣R∣<m。 输出格式 一行，一个整数，表示逃出这个地方的最小步数。如果他们逃不出来，则输出 −1−1。 样例输入 11 3 6 2 1 …#.. ..##.. ..#… 样例输出 11 5 样例输入 22 3 7 2 1 ..#..#. .##.##. .#..#.. 样例输出 22 -1 样例解释 样例解释 11 (1,1)→(1,2)→(1,3)→(1,1)→(1,2)→(1,3)→ 使用传送门 →(3,4)→(3,5)→(3,6)→(3,4)→(3,5)→(3,6)。 样例解释 22 只有一个一次性传送门的话，他们没办法逃出来。
3.10.3设计思想 deepseek_mermaid_20260108_81be25.png
3.10.4算法分析 时间复杂度: O(n×m) - BFS遍历整个网格两次，再加一次遍历所有点检查传送门 空间复杂度: O(n×m) - 存储两个距离矩阵和网格
3.10.5核心代码
#include
// BFS函数，计算从起点(sx,sy)到所有点的最短距离
vector<vector
int main() {
ios::sync_with_stdio(false);
int n, m, D, R;
cin » n » m » D » R;
vector
// 起点或终点是障碍，直接无法到达
if (grid[0][0] == '#' || grid[n - 1][m - 1] == '#') {
cout << -1 << endl;
return 0;
}
// 计算从起点和终点出发的最短距离
auto dist_from_start = bfs(0, 0, grid, n, m);
auto dist_from_end = bfs(n - 1, m - 1, grid, n, m);
// 初始答案为不使用传送门的步数
int ans = dist_from_start[n - 1][m - 1];
// 枚举使用传送门的点
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '.' && dist_from_start[i][j] != -1) {
int ni = i + D;
int nj = j + R;
// 检查传送目标是否合法
if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '.' && dist_from_end[ni][nj] != -1) {
int steps = dist_from_start[i][j] + 1 + dist_from_end[ni][nj];
if (ans == -1 || steps < ans) {
ans = steps;
}
}
}
}
}
cout << ans << endl;
return 0;
} 3.10.6测试数据或截图 image.png
3.10.7心得体会 BFS+传送门枚举，分情况讨论清晰，双起点BFS求最短路径巧妙。
_9108a3.png)
点赞数据加载中