复试机试准备（自用）-程序员宅基地

技术标签： 算法  c++  图论  复试准备  

机试准备（洛谷）

作为一个输出过程，自己看看
如果想看具体题目或者图片，我都放在markji上了，直接查王道机试就能翻到，全是王道的干货

c/c++相关语法

指针和引用

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-03IV5bXI-1679073159864)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316191331653.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z4MxCYiK-1679073159865)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316191807515.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lbVk9kFw-1679073159865)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316192827412.png)]

值传递-》引用传递

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CZqICYj2-1679073159866)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316193427180.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qbjQtOE4-1679073159866)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316193603500.png)]

自由存储区

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HDNo9Rz2-1679073159866)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316193958001.png)]

c++priorityqueue（优先队列）

C++中的优先队列是一个容器适配器，它提供了一种特殊的数据结构，其中的元素按照一定的顺序排列，可以快速地访问和删除其中某个元素。在优先队列中，每个元素都有一个优先级，元素的处理顺序基于其优先级而不是它们在队列中的位置。

C++中的优先队列实现了一个堆数据结构，它允许在O(log n)的时间内访问堆顶元素，以及在O(log n)的时间内插入和删除元素。优先队列可以使用STL头文件“”中提供的“priority_queue”模板类实现。

下面是使用优先队列的一个简单示例代码：

cpp #include <queue> #include <iostream> using namespace std; int main() { priority_queue<int> pq; pq.push(10); pq.push(5); pq.push(15); cout << pq.top() << endl; // 输出 15 pq.pop(); cout << pq.top() << endl; // 输出 10 return 0; }

在这个示例中，我们创建了一个整数类型的优先队列pq，然后向队列中插入三个元素（10、5、15）。

在访问队列中的元素时，我们使用了pq.top()函数，它返回当前队列中优先级最高的元素，即15。

接着，我们通过调用pq.pop()函数删除了该元素，并再次用pq.top()函数访问了队列中优先级最高的元素，即10。

值得注意的是，优先队列的默认情况下是以大根堆（大的元素优先级高）的形式存储元素的。如果想要实现小根堆（小的元素优先级高），可以将优先队列声明为priority_queue<int, vector, greater> pq;

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hn1ExoyO-1679073159866)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317175741118.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vcg0CtOf-1679073159867)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317175958770.png)]

默认构造的是大根堆，那我们如何构造其小根堆呢-答案：运算符重载

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KyOUUsBJ-1679073159867)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317181012190.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bRlV8G57-1679073159867)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317181016737.png)]

#include <cstdio>
#include <queue>
using namespace std;
struct Element{
    int val;
};
//运算符重载
bool operator <(Element lhs,Element rhs){
    //return true；
    //正常情况下是大根堆是默认：lhs《rhs为真即交换两个元素
    //故如果是小根堆那么rhs《lhs为真
    return rhs.val<lhs.val;
}
int main(){
    priority_queue<Element> queue;
    int arr[]={2,4,2,1,6};
    for (int i = 0; i < 5; ++i) {
        Element e;
        e.val=arr[i];
        queue.push(e);
    }
}

关于map

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rn9VJJUG-1679073159868)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317193209936.png)]

时间较为严格的情况下可以用unordered_map

相关操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-D7CXZLoD-1679073159869)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317193819364.png)]

注意：在使用map时，一般会将每个键-值对封装成pair，并将它们插入到map中。在map中，每个键唯一对应一个pair对象，通过键可以访问到对应的pair对象。pair类的作用在于将两个不同的数据类型组合成一个数据类型，方便我们在map中存储键-值对。

迭代器

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XYMToDhm-1679073159869)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317194137076.png)]

在map中，每个键值对都是一个pair对象，其中第一个元素（也就是pair的first成员）是键，第二个元素（也就是pair的second成员）是值。我们可以通过迭代器来访问map中的元素，其中迭代器指向的是pair对象。我们可以使用it->first访问pair对象中的第一个元素，也就是该键所对应的值。

find方法

用来检查某个建是否存在

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ufXBgOcX-1679073159869)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317194513491.png)]

map中的find方法用于在map中查找指定的键，并返回指向该键值对的迭代器。如果map中存在该键，则find方法返回一个指向该键值对的迭代器；否则返回一个指向map尾部的迭代器end()。通常情况下，我们可以使用迭代器来访问查找到的键值对。

如何切割字串

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tujKbonc-1679073159870)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318003552047.png)]

还剩10天

题目描述

输入两个整数 �,�a,b，输出它们的和（∣�∣,∣�∣≤109∣a∣,∣b∣≤109）。

注意

  1. Pascal 使用 integer 会爆掉哦！
  2. 有负数哦！
  3. C/C++ 的 main 函数必须是 int 类型，而且 C 最后要 return 0。这不仅对洛谷其他题目有效，而且也是 NOIP/CSP/NOI 比赛的要求！
我的题解
#include <iostream>
using namespace std;//为了不加前缀名
int main() {
	int a, b;
	cin >> a >> b;
	cout << a + b;
	return 0;
}

#include <stdio.h>
int main() {
    
	int a, b;
	scanf("%d%d", a, b);
	printf("%d", a + b);
	return 0;
}

题目2

//c++
#include <iostream>
using namespace std;
//第一种方法就是讲元看成10
int main() {
	int a, b;
	cin >> a >> b;
	cout << ((a * 10) + b )/( 19);
	return 0;
}

//c
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
    
	int a,b;
	scanf("%d %d", &a, &b);
	printf("%d", (a * 10 + b)/ (19));
	return 0;
}

题目描述（错了一次复习）

[P1422 小玉P1422 小玉家的电费 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)家的电费 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P1422#submit)

我的题解
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	int sum;
	cin >> sum;
	cout << fixed << setprecision(1);//保留小数点后一位
	if (sum <= 150) cout << sum * 0.4463;
	else if ( sum <=400) cout << 150 * 0.4463 + (sum - 150) * 0.4663;
	else cout << 150 * 0.4463 + 250 * 0.4663 + (sum - 400) * 0.5663;
	
}

/C语言

//c
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    
	int sum;
	scanf("%d",&sum);
	if (sum <= 150) printf("%.1f", sum * 0.4463) ;
	else if (sum <= 400) printf("%.1f", 150 * 0.4463 + (sum - 150) * 0.4663) ;
	else printf("%.1f", 150 * 0.4463 + 250 * 0.4663 + (sum - 400) * 0.5663) ;
}
思路

%用法

1 要输出float a=1.23234; 保留3位小数的写法为：
printf(“%.3f”,a);
2 输出double b=123.345232; 保留4为小数，写法为：
printf(“%.4lf”,b);

题目描述

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7MH08Cxo-1678635540235)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306000340152.png)]

我的题解
int main() {
    
	int a, b, c;
	for (a = 0; a <= 9; a++) {
    
		for (b = 0; b <= 9; b++) {
    
			for (c = 0; c <= 9; c++) {
    
				if ((a * 100 + b * 10 + c) + (b * 100 + c * 10 + c) == 532)
					printf("%d %d %d", a, b, c);
			}
		}
	}
}

题目描述

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0gsuyK3Y-1678635540236)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306023408982.png)]

我的思路：
int main() {
    
	int a, b, c, d,sum;
	for (a = 0; a <= 9; ++a) {
    
		for (b = 0; b < +9; ++b) {
    
			for (c = 0; c <= 9; ++c) {
    
				for (d = 0; d <= 9; ++d) {
    
					sum = a * 1000 + b * 100 + c * 10 + d;
					if (sum * 9 == (d * 1000 + c * 100 + b * 10 + a)) {
    
						if(sum>=1000)
						printf("%d\n", sum);
					}
				}
			}
		}
	}
}

王道用的是求余！！值得学习%%%%

题目描述

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-a8oj7vb2-1678635540236)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306030002374.png)]

我的题解：
int Reverse(int i) {
    
	int k = i * i;
	if (k < 10) {
    
		return k;
	}
	if (10<k &&k< 100) {
    
		int m = k % 10;//个位
		int n = k/10;//十位
		if (m == n) {
    
			return k;
		}
	}
	if (1000 > k&&k> 100) {
    
		int a = k % 10;
		int b = k / 100;
		if (a == b) {
    
			return k;
		}
	}
		if (k > 1000&&k<10000) {
    
			int a = k % 10;
			int b = k / 10 % 10;//十位
			int c = k / 100 % 10;//百位
			int d = k / 1000;//千位
			if ((a == d) && (b == c)) {
    
				return k;
			}
		}
		if (k > 10000 ) {
    
			int a = k % 10;
			int b = k / 10 % 10;//十位
			int c = k / 100 % 10;//百位
			int d = k / 1000%10;//千位
			int e = k / 10000;
			if ((a == e) && (b ==d)) {
    
				return k;
			}
		}
	return 0;
}
int main() {
    
	//本质上还是求的是逆序数
	//首先小于10肯定是
	int i=0;
	//再去找对称的数
	while (i<= 256) {
    
		if (Reverse(i) == i * i) {
    
			printf("%d\n", i);
		}
		i++;
	}
}

不得不说很久不巧写的方法比较笨==

还剩9天

模拟问题

题目描述

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OhQqXc7P-1678635540237)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306162133904.png)]

我的题解
int main() {
    
	printf("请输入一个整数\n");
	int n,h;
	scanf("%d", &h);
	int m = h,k;
	int H = h + (h - 1) * 3;
	for (h; h > 0; --h) {
    
		n = H - m;
		k = m;
		for (n; n > 0; --n) {
    
			printf(" ");
		}
		for (k; k >0;k-- ) {
    
			printf("*");
		}
		m += 2;
		printf("\n");
	}
}
//第一行为h的话，那么高度为h，即最底部的长度应该是
//H=h+(h-1)*3;

王道解法

int main() {
    
	int h;
	while (scanf("%d", &h) != EOF) {
    
		for (int i = 0; i < h; ++i) {
    
			for (int j = 0; j < 2 * h - 2 - 2 * i; ++j) {
    
				printf(" ");
			}
			for (int j = 0; j < h + 2 * i; ++j) {
    
				printf("*");
			}
			printf("\n");
		}
	}
}

使用二维数组去解决模拟问题

char arr[3000][1000];
int main() {
    
	//用二维数组来模拟
	//第一步：填空
	int h;
	while (scanf("%d", &h)!= EOF) {
    
		for (int i = 0; i < h; i++) {
    
			for (int j = 0; j < 3 * h - 2; j++) {
    
				arr[i][j] = ' ';
			}
		}
		//填充完空格开始放星星
		int m = h - 1;
		int k =0;
		for (m; m >= 0; m--) {
    
			for (int n=k ; n<= 3 * h - 2;++n) {
    
				arr[m][n] = '*';
			}
			k += 2;
		}
		//打印
		for (int i = 0; i < h; i++) {
    
			for (int j = 0; j < 3 * h - 2; j++) {
    
				printf("%c",arr[i][j]);
			}
			printf("\n");
		}
	}
}

c风格的字符串设计

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BV0REEMG-1678635540237)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306172043262.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pGbPmDMc-1678635540238)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306172233290.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NM3eLDF7-1678635540238)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306172328511.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W5jrP8CU-1678635540238)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306172740950.png)]

题目描述（错题）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zmqRpElS-1678635540239)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306182210168.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ca2IIKZI-1678635540239)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306193242901.png)]

我的题解

错了看了王道解法，记得在markji上去背

int main() {
    
	int n;//外框长度
	char inner, outter;
	printf("请输入长度以及内外花色\n");
	bool flag = true;
	while (scanf("%d %c %c", &n, &inner, &outter) != EOF) {
    
		if (flag == true) {
    
			flag = false;
		}
		else
		{
    
			printf("\n");
		}
		char pattern[80][80] = {
     0 };//方便最后以字符串的形式输出
		int length = 1;//一开始的外框长度
		int x, y;//坐标
		char changchar = inner;

		for (length = 1, x = n / 2, y = n / 2; length <= n; length = length + 2,--x,--y) {
    
			//填满周围的正方形
			for (int i = x, j = y; i < x + length; i++) {
    
				pattern[i][j] = changchar;
			}
			//左上横线
			for (int i = x, j = y; j < y + length; j++) {
    
				pattern[i][j] = changchar;
			}
			//左下横线
			for (int i = x + length - 1, j = y; j < y + length; j++) {
    
				pattern[i][j] = changchar;
			}
			//右边竖线
			for (int i = x, j = y + length - 1; i < x + length; ++i) {
    
				pattern[i][j] = changchar;
			}
			//做个翻转符号
			if (changchar == inner) {
    
				changchar = outter;
			}
			else
			{
    
				changchar = inner;
			}
		}
		//去四角
		if (n != 1) {
    
			pattern[0][0] = ' ';
			pattern[n - 1][0] = ' ';
			pattern[0][n - 1] = ' ';
			pattern[n - 1][n - 1] = ' ';
		}
	
		//输出图形
		for (int i = 0; i < n; i++) {
    
			printf("%s\n", pattern[i]);
		}
	}
}

8天-排序

必须掌握的库函数-sort（）

//关键代码
//c++引入
//头文件
#include <algorithm>
using namespace std;

头文件cstdio

#include <cstdio>
/*
	作用：<cstdio>是C语言标准库中的一个头文件，其全称为"C Standard Input and Output Library"。这个库提供了用于执行输入输出操作的函数。其中包括常用的输入函数scanf()、getchar()，以及输出函数printf()、putchar()等。这些函数可以让程序员在C语言中进行标准输入输出，从而读写文件、屏幕、键盘等设备。

在C语言中，<cstdio>可以用预处理指令“#include <cstdio>”来引入。一旦引入了这个头文件，就可以在程序中使用库提供的函数。

<cstdio>库函数的使用非常方便，而且效率高。因此，它是C语言程序员经常使用的一个标准库之一。由于C++是基于C语言的，所以在C++中也可以使用<cstdio>库中的函数。但是在C++中，建议使用iostream库进行输入输出操作，因为iostream库比<cstdio>更安全、更易于使用。
*/

using name space 作用解释

在C++中，using namespace std;是一个常用的语句，它的作用是告诉编译器使用std命名空间中的符号。std是C++标准库中许多类和函数所在的命名空间，如果不使用using namespace std语句，那么就需要使用std::来引用这些类和函数，例如std::cout、std::cin等。 使用using namespace std语句可以省略代码中的std::前缀，从而使代码更加简洁易读，但需要注意的是，这样做也会有一些潜在的问题，例如可能会引发命名冲突等问题。因此，一些C++编程规范建议尽可能不要在头文件中使用using namespace std;，而是在具体的源文件中使用。另外，也可以选择只使用需要的部分命名空间，例如using std::cout;只引入std命名空间中的cout符号，而不是整个std命名空间。 总之，using namespace std语句可以简化C++代码的编写，提高代码的可读性，但需要注意一些潜在的问题，并根据实际情况灵活使用。

sort用法实例

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3LzETv0w-1678635540239)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312143313541.png)]

#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    
        int n;//要输入的数字
        while(scanf("%d",&n)!=EOF){
    
            int arr[101];//要输入的数字
            for (int i = 0; i < n; ++i){
    
                //一次输入数字同时放入数组
                scanf("%d",&arr[i]);
            }
            //对数组进行排序
            sort(arr,arr+n);
            //输出
            for (int i = 0; i < n; ++i){
    
                printf("%d",arr[i]);
            }
        }
}

注意点：

arr【i】和arr+i

其实表达意思是完全一样的

arr【i】表示的arr数组中第i号元素的具体值是多少

arr+i表达的意思是arr第i号元素的地址哦

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OJ6yrOLJ-1678635540240)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312144815703.png)]

注意end是尾巴后一个元素的位置

如何设计其排序的规则

默认的排序是升序排序

sort(start,end,compare)//加上一个参数即为compare参数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8mkErHDS-1678635540240)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312145831814.png)]

using namespace std;

bool compare(int lhs,int rhs){
    
    if(lhs>rhs){
    
        return true;
    }else{
    
        return false;
    }
    //也可以写成 return lhs>rhs
    //不发生交换时候返回真
}
int main(){
    
    int arr[8];
    for (int i = 0; i < 8; ++i) {
    
        scanf("%d",arr+i);
    }
    sort(arr,arr+8,compare);
    for (int i = 0; i < 8; ++i) {
    
        printf("%d",arr[i]);
    }
}

第一题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kx914wzC-1678635540240)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312181633384.png)]

我的题解
#include <cstdio>
#include <algorithm>
using namespace std;
bool comp(int i,int j){
    //返回true不交换两个元素
    /*第一种情况：左奇数右边偶数不交换*/
    if(i%2==1&&j%2==0){
        return true;
    }else if(i%2==1&&j%2==1&&i>j){
        //第二种就是判断奇数如果左边大右边小不交换
        return true;
    }else if(i%2==0&&j%2==0&&i<j){
        //第三种情况判断偶数如果左边小右边大不交换
        return true;
    }else{
        return false;
    }
}

第二题

致命错误（第一次写的时候编译错误记录）

使用了变长数组（Variable Length Arrays，VLA），即使用了变量n来定义了一个可以放入n个学生对象的数组students。在C++11标准之前，这种定义数组的方式是不合法的，导致代码可移植性不好，编译器的实现也不稳定。因此，应该使用常量或者宏定义来定义数组的长度，例如使用 #define MAX_STUDENT_NUM 100 来定义数组的最大长度

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JqEMl4P6-1678635540241)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312192346582.png)]

我的题解
#include <cstdio>
#include <algorithm>
#define MAX_STUDENT_NUM 100
using namespace std;
struct Student{
    int stuNum;
    int stuGrade;
};
bool compare(Student lhs,Student rhs){
/*成绩从小到大,排序不变也就是true
     * 若成绩相同，学号大小从小到大*/

    if(lhs.stuGrade<rhs.stuGrade){
        return true;
    } else if (lhs.stuGrade==rhs.stuGrade&&lhs.stuNum<rhs.stuNum){
        return true;
    }else{
        return false;
    }
}
int main(){
        Student students[MAX_STUDENT_NUM];//开辟一个可以放入是个学生对象的数组
    //首先是输入n个整数来表示学生的个数
        int n;
        scanf("%d",&n);

        for(int i=0;i<n;i++){
            scanf("%d%d",&students[i].stuNum,&students[i].stuGrade);
        }
        //接下来排序
        sort(students,students+n, compare);
        for (int i = 0; i < n; ++i) {
            printf("%d %d",students[i].stuNum,students[i].stuGrade);
            printf("\n");//换行
        }
}

第三题

重要技巧：

由于sort底层（快速排序）其实本身并不是稳定的故我们需要自己去设置一个变量，来令其稳定

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MkqaAkHy-1678635540241)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312194125321.png)]

我的题解
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_STUDENT_NUM 100
struct Student{
    char name[100];
    int score;//成绩
    int seq;//保证其有序
};
//升序排序参数
bool upper(Student lhs,Student rhs){
    if(lhs.score<rhs.score){
        return true;
    }else if (lhs.score==rhs.score&&lhs.seq>rhs.seq){
        //相同成绩先录入在前
        return true;
    }else{
        return false;
    }
}
//降序排序参数
bool down(Student lhs,Student rhs){
    if(lhs.score>rhs.score){
        return true;
    } else if (lhs.score==rhs.score&&lhs.seq>rhs.seq){
        //相同成绩先录入在前
        return true;} else{
        return false;
    }
}
int main(){
    Student students[MAX_STUDENT_NUM];
    int n,order;//排序人数和排序方法
    while (scanf("%d%d",&n,&order)!=EOF){
        //依次输入学生信息
        int seq;
        for (int i = 0; i < n; ++i) {
            seq=0;
            scanf("%s%d",&students[i].name,&students[i].score);
            students[i].seq=seq;
            seq++;
        }
        //开始分析是低到高还是告到底
        if(order==1){
            //升序的情况
            sort(students,students+n, upper);
            //输出值
            printf("从高到低 成绩\n");
            for (int i = 0; i < n; ++i) {
                printf("%s %d\n",students[i].name,students[i].score);
            }
        }
        //降序的情况
        if(order==0){
            sort(students,students+n, down);
            printf("从低到高 成绩\n");
            for (int i = 0; i < n; ++i) {
                printf("%s %d\n",students[i].name,students[i].score);
            }
        }
    }
}

第四题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Oto9TD2s-1678635540241)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312204056028.png)]

我的题解
#include <cstdio>
using namespace std;

int main(){
    //首先是输入一个数n
    int n;
    int arr[201];
    scanf("%d",&n);
    for (int i = 0; i < n; ++i){
        scanf("%d",&arr[i]);
    }
    int x;
    scanf("%d",&x);
    int i;
    for ( i = 0; i < n; ++i){
        if(arr[i]==x){
            printf("%d\n",i);
            break;
        }
    }
    if(i==n){
        //说明没有这个玩意
        printf("-1\n");
    }
}

遇到多个数据的时候最好的方式是排序+二分查找哦

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SssNUojp-1678635540242)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312204949484.png)]

容易出现的问题是

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-n4u1q1No-1678635540242)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312205154151.png)]

用map解决查找问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f13bdNmY-1678635540242)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312231325674.png)]

做题前瞻
常用方法名-find（）

在C++中，std::map是一种关联式容器，它将键映射到值。我们可以使用map中的find方法来查找容器中是否存在某个指定的键。 find函数的具体作用为：在map中查找键值等于指定键值的元素，如果能够找到，则返回指向该元素的迭代器；如果查找失败，则返回指向容器尾部的迭代器。

函数的形式为： c++ iterator map::find(const key_type& key); const_iterator map::find(const key_type& key) const; 其中，key为要查找的键值，如果map中存在该键，则返回指向该元素的迭代器；否则返回指向容器尾部的迭代器。

下面是一个使用std::map::find函数的例子：

c++ #include <iostream> #include <map> int main() { std::map<std::string, int> m; m["Alice"] = 90; m["Bob"] = 80; m["Charlie"] = 70; auto it = m.find("Alice"); if (it != m.end()) { std::cout << "Alice's score is " << it->second << std::endl; } else { std::cout << "Alice is not found" << std::endl; } it = m.find("David"); if (it != m.end()) { std::cout << "David's score is " << it->second << std::endl; } else { std::cout << "David is not found" << std::endl; } return 0; }

在这个例子中，我们定义了一个std::map对象m，它将学生的姓名映射到他们的成绩。我们首先向m中添加了三个元素，然后使用find函数查找m中是否存在某个指定的键。第一个查找"Alice"，由于这个键存在于m中，因此find函数返回指向该元素的迭代器，并输出对应的成绩。第二个查找"David"，由于这个键不存在于m中，因此find函数返回指向容器尾部的迭代器，并输出一个提示信息。

find（）常常会和end（）配合使用

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sdGl6wcI-1678635540242)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312233708280.png)]

#include <cstdio>
#include <map>
using namespace std;
int main(){
    map<int,int> findIndex;
    int m,n;
    int arr[101];
    while (scanf("%d",&n)!=EOF){
        for (int i = 0; i < n; ++i){
            scanf("%d",&arr[i]);
            findIndex[arr[i]]=i;
            //将数组元素作为建，数组元素下标作为值
        }
        scanf("%d",&m);
        for (int i = 0; i < m; ++i){
            int findnum;//带查找元素
            scanf("%d",&findnum);
            if(findIndex.find(findnum)!=findIndex.end()){
                printf("NO\n");
            } else{
                printf("YES\n");
            }
        }
    }
}

## 7天-字符串与线性数据结构

> 讨喜的写法：当输入或者是输出的时候呢用
>
> ```c
> scanf or printf
> ```
>
> 但是如果是运算时候分割等操作可以转化为cpp中的string
>
> 涉及的问题是如何互相转化

> 解决方法：
>
> 在C语言中，我们通常使用字符数组（char array）来存储和处理字符串。而在C++中，则提供了一个内置的字符串类型std::string。要将字符数组转换为std::string，可以使用std::string的构造函数，如下所示： ```c++ char cstr[] = "Hello, world!"; std::string cppstr(cstr); ```
>
> 要将std::string转换为字符数组，可以使用std::string的c_str()方法，它返回一个指向C风格字符串的指针，如下所示： ```c++ std::string cppstr = "Hello, world!"; const char* cstr = cppstr.c_str(); ```
>
> 需要注意的是，使用c_str()方法得到的指针指向一个常量字符数组，因此不能修改该数组的内容。如果需要修改字符串内容，则需要将其复制到一个非常量字符数组中。例如： ```c++ std::string cppstr = "Hello, world!"; char cstr[20]; std::strcpy(cstr, cppstr.c_str()); ```这个例子中，我们将std::string复制到了一个大小为20的字符数组中。需要确保目标数组足够大，否则可能会发生缓冲区溢出（buffer overflow）的错误。
>
> ![image-20230314154655789](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314154655789.png)
>
> ![image-20230314154849943](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314154849943.png)

### c++风格字符串的优点

> ![image-20230314155009476](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155009476.png)
>
> ![image-20230314155112548](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155112548.png)
>
> ![image-20230314155227247](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155227247.png)'

**同时string也包含有迭代器**

> ![image-20230314155431537](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155431537.png)

#### string做一个连接的操作

**+**

![image-20230314155734052](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155734052.png)

#### 做一个删除的操作（erase）

![image-20230314160015069](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314160015069.png)

> 数组最后一个换行符，肯定是`str.erase( str.size()-1);`

#### 做一个清空的操作（clear）

`str.clear()`:**会把该字符变成空字符串哦**

#### find操作

![image-20230314161018382](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314161018382.png)

![image-20230314161211834](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314161211834.png)

### 数组的缺点-确定之后无法扩容

![image-20230314162412634](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314162412634.png)

### c++风格的动态数组-vector

![image-20230314163738629](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314163738629.png)

#### 扩容-push_back()

![image-20230314164217532](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314164217532.png)

#### 创建一个数组并在一开始赋值

![image-20230314164404391](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314164404391.png)

#### 主要常用函数方法

![image-20230314164728303](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314164728303.png)

![image-20230314164959562](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314164959562.png)

#### 插入和删除方法

![image-20230314165157382](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314165157382.png)

#### vector底层原理

![image-20230314174821515](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314174821515.png)

![image-20230314174947861](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314174947861.png)

### 相应习题

#### 第一题：

> 因子：数学中的因子指的是能够整除一个给定正整数的所有正整数。例如，6的因子有1、2、3和6。因子通常用于分解质因数的过程中，以及判断一个数是否为质数。一个正整数的因子总是包括1和本身，而其他因子可能会有更多个。

![image-20230314170125174](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314170125174.png)

##### 我的题解

```c++
#include <vector>
#include <cstdio>
using namespace std;
int sum(int i){
    //用于算因子之和
    int sum=0;
    for (int j = 1; j < i; ++j){
        if(i%j==0){
            sum+=j;
        }
    }
    return sum;
}
int main(){
    vector<int> Enum;//完数
    vector<int> Gnum;//盈数
    //要求是输出2-60之间所有的完数和盈数
    for (int i = 2; i <= 60; ++i) {
        if(i==sum(i)){
            //相等的时候,放入容器中
            Enum.push_back(i);
        } else if(i<sum(i)){
            //为盈数
            Gnum.push_back(i);
        }
    }
    //这时候放完了故输出
    printf("E:");
    for (int i = 0; i < Enum.size(); ++i) {
        printf(" %d",Enum[i]);
    }
    printf("\n");
    printf("G:");
    for (int i = 0; i < Gnum.size(); ++i) {
        printf(" %d",Gnum[i]);
    }
}

受限制的线性表

队列

先进先出

c++库中已经依据队列的逻辑结构给予了相应的实现方法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uqYRvq6E-1678814571378)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314175732696.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wIrBLofF-1678814571379)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314175944438.png)]

如何模拟循环队列的效果：

先出再入

队列相关习题

第一题：约瑟夫环

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fbQQnk9z-1678814571379)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314190414080.png)]

我的题解：
#include <queue>
#include <cstdio>
using namespace std;
int main(){
    int n,p,m;
    while (true){
        scanf("%d%d%d\n",&n,&p,&m);
        //输入000出去
        if(n==0&&p==0&&m==0) {
            break;
        }
    /*这时候n表示有n个小孩，队头应该是编号p的小孩子
     * m表示报数奥m的时候队头小孩子出队*/
    //依次入队，队友为p
    queue<int> Children;
        for (int i = p,j=0; j < n; ++j){
            //p--n--1--
            Children.push(i);
            if(i==n){
                i=0;
            }
            i++;
        }
        //出循环说明队列已经初始化完成
        //这时候开始依次出队
        int i=0;
        while(true){
            //当不明确什么时候完成时定为无线循环，到点了break
            //出队
            i++;
            int k=Children.front();//保持头部元素
           Children.pop();//出队
           if(i!=m){
               //说明没到，再放入
               Children.push(k);
           }
           if(i==m){
               //说明到了，这时候输出其编号
               i=0;
               printf("%d,",k);
           }
           //如果只有一个元素了直接输出
           if(Children.size()==1){
               printf("%d",Children.front());
               break;
           }
        }
    }

}
第二题：猫狗收容所

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Q6TAHX7K-1678814571380)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314200148645.png)]

我的题解
#include <queue>
#include <cstdio>
using namespace std;
struct Animal{
    int num;//编号
    int queue;//表示进入队列的顺序，因为队列的先后动作关乎于第一种收养方式
};
int main(){
    //处理输入数据
    int n;
    scanf("%d",&n);
    int m,t;
    queue<Animal> DogQue;
    queue<Animal> CatQue;
    int queue=1;
    for (int i = 0; i < n; ++i){
        scanf("%d%d",&m,&t);//m表示是送动物进入/收养，t表示的是动物编号
        if(m==1){
            //这种情况说说明是要送入收养
            if(t<0){
                //送猫
                Animal cat;
                cat.queue=queue++;
                cat.num=t;
                CatQue.push(cat);
            } else if(t>0){
                //送狗
                Animal dog;
                dog.queue=queue++;
                dog.num=t;
                DogQue.push(dog);
            } else{
                continue;//直接进入下一次循环
            }
        }
        else if(m==2){
            //说明是要收养
            if(t==1){
                /*指定收养狗*/
                if(!DogQue.empty()){
                    Animal g=DogQue.front();//队头元素
                    DogQue.pop();//不为空
                    printf("%d ",g.num);//输出其编号
                } else{
                    continue;
                }
            }
            else if(t==-1){
                //收养猫
                if(!CatQue.empty()){
                    Animal g=CatQue.front();//队头元素
                    CatQue.pop();//不为空
                    printf("%d ",g.num);//输出其编号
                } else{//说明空了
                    continue;
                }
            }
            else if(t==0){
                //收养最早进入队列元素
                //收养狗的情况
                if(CatQue.empty()&&!DogQue.empty()||
                        (!CatQue.empty()&&!DogQue.empty()&&CatQue.front().queue>DogQue.front().num)){
                    printf("%d ",DogQue.front().num);
                    DogQue.pop();
                } else if(CatQue.empty()&&DogQue.empty()){
                    continue;
                } else{
                    //剩下的情况：猫不为空，狗空；猫狗不空但是猫编号小
                    printf("%d ",CatQue.front().num);
                    CatQue.pop();
                }
            }

        }
    }
}

栈

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AvMeK1HO-1678814571380)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314231006866.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-98Cl1GTf-1678814571380)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314231450870.png)]

相关习题
第一题：反转数字

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8w1COHeN-1678814571380)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314232613751.png)]

我的题解：
//反转数字输出
#include <cstdio>
#include <stack>
using namespace std;
int main(){
    //数字范围很大故要用longlong型存储
    long long num;
    int n;//输入数字
    scanf("%d",&n);
    stack<long long>stack;
    for (int i = 0; i < n; ++i){
        scanf("%lld",&num);
        stack.push(num);
    }
    //然后再出栈输出
    while(!stack.empty()){
        printf("%lld ",stack.top());
        stack.pop();
    }
    printf("\n");
}
第二题：括号匹配

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0mHXzAsV-1678814571381)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315001034874.png)]

我的题解：
#include <cstdio>
#include <string>
#include <stack>
using namespace std;
int main(){
    
    char str[200];//等待输入的字符
    string string1;
    while(fgets(str,199,stdin)!=NULL){
    
        //读取一个词语-scanf+%s
        //若是要读一行字用fgets配合上while可以实现不确定行数的多行输入
        string1=str;//转化为c++风格的字符串
        string1.pop_back();//去掉结尾的\n,因为fgets会读取多余的换行符
        stack<unsigned > index;//存放下标
        string  string2;//存放结果字符串
        for (int i = 0; i < string1.size(); ++i) {
    
            if(string1[i]=='('){
    
                index.push(i);
                string2.push_back('$');//假装是匹配的知道遇到右括号
            } else if(string1[i]==')'){
    
                //第一种情况：栈中为空这时候无匹配项了
                if(index.empty()){
    
                    string2.push_back('?');
                } else{
    
                    //说明有左括号哦
                    string2.push_back(' ');
                    int k=index.top();
                    string2[k]=' ';
                    index.pop();
                }
            }else{
    
                //其他字符直接当空格放入就行
                string2.push_back(' ');
            }
        }
        //这时候输出就好了
            printf("%s\n%s",string1.c_str(),string2.c_str());
    }
}
第三题：简单计算器（难）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YjWFEoWz-1678814571381)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315012038618.png)]

我的题解：
#include <stack>
#include <string>
#include <cstdio>
#include <map>
using  namespace std;
int main(){
    map<char,int> priority{
            {'$',0},
            {'+',1},{'-',1},
            {'*',2},{'/',2}
    };
    char buf[300];

    while(fgets(buf,300,stdin)!=NULL){
        string expr=buf;
        expr.pop_back();
        if(expr=="0"){
            break;
        }
        expr.push_back('$');
        string num;//用来收集单独的0-9
        stack<double> numstack;
        stack<char> operstack;
        for (unsigned i = 0; i <expr.size() ; ++i) {
            if(expr[i]>='0'&&expr[i]<='9'){
                /*在 ASCII 码表中，'0' ~ '9' 的字符编码分别为 48 ~ 57，
                 * 因此它们的大小关系是从小到大依次为'0' < '1' < '2' < ... < '9'，其中 '0' 最小，'9' 最大。 */
                num.push_back(expr[i]);
            }else if(expr[i]==' '){
                if(num!=" "){
                    numstack.push(stod(num));
                    num=" ";
                }
            }
            else{
                //+ - / *
                if(expr[i]=='$'){
                    //结尾
                    if(num!=" "){
                        numstack.push(stod(num));
                        num=" ";
                    }
                }
                while(!operstack.empty()&&priority[operstack.top()]>= priority[expr[i]]){
                    char oper=operstack.top();
                    operstack.pop();
                    double rhs=numstack.top();
                    numstack.pop();
                    double  lhs=numstack.top();
                    numstack.pop();

                    switch (oper) {
                        case '+':
                            numstack.push(lhs+rhs);
                            break;
                        case '-':
                            numstack.push(lhs-rhs);
                            break;
                        case '/':
                            numstack.push(lhs/rhs);
                            break;
                        case '*':
                            numstack.push(lhs*rhs);
                            break;
                    }
            }
                operstack.push(expr[i]);
            }
        }
        printf("%.2lf\n",numstack.top());
    }
}
表达式的解析问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F0OZ9wHG-1678814571381)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315002248526.png)]

表达式的数据结构设计

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lP12lOZu-1678814571382)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315002512582.png)]

读取字符串的操作！（很重要）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xu2kmjHf-1678814571382)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314233458670.png)]、

6天-函数调用的本质和递归的原理

函数调用的本质

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2X7PBx7I-1678881535184)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315150025181.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TvasZxeK-1678881535185)(D:\刷题图片\image-20230315150500425.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-c4MGtlgT-1678881535185)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315150542624.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-42iZpAjy-1678881535186)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315151156157.png)]

金典理解方面的错误：并不是进入main函数操作系统才申请栈区的哦

在进入 main 函数之前，程序会首先进行一些初始化操作，包括分配栈区等操作。具体来说，当操作系统启动一个进程时，会为这个进程分配一些虚拟内存空间，其中一部分用于存储栈区。 在进入 main 函数之前，操作系统会把一部分虚拟内存空间分配给栈区，然后在进入 main 函数时，程序会在这段栈区中为 main 函数的局部变量、参数等分配空间。当 main 函数结束时，程序会释放 main 函数所分配的栈空间，然后退出进程，操作系统会收回这些虚拟内存空间。 所以可以说，在进入 main 函数之前，程序已经分配了栈区，但这并不代表这个栈区一定很大，栈区的大小取决于操作系统的分配策略和硬件资源的限制。

所以一直递归不出栈才会导致爆栈

第二点：栈区申请具体流程

在程序运行时，栈区是在进入函数时动态开辟的，也就是说，当函数被调用时，栈会自动分配一段地址空间，并且会在函数调用结束时释放。 栈区的大小是由操作系统根据需要来动态分配的，而不是由程序员手动定义的。当进程启动时，操作系统会为进程分配一定大小的栈空间。当函数调用时，程序将栈指针向下移动，以为当前调用函数预留一定大小的栈空间，栈大小的限制取决于操作系统对栈区的分配策略和硬件资源的限制。 在C语言中，栈的大小是可以通过修改编译器或链接器的设置来改变的，但是这样做并不是一个好的选择，并且一般来说，程序员也不需要手动去管理栈的大小。另外，如果在函数中定义了过多的局部变量、数组等数据，可能会导致栈区溢出，从而导致程序崩溃。

第三点：如何避免爆栈

要避免栈溢出（stack overflow），可以采取以下措施：

减少局部变量和递归调用的深度：在函数中声明的局部变量以及递归调用的深度都会占用栈空间，如果变量和调用层数过多，就容易导致栈溢出。

使用动态分配的内存：可以通过使用动态分配的内存（如 malloc、calloc 等）来减少栈的使用量。动态分配的内存存放在堆区，不会影响栈空间的大小。

增加栈空间的大小：可以通过修改编译器或链接器的设置来增加栈空间的大小，但是这种方法并不推荐，因为栈空间的大小是受到硬件资源限制的。

使用尾递归：尾递归是指函数调用自身，并且这个函数调用是出现在所返回的值上，而不是出现在表达式的中间。使用尾递归可以避免递归调用的深度过大，从而减少栈空间的使用量。

编写代码时，注意检查边界条件：例如，当使用数组或指针时，一定要确保不会访问到超出数组或指针范围的内存。这样即使出现了错误也不会导致栈溢出。 需要注意的是，栈溢出是一种非常危险的情况，可能会导致程序崩溃或者出现未定义的行为。因此，在编写代码时一定要格外小心，避免出现栈溢出的情况。

递归推导的要点

递归推导的基本方法是找到一个递推公式或者递归式来表示原问题，然后通过对公式或者式子的分析，得到问题的解。 具体的技巧包括：

  1. 找出递推公式或递归式，确定递归边界。对于递归问题，首先要确定递归关系，即原问题和子问题之间的关系。在找到递归关系之后，需要确定边界条件，即最小和最简单的问题的解，也就是递归问题的停止条件。
  2. 简化递归问题。对于复杂的递归问题，可以通过简化问题，缩小问题规模的方式来减少问题的复杂度，使得问题更易于处理。例如，可以考虑将原问题分解为若干个子问题，然后递归地解决这些子问题，最后合并子问题的结果得到原问题的解。
  3. 求解递归问题。在确定了递归关系和边界条件之后，就可以递归地求解问题了。在每一次递归调用中，首先需要判断是否满足递归边界，如果满足，则返回边界条件对应的结果；否则，继续递归解决子问题，并将子问题的结果合并，得到当前问题的解。
  4. 验证和优化递归算法。验证递归算法的正确性和优化递归算法的效率也是很重要的技巧。在验证递归算法时，可以使用数学归纳法或者反证法等方法。在优化递归算法时，可以考虑使用记忆化搜索或者动态规划等技术。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nfHjAne3-1678881535186)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315152618230.png)]

第一题：n的阶乘

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tmqS8w2f-1678881535187)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315160501949.png)]

我的题解:
#include <cstdio>
using namespace std;
int func(int i){
    if(i==1){
        return 1;
    }
   return i *func(i-1);

}
int main(){
    //求n的阶乘
    int n;
    scanf("%d",&n);
    printf("%d", func(n));
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Nx3YSWTP-1678881535187)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315160531961.png)]

\

第二题：汉诺塔问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IhgN4yr4-1678881535187)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315162643525.png)]

我的题解：
//递归金典问题：汉诺塔问题
#include <cstdio>
using namespace std;
//指数级增长用longlong

int Hanuo(long long i){
    //1.推导的是n和n-1的关系-》3*hanuo（n-1）+2
    //2.算出口即n=1的时候——》2
    if(i==1){
        return 2;
    }
    else{
        return 3*Hanuo(i-1)+2;
    }
}
int main(){
    int  N;
    while(scanf("%d",&N)!=EOF){
        printf("%lld", Hanuo(N));
        printf("\n");
    }
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ibxxSLG3-1678881535188)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315163107236.png)]

从分而治之到递归的过程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m07Su8BL-1678881535188)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315180947444.png)]

分而治之（Divide and Conquer）是一种将大问题分解成若干个小问题来解决的问题求解策略。

它通常包括三个步骤：分解问题、解决问题、合并问题的解。

在分解问题时，将问题分解为若干个规模较小、结构与原问题相似的子问题，然后对这些子问题进行递归求解。在解决问题时，利用递归求解子问题得到子问题的解。在合并问题的解时，将子问题的解合并为原问题的解。 而递归（Recursion）是一种在函数定义中使用函数自身的方法。当函数调用自身时，就形成了递归调用。

从分而治之到递归的过程主要体现在解决问题的步骤上。在分而治之中，利用递归求解子问题得到子问题的解后，需要将子问题的解合并为原问题的解。在这个过程中，往往需要编写额外的代码来实现合并。而在递归中，自然而然地得到了子问题的解，避免了额外的合并操作。

例如，对于快速排序算法，它是一种基于分而治之策略的排序算法。在分解问题时，将待排序序列分成两个子序列，然后分别递归地对子序列进行排序。在解决问题时，通过递归排序子序列得到子序列的有序序列，然后通过合并两个有序序列得到原问题的有序序列。而在递归中，每个子序列的有序性质都可以自然地得到，不需要额外的合并操作，使得算法更加简洁高效。 因此，从分而治之到递归的过程，是从手动实现合并操作到利用递归自然地得到子问题的解，使得算法更加简洁高效的过程。

典型例题：斐波那契数列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gp7gjmR5-1678881535189)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315182058835.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FjaPEp0d-1678881535189)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315182412462.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ukR6LbxO-1678881535189)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315182502250.png)]

#include <cstdio>
int Func(int i){
    if(i==1){
        return 1;
    } else if(i==0){
        return 0;
    } else{
        return Func(i-1)+ Func(i-2);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    printf("%d", Func(n));
}
典例二：二叉树习题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4oNJglFA-1678881535190)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315194233641.png)]

首先，我们可以利用递归求解二叉树的节点总数。具体来说，我们可以定义一个函数getNodeNum，它的输入是一个二叉树的根节点root，输出是该二叉树的节点总数。该函数的实现步骤如下： 1. 若root为空，返回0。 2. 否则，递归计算root节点的左子树和右子树的节点总数，再加上1（因为root节点也算一个节点），得到该二叉树的节点总数。 3. 返回上一层调用栈，将左右子树的节点总数相加，得到上一层的节点总数，并最终返回根节点的节点总数。

其次，我们可以在后序遍历的过程中，对每个节点计算其子树的节点总数，并记录每个节点子树的节点总数是否等于给定的数m。具体来说，我们可以定义一个函数getSubtreeWithNodeNum，它的输入是一个二叉树的根节点root、一个整数m和一个vector res，输出是所有节点子树的节点总数等于m的节点。该函数的实现步骤如下： 1. 若root为空，直接返回。 2. 否则，先递归遍历左子树和右子树。 3. 再计算当前节点root的左子树和右子树的节点总数leftNum和rightNum，再加上1，得到以root为根节点的子树的节点总数totalNum。 4. 若totalNum等于m，将root加入结果集res中。 5. 返回上一层调用栈。 最后，我们可以调用函数getSubtreeWithNodeNum，得到所有节点数为m的子树的根节点。

#include <cstdio>
using namespace std;
//确定完全二叉树怎么算
int getNodeNum(int m,int n){
    //求的是结点编号为m的子树的结点总数
    if(m>n){
        return 0;
    } else{
        return 1+ getNodeNum(2*m,n)+ getNodeNum(2*m+1,n);
    }
}


int main(){
    //输入
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
        if(m==0&&n==0){
            break;
        } else{
            printf("%d\n", getNodeNum(m,n));
        }
    }
}

5天-树型结构

二叉树-链式存储

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-B813wHbQ-1679073096802)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316195951626.png)]

结构体设计

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kLNVs7mY-1679073096804)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316200346003.png)]

如何建树-层次建树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9qT0UB5Z-1679073096804)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316200831870.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A1aquzVE-1679073096805)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316201059619.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-o1IZgXuw-1679073096805)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316201222908.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NVU2uzM8-1679073096805)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316201428478.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KkuA6Gtr-1679073096806)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316201728622.png)]

堆空间并不会因为退出函数体就销毁哦[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R8oIUQKy-1679073096806)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316201835572.png)]

#include <cstdio>
#include <queue>
using namespace std;
//树结点定义
struct TreeNode{
    char val;
     TreeNode* left;
     TreeNode* right;
};
//辅助队列结点定义
struct QueueNode{
    TreeNode* parent;//指向其二叉树结点
    bool isLeft;//有无左子树
};
//插入方法
void InsertNode(TreeNode* &root,queue<QueueNode*> &myQueue,char data){
    if(data!='#'){
        //第一种情况，data不为空,创新节点放入
        TreeNode* treeNode=new TreeNode;
        treeNode->val=data;
        QueueNode* queueNode=new QueueNode;//队列结点
        queueNode->parent=treeNode;
        queueNode->isLeft= false;
        myQueue.push(queueNode);//入队
        if(root==NULL){
            //说明是第一个结点
            root=treeNode;
        }else{
            //不是第一个结点找他的父节点
            QueueNode* Pparent=myQueue.front();
            //看看放在哪
            if(Pparent->isLeft== false){
                //放左边
                Pparent->parent->left=treeNode;
                Pparent->isLeft=true;
            }else{
                Pparent->parent->right=treeNode;//放满了可以出队列了
                myQueue.pop();
                delete Pparent;
            }
        }
    }
    else{
        //说明是空的也就是插入结点为null
        if(root!=NULL){
            //如果空为空树直接不管
            QueueNode* Pparent=myQueue.front();
            if(Pparent->isLeft== false){
                //左边没有zhikong
                Pparent->parent->left=NULL;
                Pparent->isLeft=true;
            }else{
                //左字数有了右子树置为空
                Pparent->parent->right=NULL;
                myQueue.pop();
                delete Pparent;
            }
        }
    }
}
int main(){
    TreeNode* root=NULL;//一定要记得给个NULL错了n次就是因为忘记初始化
    queue<QueueNode*> myQueue;
    char  Charlist[]="abc##de#g##f###";
    for (int i = 0; Charlist[i]!='\0'; ++i) {
        InsertNode(root,myQueue,Charlist[i]);
    }
    LevelOrder(root);
}
二叉树的广度优先遍历

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OJLeu0bS-1679073096806)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230316213546353.png)]

//层次遍历
void LevelOrder(TreeNode* root){
    queue<TreeNode*> myQueue;
    myQueue.push(root);
    while(!myQueue.empty()){
        TreeNode* tmp=myQueue.front();
        printf("%c ",tmp->val);
        //出去+有左放左有右放右
        myQueue.pop();
        if(tmp->left!=NULL){
            myQueue.push(tmp->left);
        }
        if(tmp->right!=NULL){
            myQueue.push(tmp->right);
        }
    }
}
二叉树递归遍历
//前序遍历
void preOrder(TreeNode* root){
    if(root==NULL){
        return;
    }
    printf("%c ",root->val);
    preOrder(root->left);
    preOrder(root->right);
}
//中序遍历
void inOrder(TreeNode* root){
    if(root==NULL){
        return;
    }
    inOrder(root->left);
    printf("%c ",root->val);
    inOrder(root->right);
}
//后序遍历
void postOrder(TreeNode* root){
    if(root==NULL){
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%c ",root->val);
}
二叉树的重建

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vIM8DKcM-1679073096807)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317012817881.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mh9c2vG8-1679073096807)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317013132699.png)]

//根据前序和中序重建二叉树
#include <cstdio>
#include <string>
using namespace std;
struct TreeNode{
    
    char val;
    TreeNode* lChild;
    TreeNode* rChild;
};
TreeNode* ReBuild(string preorder,string inorder){
    
    if(preorder.size()==0||inorder.size()==0){
    
        return NULL;
    } else{
    
        //找到根节点值
        TreeNode* root=new TreeNode;
        char posval=preorder[0];
        root->val=posval;
        //从中序查到该点下标
        int pos=inorder.find(posval);
        //分割结点由大化小,前序切割成小前序
        root->lChild= ReBuild(preorder.substr(1,pos),inorder.substr(0,pos));
        root->rChild= ReBuild(preorder.substr(pos+1),inorder.substr(pos+1));
        return root;
    }
}

//后序遍历
void postOrder(TreeNode* root){
    
    if(root==NULL){
    
        return;
    }
    postOrder(root->lChild);
    postOrder(root->rChild);
    printf("%c ",root->val);
}
int main(){
    
    char preorder[30];
    char inorder[30];
    while (scanf("%s%s",preorder,inorder)!=EOF){
    
        TreeNode* root;
        root=ReBuild(preorder,inorder);
        postOrder(root);
    }
}
给出特殊的前序序列遍历二叉树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AqEnPibB-1679073096808)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317142657119.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AwK2cxvJ-1679073096808)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317142924022.png)]

#include <cstdio>
#include <string>
using namespace std;
struct TreeNode{
    char val;
    TreeNode* LChild;
    TreeNode* RChild;
};
TreeNode* RecursiveBuildTree(string str,int& i){
    char value=str[i];
    i++;
    //找根结点
    if(value=='#'){
        return  NULL;
    }
    else{
        TreeNode* treeNode=new TreeNode;
        treeNode->val=value;
        treeNode->LChild= RecursiveBuildTree(str,i);
        treeNode->RChild= RecursiveBuildTree(str,i);
        return treeNode;
    }
}
void InOrder(TreeNode* root){
    if(root==NULL){
        return;
    }
    InOrder(root->LChild);
    printf("%c ",root->val);
    InOrder(root->RChild);
}
int main(){
   /* string str="ab##cd#gf###e##";*/
    char str[3000];
    while(scanf("%s",str)!=EOF) {
        int i = 0;//起始下标
        TreeNode *root = RecursiveBuildTree(str, i);
        InOrder(root);
        printf("\n");
    }
}
二叉搜素树的插入

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RPJ7AlMl-1679073096808)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317151059692.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jFUvQZWL-1679073096809)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317151352311.png)]

//二叉搜索树插入的实现
#include <cstdio>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* LChild;
    TreeNode* RChild;
};
void BuildTree(TreeNode* &root,int data){
    TreeNode* treeNode=new TreeNode;
    treeNode->val=data;
    treeNode->LChild=NULL;
    treeNode->RChild=NULL;
    if(root==NULL){
        root=treeNode;
    } else{
      TreeNode* pPre=root;
      TreeNode* cur;
         while (true){
            if(data<pPre->val){
                //走左边
                cur=pPre->LChild;//查左边结点
                if(cur==NULL){
                    pPre->LChild=treeNode;
                    break;
                } else{
                    //说明有继续走，及定位在cur
                    pPre=cur;
                }
              }
            else{
                cur=pPre->RChild;
                if(cur==NULL){
                    //说明插入此处
                    pPre->RChild=treeNode;
                    break;
                }else{
                    //说明有继续找
                    pPre=cur;
                }
            }
        }
    }
}
int main(){
    TreeNode* root=NULL;
    int array[]={2,3,5,1,4};
    for (int i = 0; i < 5; ++i) {
        BuildTree(root,array[i]);
    }
}

相关习题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WTLsC98w-1679073096809)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317161416205.png)]

//二叉搜索树插入的实现
#include <cstdio>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* LChild;
    TreeNode* RChild;
};
void BuildTree(TreeNode* &root,int data){
    TreeNode* treeNode=new TreeNode;
    treeNode->val=data;
    treeNode->LChild=NULL;
    treeNode->RChild=NULL;
    if(root==NULL){
        root=treeNode;
        printf("-1\n");
    } else{
      TreeNode* pPre=root;
      TreeNode* cur;
         while (true){
            if(data<pPre->val){
                //走左边
                cur=pPre->LChild;//查左边结点
                if(cur==NULL){
                    pPre->LChild=treeNode;
                    printf("%d\n",pPre->val);
                    break;
                } else{
                    //说明有继续走，及定位在cur
                    pPre=cur;
                }
              }
            else{
                cur=pPre->RChild;
                if(cur==NULL){
                    //说明插入此处
                    pPre->RChild=treeNode;
                    printf("%d\n",pPre->val);
                    break;
                }else{
                    //说明有继续找
                    pPre=cur;
                }
            }
        }
    }
}
int main(){
    TreeNode* root=NULL;
   int n;
    scanf("%d",&n);
    int m;
    for (int i = 0; i < n; ++i) {
        scanf("%d",&m);
        BuildTree(root,m);
    }
}
判断不是同一颗树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y6ngRxlQ-1679073096809)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317173607252.png)]

#include <cstdio>
#include <string>

using namespace std;

struct TreeNode{
    char data;
    TreeNode* lChild;
    TreeNode* rChild;
};
//建立一个二叉搜索树函数
void InsertBuild(TreeNode*& root,char data){
    TreeNode* treeNode=new TreeNode;
    treeNode->data=data;
    treeNode->rChild=NULL;
    treeNode->lChild=NULL;
    if(root==NULL){
        root=treeNode;
    }
    else{
        TreeNode* pPre=root;
        TreeNode* cur;
        while(true){
            if(data<pPre->data){
                //左边
                cur=pPre->lChild;
                if(cur==NULL){
                    pPre->lChild=treeNode;
                    break;
                } else{
                    //说明有
                    pPre=cur;
                }
            }else{
                //大于的情况走右边
                cur=pPre->rChild;
                if(cur==NULL){
                    pPre->rChild=treeNode;
                    break;
                } else{
                    pPre=cur;
                }
            }
        }
    }
}
string InOrder(TreeNode* root){
    if(root==NULL){
        return " ";
    }
    return InOrder(root->lChild)+root->data+ InOrder(root->rChild);
}
string PreOrder(TreeNode *root){
    if(root==NULL){
        return " ";
    }
    return root->data+ PreOrder(root->lChild)+ PreOrder(root->rChild);
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0){
            break;
        }
        char str1[100];
        scanf("%s",str1);
        TreeNode* root=NULL;
        for (int i = 0; str1[i]!='\0'; ++i) {
            InsertBuild(root, str1[i]);
        }
        string preorder1= PreOrder(root);
        string inorder1= InOrder(root);
 /*       printf("%s %s",preorder1.c_str(),inorder1.c_str());*/
        char str2[100];
        for (int i = 0; i < n; ++i) {
            scanf("%s",str2);
            TreeNode* root2=NULL;
            for (int j = 0; str2[j] !='\0' ; ++j) {
                InsertBuild(root2,str2[j]);
            }
            string preorder2= PreOrder(root2);
            string inorder2= InOrder(root2);
            if(preorder1==preorder2&&inorder2==inorder1){
                    printf("YES\n");
            }else{
                printf("NO\n");
            }
        }
    }
}

堆

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iDYKf4fr-1679073096810)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317175127268.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WzpTUH7V-1679073096810)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317175600063.png)]

第一题：复数集合

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1iQ8uKwe-1679073096810)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317185111012.png)]

我的题解：
#include <cstdio>
#include <string>
#include <queue>
using namespace std;
//定义复数的结构体
struct complex{
    int real;
    int image;
};
//运算符重载
//交换就返回true
bool operator <(complex a,complex b){
    return a.real*a.real+a.image*a.image<b.real*b.real+b.image*b.image;
}
int main(){
    int n;
    scanf("%d",&n);
    priority_queue<complex> queue;
    for (int i = 0; i < n; ++i) {
        char arr[100];
        scanf("%s",arr);
        string string1=arr;
        if(string1=="Pop"){
            if(queue.empty()){
                printf("empty\n");
            }else
            {
                printf("%d+i%d\n",queue.top().real,queue.top().image);
                queue.pop();
                printf("SIZE=%d\n",queue.size());
            }
        }else if(string1=="Insert"){
            int m,n;
            scanf("%d+i%d",&m,&n);
            complex tmp;
            tmp.image=n;
            tmp.real=m;
            queue.push(tmp);
            printf("SIZE=%d\n",queue.size());
        }

    }
}
第二题：哈夫曼树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-41FDCzgk-1679073096810)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317185835751.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FKFtorqq-1679073096811)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317190441992.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RHWAoNe0-1679073096811)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317192613709.png)]

我的题解
#include <cstdio>
#include <queue>
using namespace std;
int main(){
    priority_queue<int> queue;
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        int weight;
        scanf("%d",&weight);
        //用负数来模拟小根堆效果
        queue.push(-weight);
    }
    //放完了开始算权值
    int res=0;
    while(queue.size()>1){
        int weight1=queue.top();
        queue.pop();
        int weight2=queue.top();
        queue.pop();
        //计算带权路径和
        res=res+weight1+weight2;
        queue.push(weight1+weight2);
    }
    printf("%d",-res);
}

巧用map进行查找

第一题：查找学生信息

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vW7slhrg-1679073096811)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230317202716819.png)]

我的题解：
#include <cstdio>
#include <map>
#include <string>
using namespace std;
//创建一个学生对象
struct  Student{
    string name;
    string gender;
    int age;
};
int main(){
    int M;
    scanf("%d",&M);
    map<string,Student> map;
    for (int i = 0; i < M; ++i) {
        char num[30];
        char gender[30];
        char name[30];
        int age;
        scanf("%s%s%s%d",num,gender,name,&age);
        string string1=num;//c转换为cpp风格的字符串
        Student student;
        student.age=age;
        student.name=name;
        student.gender=gender;
        //放入map集合中
        map[string1]=student;
    }
    //查询操作
    int m;
    scanf("%d",&m);
    for (int i = 0; i < m; ++i) {
        char num[30];
        scanf("%s",num);
        string string1=num;
        if(map.find(string1)!=map.end()){
            //说明找到了
            printf("%s %s %s %d\n",string1.c_str(),
                   map[string1].name.c_str(),
                   map[string1].gender.c_str(),
                   map[string1].age);
        } else{
            printf("NO Answer!\n");
        }
    }
}
第二题：魔咒词典

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cPQCIdRe-1679073096811)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318010831971.png)]

我的题解
#include <cstdio>
#include <map>
#include <string>
using namespace  std;
int main(){
    
    map<string,string> map;
    while(true){
    
        char list[300];
        fgets(list,299,stdin);
        string str=list;
        str.pop_back();//去掉换行符
        if(str=="@END@"){
    
            break;
        }
        //读入map
        int pos=str.find(']');
        string word=str.substr(0,pos+1);
        string info=str.substr(pos+2);
        map[word]=info;
        map[info]=word;
    }
    int n;
    scanf("%d",&n);
    getchar();//因为题目中4后面跟了换行符
    for (int i = 0; i < n; ++i) {
    
        char line[200];
        fgets(line,199,stdin);
        string linestr=line;
        linestr.pop_back();
        if(map.find(linestr)!=map.end()){
    
            //说明找到了
            //看看是根据什么找什么
            if(linestr[0]=='['){
    
                //根据魔咒找功能
                printf("%s\n",map[linestr].c_str());
            } else{
    
                //根据功能找魔咒，魔咒要去掉左右中括号
                printf("%s\n", map[linestr].substr(1,linestr.size()-2).c_str());
            }
        }else
        {
    //没找到
            printf("what\n");
        }
    }
}

4天-搜索

广度优先遍历

广度优先搜索是一种基础的图搜索算法，它可以用来解决许多问题，其中最常见的是以下几种： 1. 无权图最短路径问题：在无权图中，从起点到终点的最短路径是什么。 2. 迷宫问题：在一个由通道和墙壁组成的迷宫中，找出从起点到终点的路径。 3. 连通性问题：在一个图中，确定两个节点之间是否存在路径。 4. 可达性问题：在一个图中，确定某个节点是否可以通过另一个节点到达。 5. 遍历问题：在一个图中，访问所有节点。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ItZBXjOA-1679156076260)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318103834485.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VuKBe1YO-1679156076262)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318104704404.png)]

第一题:找牛（广度优先遍历）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DlogXpJ4-1679156076262)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318111852173.png)]

我的题解：
#include <cstdio>
#include <queue>
using namespace std;
struct info{
    int pos;
    int time;
};
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    queue<info> myQueue;
    bool isVisit[100001];
    for (int i = 0; i < 100001; ++i) {
        isVisit[i]= false;
    }
    info first;
    first.pos=n;
    first.time=0;
    myQueue.push(first);
    while(myQueue.empty()!= true){
        info cur=myQueue.front();
        myQueue.pop();
        if(cur.pos==k){
            printf("%d",cur.time);
            break;
        }
        isVisit[cur.pos]=true;
        //加入邻居
        info neighber;
        if(cur.pos-1>0&&cur.pos-1<10000&& isVisit[cur.pos-1]== false){
            neighber.pos=cur.pos-1;
            neighber.time=cur.time+1;
            myQueue.push(neighber);
        }
        if(cur.pos+1>0&&cur.pos+1<10000&& isVisit[cur.pos+1]== false){
            neighber.pos=cur.pos+1;
            neighber.time=cur.time+1;
            myQueue.push(neighber);
        }
        if(cur.pos*2>0&&cur.pos*2<10000&& isVisit[cur.pos*2]== false){
            neighber.pos=cur.pos*2;
            neighber.time=cur.time+1;
            myQueue.push(neighber);
        }
    }
}

第二题：Find the Multiple

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jbrJn3Bb-1679156076263)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318114437270.png)]

我的题解：
#include <cstdio>
#include <queue>
using namespace std;
int main(){
    //广度优先搜索
    int n;
    while(true){
        scanf("%d",&n);
        if(n==0){
            break;
        }
        queue<long long >myQueue;
        myQueue.push(1);
        while(myQueue.empty()== false){
            long long cur=myQueue.front();
            myQueue.pop();
            if(cur%n==0){
                printf("%lld\n",cur);
                break;
            }
            myQueue.push(cur*10);
            myQueue.push(cur*10+1);
        }
    }
}

然后发现超时了，答案是对的这种情况下使用打表

#include <cstdio>
#include <queue>
using namespace std;
int main(){
    //广度优先搜索
    int n=1;
    while(true){
        if(n==201)
            break;
        queue<long long >myQueue;
        myQueue.push(1);
        while(myQueue.empty()== false){
            long long cur=myQueue.front();
            myQueue.pop();
                if (cur % n == 0) {
                    printf("%lld,", cur);
                    break;
                }
            myQueue.push(cur*10);
            myQueue.push(cur*10+1);

        }
        n++;
    }
    printf("\n");
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8eWxZfZb-1679156076263)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318115549813.png)]

输出的数字即从1到200所有的情况

最终解：
int main(){
    long long arr[201]={0,1,10,111,100,10,1110,1001,1000,111111111,10,11,11100,1001,10010,1110,10000,11101,1111111110,11001,100,10101,110,110101,111000,100,10010,1101111111,100100,1101101,1110,111011,100000,111111,111010,10010,11111111100,111,110010,10101,1000,11111,101010,1101101,1100,1111111110,1101010,10011,1110000,1100001,100,100011,100100,100011,11011111110,110,1001000,11001,11011010,11011111,11100,100101,1110110,1111011111,1000000,10010,1111110,1101011,1110100,10000101,10010,10011,111111111000,10001,1110,11100,1100100,1001,101010,10010011,10000,1111111101,111110,101011,1010100,111010,11011010,11010111,11000,11010101,1111111110,1001,11010100,10000011,100110,110010,11100000,11100001,11000010,111111111111111111,100,101,1000110,11100001,1001000,101010,1000110,100010011,110111111100,1001010111,110,111,10010000,1011011,110010,1101010,110110100,10101111111,11111100,11101111,11010110,11011111110,11101000,10001,100001010,110110101,100100,10011,100110,1001,1111111110000,11011010,100010,1100001,11100,110111,11100,1110001,11001000,10111110111,10010,1110110,1010100,10101101011,100100110,100011,100000,11101111,11111111010,1010111,1111100,1111110,1010110,11111011,10101000,10111101,111010,1111011111,110110100,1011001101,110101110,100100,110000,100101111,110101010,11010111,11111111100,1001111,10010,100101,110101000,1110,100000110,1001011,1001100,1010111010111,110010,11101111,111000000,11001,111000010,101010,110000100,1101000101,1111111111111111110,111000011,1000};
    int n;
    while (true){
        scanf("%d",&n);
        if(n==0){
            break;
        } else{
            printf("%lld\n",arr[n]);
        }
    }
}

深度优先遍历

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hTxhry2t-1679156076264)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318124239785.png)]

深度优先遍历（Depth-First Search，简称DFS）是一种常见的遍历图或树的算法。其运用了“回溯法”思想，在搜索过程中尽量先访问子节点，然后再返回到父节点，沿着一条分支一直走到底，直到不能再走为止，然后返回上一个分支继续搜索，直到遍历完整个图或树为止。 深度优先遍历可以使用递归或者栈来实现。递归实现时，每次访问到一个节点，就将其标记为已访问，然后递归遍历其所有未被访问过的邻居节点，直到遍历完所有的连通节点。使用栈实现时，首先把起始节点压入栈中，然后不断弹出栈顶节点，访问该节点并将其未被访问过的邻居节点压入栈中，直到栈为空为止。 深度优先遍历的应用非常广泛，例如最短路径问题、拓扑排序、判断图是否为连通图等问题都可以用深度优先遍历来解决。

第一题：骑士的旅行

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pALeSX5P-1679156076264)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318142340039.png)]

我的题解：
#include <cstdio>
#include <string>
using namespace std;
//可以走的方向
int direction[50][50]={
        {-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}
};
bool Isvisited[50][50];
bool DFS(int x,int y,int cur,int p,int q,string path){
    path+=(y+'A');
    path+=(x+'1');
    Isvisited[x][y]=true;
    if(cur==p*q){
        return true;
    }
    for (int i = 0; i < 8; ++i) {
        if(x+direction[i][0]>=0&&x+direction[i][0]<p&&
        y+direction[i][1]>=0&&y+direction[i][1]<q&&
        Isvisited[x+direction[i][0]][y+direction[i][1]]== false){
            return true;
        }
        //不存在从本届点出发到终点的路径
        Isvisited[x][y]= false;
        path.substr(0,path.size()-2);//把最后两个字符去掉
        return false;
        }
}

int main(){
    int n,p,q;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d",&p,&q);
        printf("Scenario #%d:\n",i+1);
        for (int j = 0; j < p; ++j) {
            for (int k = 0; k < q; ++k) {
                Isvisited[i][j]= false;
            }
        }
        string path;
        if(DFS(0,0,1,p,q,path)== false){
            printf("impossible\n\n");
        }
    }
}

第二题：找正方形

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VuwidS1H-1679156076264)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318145708974.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-B97Kc1pK-1679156076265)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318145723673.png)]

我的题解：
#include <cstdio>
using namespace std;
int m;
int stick[30];
bool issue[30];
bool DFS(int curSide,int curLength,int position,int side){
    //当前已经拼好的边的个数，当前边长度，木棍遍历期待你，边要的长度
    if(curSide==3){
        return true;
    }
    for (int i = position; i <m ; ++i) {
        if(issue[i]==true||curLength+stick[i]>side){
            continue;
        }
        issue[i]= true;
        if(curLength+stick[i]<side){
            if(DFS(curSide,curLength+stick[i],i+1,side)==true){
                return true;}
            }
            else if(curLength+stick[i]==side){
                if(DFS(curSide+1,0,0,side)==true){
                    return true;
                }
            }
        //取回刚刚的木棍
        issue[i]= false;
        }
    return false;
    }
int main(){
    int n;
    scanf("%d",&n);
    int total=0;
    for (int i = 0; i < n; ++i) {
        scanf("%d",&m);
        total+=stick[i];
        issue[i]= false;
    }
    int side;//边长
    if(total%4==0){
        side=total/4;
        if(DFS(0,0,0,side)==true){
            printf("yes\n");
        } else{
            printf("no\n");
        }

    } else{
        printf("no\n");
    }
}

3天-图

图的基础知识

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4WIat7EO-1679156076265)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318150135500.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qZY1G34A-1679156076266)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318150222523.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hSFCcc91-1679156076266)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318150406748.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nNQk9K0e-1679156076266)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318150748105.png)]

#include <cstdio>
#include <vector>
#define N 1000
using namespace std;
struct Edge{
    int y;//这条边对端的编号
    int weight;//这条边的权重
};
vector<Edge> graph[N];//维持了一个长度为n的数组，数组的每一个元素都保存了某个顶点的所有关联边
//insert edge x,y,weight
void addEdge(int x,int y,int weight){
    Edge edge;
    edge.y=y;
    edge.weight=weight;
    graph[x].push_back(edge);
}

并查集相关知识点及其实现

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Pau9potX-1679156076267)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318155012750.png)]

#include <cstdio>
using namespace std;
#define N 1000  //元素上限个数
int  father[N];//存储了每一个元素的父亲的下标
//初始化
void Init(int n){
    //最开始的时候每个元素的父亲都是自己
    for(int i=0;i<n;++i){
        father[i]=i;
    }
}
//查找函数(返回其父亲结点的下标)
int Find(int x){
    if(x!=father[x]){
        //递归向上查找
        return Find(father[x]);
    }
    //x就是树的根
    return father[x];
}
//并查集的合并
void Union(int x,int y){
    //把某个结点的父亲结点的下标直接镰刀另外一个父亲系欸但下标
    father[Find(y)]= Find(x);//将y的父亲结点连到x的父亲结点下面
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cc4pfULT-1679156076267)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318155936118.png)]

路径压缩

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fitqodm0-1679156076267)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318160000533.png)]

//查找的路径压缩
int Findup(int x){
    if(x!=father[x]){
        //递归向上查找的同时，找到祖先之后先不返回，而是设置自己的新父亲
        father[x]= Findup(father[x]);
    }
    return father[x];
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NHDxXl9P-1679156076268)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318161458446.png)]

#include <cstdio>
using namespace std;
#define N 1000  //元素上限个数
int  father[N];//存储了每一个元素的父亲的下标
int height[N];//记录父亲结点到子节点的高度
//初始化
void Init(int n){
    //最开始的时候每个元素的父亲都是自己
    for(int i=0;i<n;++i){
        father[i]=i;
        height[i]=1;
    }
}
//查找函数(返回其父亲结点的下标)
int Find(int x){
    if(x!=father[x]){
        //递归向上查找
        return Find(father[x]);
    }
    //x就是树的根
    return father[x];
}
//查找的路径压缩
int Findup(int x){
    if(x!=father[x]){
        //递归向上查找的同时，找到祖先之后先不返回，而是设置自己的新父亲
        father[x]= Findup(father[x]);
    }
    return father[x];
}
//并查集的合并
void Union(int x,int y){
    //把某个结点的父亲结点的下标直接镰刀另外一个父亲系欸但下标
    father[Find(y)]= Find(x);//将y的父亲结点连到x的父亲结点下面
}
//合并的路径压缩
void UnionUp(int x,int y){
    //小树并入大树
    x= Find(x);//找祖先
    y= Find(y);//找祖先
    if(height[x]<height[y]){
        father[x]=y;
    }
    else if(height[y]>height[x]){
        father[y]=x;
    }else{
//同等高度下合并就无所谓了单数要注意的是合并过去高度要+1
        father[y]=x;
        ++height[x];
    }
}

并查集相关习题-连通图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y7wWhPQN-1679156076268)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318164115982.png)]

我的题解：
#include <cstdio>
using namespace std;
#define N 1000  //元素上限个数
int  father[N];//存储了每一个元素的父亲的下标
int height[N];//记录父亲结点到子节点的高度
//初始化
void Init(int n){
    //最开始的时候每个元素的父亲都是自己
    for(int i=1;i<n;++i){
        father[i]=i;
        height[i]=1;
    }
}
//查找函数(返回其父亲结点的下标)
int Find(int x){
    if(x!=father[x]){
        //递归向上查找
        return Find(father[x]);
    }
    //x就是树的根
    return father[x];
}
//查找的路径压缩
int Findup(int x){
    if(x!=father[x]){
        //递归向上查找的同时，找到祖先之后先不返回，而是设置自己的新父亲
        father[x]= Findup(father[x]);
    }
    return father[x];
}
//并查集的合并
void Union(int x,int y){
    //把某个结点的父亲结点的下标直接镰刀另外一个父亲系欸但下标
    father[Find(y)]= Find(x);//将y的父亲结点连到x的父亲结点下面
}
//合并的路径压缩
void UnionUp(int x,int y,int &num){
    //小树并入大树
    x= Find(x);//找祖先
    y= Find(y);//找祖先
    if(x!=y){
        num--;//合并之后连通子图数量减一
    }
    if(height[x]<height[y]){
        father[x]=y;
    }
    else if(height[y]>height[x]){
        father[y]=x;
    }else{
//同等高度下合并就无所谓了单数要注意的是合并过去高度要+1
        father[y]=x;
        ++height[x];
    }
}

int main(){
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0){
            break;
        }
        Init(n);//初始化有n个顶点的并查集
        //输入m行数据
        int num=n;//初始条件下连通子图的数量
        for (int i = 0; i < m; ++i) {
            int x,y;
            scanf("%d%d",&x,&y);
            UnionUp(x,y,num);
        }
        if(num==1){
            printf("YES\n");
        } else{
            printf("NO\n");
        }
    }
}

最小生成树相关

最小生成树是一个连通无向图的生成树，它的所有边的权值和最小。

生成树是一个无向树，它包含图中的所有顶点，但只有足以构成一棵树的边。

如果一个图本身就是一棵树，则该图的最小生成树就是它本身。

在给定一个带权的连通无向图后，最小生成树问题就是要找到权值和最小的生成树。

最小生成树问题是一种经典的、重要的问题，在许多实际问题的求解中都有应用，例如城市道路规划、电路设计、计算机网络等。 最小生成树问题有很多解法，其中比较常用的是Prim算法和Kruskal算法。

Prim算法是一种贪心算法，以某个顶点为起点，不断扩展已有的生成树，加入一个顶点，就将离它最近的边加入生成树，直到所有顶点都加入为止。

Kruskal算法则是一种基于并查集的贪心算法，首先将所有的边从小到大排序，然后从最小的边开始加入生成树，如果边的两个端点已经在同一个连通分量中，则不加入该边；否则将该边加入生成树，并将两个端点合并到同一个连通分量中。两种算法都能够得到最小生成树。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ozNHMgtb-1679156076268)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318170329848.png)]

Kruskal算法（利用并查集的思想去实现）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bWTHbn1r-1679156076268)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318170314977.png)]

kruskal相关习题-道路习题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g3M0XpXf-1679156076269)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230318173136281.png)]

我的题解
/*
#include <cstdio>
using namespace std;
#define N 1000  //元素上限个数
int  father[N];//存储了每一个元素的父亲的下标
int height[N];//记录父亲结点到子节点的高度
//初始化
void Init(int n){
    //最开始的时候每个元素的父亲都是自己
    for(int i=1;i<n;++i){
        father[i]=i;
        height[i]=1;
    }
}
//查找函数(返回其父亲结点的下标)
int Find(int x){
    if(x!=father[x]){
        //递归向上查找
        return Find(father[x]);
    }
    //x就是树的根
    return father[x];
}
//查找的路径压缩
int Findup(int x){
    if(x!=father[x]){
        //递归向上查找的同时，找到祖先之后先不返回，而是设置自己的新父亲
        father[x]= Findup(father[x]);
    }
    return father[x];
}
//并查集的合并
void Union(int x,int y){
    //把某个结点的父亲结点的下标直接镰刀另外一个父亲系欸但下标
    father[Find(y)]= Find(x);//将y的父亲结点连到x的父亲结点下面
}
//合并的路径压缩
void UnionUp(int x,int y,int &num){
    //小树并入大树
    x= Find(x);//找祖先
    y= Find(y);//找祖先
    if(x!=y){
        num--;//合并之后连通子图数量减一
    }
    if(height[x]<height[y]){
        father[x]=y;
    }
    else if(height[y]>height[x]){
        father[y]=x;
    }else{
//同等高度下合并就无所谓了单数要注意的是合并过去高度要+1
        father[y]=x;
        ++height[x];
    }
}

int main(){
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0){
            break;
        }
        Init(n);//初始化有n个顶点的并查集
        //输入m行数据
        int num=n;//初始条件下连通子图的数量
        for (int i = 0; i < m; ++i) {
            int x,y;
            scanf("%d%d",&x,&y);
            UnionUp(x,y,num);
        }
        if(num==1){
            printf("YES\n");
        } else{
            printf("NO\n");
        }
    }
}*/
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge{
    int x;
    int y;
    int weight;
};
#define N 1000  //元素上限个数
int  father[N];//存储了每一个元素的父亲的下标
int height[N];//记录父亲结点到子节点的高度
//初始化
void Init(int n){
    //最开始的时候每个元素的父亲都是自己
    for(int i=1;i<n;++i){
        father[i]=i;
        height[i]=1;
    }
}
//查找函数(返回其父亲结点的下标)
int Find(int x){
    if(x!=father[x]){
        //递归向上查找
        return Find(father[x]);
    }
    //x就是树的根
    return father[x];
}
//合并的路径压缩
void UnionUp(int x,int y,int weight,int &total){
    //小树并入大树
    x= Find(x);//找祖先
    y= Find(y);//找祖先
    if(x!=y){
        total+=weight;
    }
    if(height[x]<height[y]){
        father[x]=y;
    }
    else if(height[y]>height[x]){
        father[y]=x;
    }else{
//同等高度下合并就无所谓了单数要注意的是合并过去高度要+1
        father[y]=x;
        ++height[x];
    }
}
bool compare(Edge lhs,Edge rhs){
    return lhs.weight<rhs.weight;
}
int main(){
    int n;
    vector<Edge> vec;
    while(scanf("%d",&n)!=EOF){
        if(n==0){
            break;
        }
        Init(n);//初始化
        for (int i = 0; i < n*(n-1)/2; ++i) {
            Edge edge;
            scanf("%d%d%d",&edge.x,&edge.y,&edge.weight);
            vec.push_back(edge);
        }
        //对容器中数据从小到大排序
        sort(vec.begin(),vec.end(), compare);
        int total=0;//权值之和
        for (int i = 0; i < n*(n-1)/2; ++i) {
            UnionUp(vec[i].x,vec[i].y,vec[i].weight,total);
        }
        printf("%d\n",total);
    }
}

最短路径相关
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/m0_49218627/article/details/129483349

智能推荐

【iOS开发】SwiftLint——代码规范工具-程序员宅基地

文章浏览阅读1.1k次。目的包括PMS及以后的Swift项目在多人开发中，即使有官网的规范模板，每个人的代码风格和规范难以做到完全一致，对后期项目维护会增加一定的困难。使用SwiftLint可以对规范代码有很大帮助。SwiftLint是啥SwiftLint是Realm公司开发的一个插件，专门用于管理Swift代码的规范，能够对原有的代码自动格式化，在 Xcode 中执行编译时，SwiftLint 会自动运行检查，不符合规范的代码会通过警告或者报错的形式指示出来，并且拥有丰富的配置项，可以进行大量的自定义规范操作，是一个很方_swiftlint

tomcat 源码阅读步骤一_myeclipse怎么查看tomcat源码-程序员宅基地

文章浏览阅读618次。tomcat源码阅读1org.apache.catalina 包包内接口主要有：AuthenticatorAuthenticator 是一个组件（通常是一个阀门或容器），它提供了这类服务的身份验证Cluster一个Cluster 像一个当地客户服务器集群那样工作，它的实现需要支持集群内的多种交流方式Contained它是一个解耦接_myeclipse怎么查看tomcat源码

[Android]APP多域名服务高可用方案_一个app要连多个域名灾备吗-程序员宅基地

文章浏览阅读2.6k次。负责公司的基础数据扫描采集.这部分对于系统的可用性基本是100%所以做了很多高可用的方案前置准备在对APP进行高可用实施之前,我们需要准备:1.核心域名多个降级[一主多备]最基础的要求,必须!!!能够支持云端下发 & 本地动态切换(蓝-绿发布 & 灰度 & UAT)2.多个CDN每个域名 都使用不同CDN,避免因CDN节点故障导致服务不可用(出现过因CDN节点异常的生产故障)3.多个部署网络机房每个域名 部署在不同地域网络机房(出现过主干线因施工被挖断的生产._一个app要连多个域名灾备吗

Ubuntu U盘只能读取不能写入_ubuntu系统硬盘变只读的原因-程序员宅基地

文章浏览阅读1.4w次。原因是U盘的文件系统损坏，操作系统为了防止进一步毁坏文件系统，而将其设置成了只读。Ubuntu系统下，U盘突然只能读取无法写入。_ubuntu系统硬盘变只读的原因

elasticsearch学习笔记之四（使用logstash导入mysql数据）_logstash unable to get charset-程序员宅基地

文章浏览阅读232次。本文介绍elasticsearch的从mysql导入数据文章目录0. 数据准备1. 下载并安装logstash1.1 下载地址1.2 安装2. 配置文件2.1 下载jdbc包2.2 更改配置文件3. 启动5. 查询0. 数据准备create database shopdbCREATE TABLE `goods` ( `id` int(11) unsigned NOT NULL A..._logstash unable to get charset

盘点 | 2020年「21篇」医学影像算法最佳综述-程序员宅基地

文章浏览阅读1.2k次，点赞3次，收藏23次。点击上方，选择星标或置顶，不定期资源大放送！阅读大概需要15分钟Follow小博主，每天更新前沿干货仅作学术分享，不代表本公众号立场，侵权联系删除转载于：作者丨cynthia yawain..._医学图像分割yolo

随便推点

GIT从指定分支克隆代码_从分支克隆代码-程序员宅基地

文章浏览阅读595次。git clone -b 分支名称 克隆地址_从分支克隆代码

peewee连接mysql中文数据编码_peewee 生成 文件乱码-程序员宅基地

文章浏览阅读8.2k次。系统是win7 x64python 2.7.6的site.py里面编码设定为 utf-8py文件首行指定 #coding:utf-8mysql 5.5.38安装时指定代码为utf-8peewee的连接数据库代码为：db = MySQLDatabase(host = '127.0.0.1', user = 'root', passwd = '1', database = _peewee 生成 文件乱码

RNN/LSTM细节及编程输入输出维度问题、GRU_lstm输出维度和输入维度相同-程序员宅基地

文章浏览阅读3.6k次，点赞2次，收藏12次。为了解决RNN的长时依赖的问题。RNN无法保存较长的时间的信息，因为梯度消失问题。LSTM引入了门控单元的机制，也就是添加了C这条通路，使得可以较长长时间保存信息。LSTM单元（unit）一般由一个细胞（cell）,一个输入门 （inputgate）,一个输出门（outputgate）和一个遗忘门 （forgetgate）组成. •细胞能够记住任意时间间隔上的值，三个门能够控制进出细胞的 信息流动。引入了“门”机制对细胞状态信息进行添加或删除，实现长时记忆。•“门”机制由一个Sigmoid激活函数_lstm输出维度和输入维度相同

YUV是究竟什么意思_yuv格式是什么意思-程序员宅基地

文章浏览阅读3.2k次。(9+条消息)对颜色空间YUV、RGB的理解 - 一条肥鱼的博客 - 程序员宅基地 https://blog.csdn.net/asahinokawa/article/details/80596655YUV（亦称YCrCb）是被欧洲电视系统所采用的一种颜色编码方法（属於PAL）。YUV主要用于优化彩色视频信号的传输，使其向后相容老式黑白电视。与RGB视频信号传输相比，它最大的优点在于只需占..._yuv格式是什么意思

kitti点云地图拼接_semantickitti点云拼接-程序员宅基地

文章浏览阅读3.8k次，点赞5次，收藏32次。文章目录1. 关于kitti数据集以及坐标系2. 关于bin格式点云的存储方式3. 点云拼接前言：这段时间在学习坐标系变换相关的知识，同时尝试了利用kitti公开点云数据集以及对应的真实位姿，拼接出全局地图，如下图所示，我采用了kitti点云数据集的00序列来测试拼接地图。下面大致记录下点云拼接过程以及基于C++和Matlab的拼接代码，备忘。1. 关于kitti数据集以及坐标系kitti数..._semantickitti点云拼接

SpringBoot RabbitMQ 无法连接问题_springboot连不上rabbitmq-程序员宅基地

文章浏览阅读3.7k次。环境Ubuntu除了要配置访问权限以外，还需要将运行环境配置修改下：命令：vi/etc/rabbitmq/rabbitmq-env.conf# Defaults to rabbit. This can be useful if you want to run more than one node# per machine - RABBITMQ_NODENAME shoul..._springboot连不上rabbitmq

推荐文章

热门文章

相关标签