C++刷题

数据结构与算法

[(459条消息) 【C语言】程序运行过程：预处理/编译/汇编/链接_预处理编译汇编链接_慕雪华年的博客-CSDN博客](https://blog.csdn.net/muxuen/article/details/123227200?ops_request_misc=%7B%22request%5Fid%22%3A%22168596052316800182799736%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=168596052316800182799736&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-123227200-null-null.142^v88^control_2,239^v2^insert_chatgpt&utm_term=预处理 编译 汇编 链接&spm=1018.2226.3001.4187)

(443条消息) 保研机试——1基础算法（排序、哈希、模拟（日期、图形、查找、进制、字符串）、递归与分治、贪心）_Yuezero_的博客-CSDN博客

[(425条消息) 数据结构保研面试题整理（自用）_保研数据结构常温问题_乌鸡摸鱼的博客-CSDN博客](https://blog.csdn.net/m0_52571748/article/details/120505195?ops_request_misc=&request_id=&biz_id=102&utm_term=数据结构 保研&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-0-120505195.142^v73^pc_search_v2,201^v4^add_ask,239^v2^insert_chatgpt&spm=1018.2226.3001.4187)

(463条消息) 插入排序–折半插入排序（来一来，看一看，走过路过，不要错过）_老 胡的博客-CSDN博客

P问题、NP问题、NPC问题、NP-hard问题详解 - 知乎 (zhihu.com)

[保研机试整理 - 知乎 (zhihu.com)

什么时候才考虑用二分答案的技巧？
正向求出答案不好入手，求解答案远远没有验证答案简单。

已知前序后序算中序有多少种：

[(441条消息) 二叉树遍历（已知前序和后序遍历，求中序遍历的可能的序列数）_已知二叉树的前序遍历和后序遍历_我要出家当道士的博客-CSDN博客

(462条消息) 堆排序的时间复杂度分析_一只牛_007的博客-CSDN博客

建立索引树：[(462条消息) 2020北航计算机夏令营机试题目个人理解_北航夏令营 机试_四处碰壁嘤嘤怪的博客-CSDN博客](https://blog.csdn.net/Bernie_double/article/details/118190022?ops_request_misc=%7B%22request%5Fid%22%3A%22168715279416800185829257%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=168715279416800185829257&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-5-118190022-null-null.142^v88^control_2,239^v2^insert_chatgpt&utm_term=北航夏令营 机试&spm=1018.2226.3001.4187)

注意

scanf后，用getchar()吃掉回车

表示最大 INT_MAX(climits)

//malloc
int *nums;
nums=(*int)malloc(10*sizeof(int));
//long long int 别用cin cout
long long a;
scanf("%lld",&a);
printf("%lld",a);

scanf还会返回成功输入的变量的个数,因此可判定EOF

Floyd判圈法很吊

1.lower_bound(v.begin(), v.end(), key)-v.begin()返回有序序列中大于等于key的第一个值的位置
2.upper_bound(v.begin(), v.end(), key)-v.begin()返回有序序列中大于key的第一个值的位置
3.lower_bound(v.begin(), v.end(), key, greater())-v.begin()返回有序序列中小于等于key的第一个值的位置
4.upper_bound(v.begin(), v.end(), key, greater())-v.begin()返回有序序列中小于key的第一个值的位置
5.上述四个函数，若无满足条件的值，则返回v.size()

文件操作

freopen("1.in","r",stdin);
freopen("1.out","w",stdout);

一些常用的库

1. algorithm
2. vector
3. map
4. queue
5. iostream
6. string
7. bits/stdc++.h（带上就对了）
8. cmath(sqrt之类的)
9. climits（INT_MAX INT_MIN）

STL内置find()复杂度：
algorithm的find 复杂度是O(n)，对vector，string等 顺序查询。
map::find 和 set::find 复杂度是O(logn)，因为map和set底层都是红黑树。

---

vector:

下面是一些常用的vector方法：

1. push_back：在vector的末尾添加一个元素。

2. pop_back：删除vector末尾的一个元素。

3. size：返回vector中元素的个数。

4. clear：删除vector中所有的元素。

5. empty：判断vector是否为空。

6. at：返回vector中指定位置的元素。

7. front：返回第一个元素。

8. back：返回最后一个元素。

9. erase：删除vector中指定位置的元素。

10. insert：在vector中指定位置插入一个元素或多个元素。

11. resize：改变vector的大小。

12. reserve：为vector预留一定的空间。

    reverse(a.begin(),a.end());

13. swap：交换两个vector中的元素。

14. begin：返回指向vector第一个元素的迭代器。

15. end：返回指向vector最后一个元素之后的迭代器。 这些方法能够满足大部分情况下的需求，可以根据具体的使用场景选择合适的方法进行操作。

要取迭代器的值，直接*指针取值

对于向量(vector)，它是一种支持随机访问的容器，因此可以直接通过下标访问向量中的元素。

vector<int> v = {1, 2, 3, 4, 5};
// 使用auto关键字定义迭代器
for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
}

vector不能直接使用sort函数进行排序，需要传入一个迭代器指定排序的范围。修改代码如下：

sort(v.begin(),v.end(),com);

---

map

以下是C++中map类的常用方法：

1. insert(make_pair<key, value>)：向map中插入一个键值对。

2. erase(key)：删除map中指定键的元素。

3. clear()：清空map中所有元素。

4. size()：返回map中元素的个数。

5. empty()：返回map是否为空。

6. find(key)：查找map中是否存在指定键的元素，如果存在则返回指向该元素的迭代器，否则返回end()迭代器。

   常常和end联合起来用判断找到没。(这个适合动态查找，底层红黑树实现)

7. count(key)：返回指定键在map中出现的次数，如果不存在则返回0或1。

8. begin()：返回指向map第一个元素的迭代器。

9. end()：返回指向map最后一个元素后面的位置的迭代器。

10. operator[]：通过键访问map中的元素，如果键不存在，则自动插入一个新的键值对并返回对应的值。

11. lower_bound(key)：返回第一个大于或等于指定键的元素的迭代器。

12. upper_bound(key)：返回第一个大于指定键的元素的迭代器。

13. equal_range(key)：返回一个pair对象，其中包含lower_bound和upper_bound返回的迭代器。

14. swap(map2)：交换当前map和map2的元素。 C++中的map类是一种关联式容器，用于存储键值对，其中每个键都唯一，并且按照一定的顺序排列。map的底层实现通常是红黑树，因此查找、插入和删除操作的时间复杂度为O(log n)，其中n是map中元素的个数。map类提供了丰富的方法，可以方便地进行键值对的操作，例如插入、删除、查找、排序等。同时，由于map使用键值对来存储数据，因此可以将map看作是一种特殊的数组，其下标为键，对应的值为数组元素。因此，可以通过下标来访问和修改map中的元素。

map<string, int> m = {{"apple", 1}, {"banana", 2}, {"orange", 3}};
// 使用auto关键字定义迭代器
for (auto it = m.begin(); it != m.end(); it++) {
    cout << it->first << ": " << it->second << endl;
}

---

stack

C++ 中的 stack 库提供了以下常用的方法：

• push(elem)：将元素 elem 压入栈顶。
• pop()：弹出栈顶元素。
• top()：返回栈顶元素，但不弹出。
• empty()：判断栈是否为空。
• size()：返回栈中元素的个数。 除此之外，stack 还支持以下操作：
• emplace(args…)：构造一个新元素并将其压入栈顶。
• swap(stack)：交换两个 stack 的元素。
• operator==、operator!=、operator<、operator<=、operator>、operator>=：比较两个 stack 是否相等、不相等、小于、小于等于、大于、大于等于。 具体用法可以参考下面的示例代码

stack元素可以是任何类型。

---

queue

C++中的queue是一种容器适配器，用于实现“先进先出”（FIFO）的数据结构。queue基于deque或list进行实现，提供了一些方法来操作队列，包括入队、出队、获取队首元素、获取队列大小等。以下是queue的常用方法：

1. push(element)：将一个元素加入队列的尾部。
2. pop()：将队列头部的元素弹出，但没有返回值。
3. front()：返回队列头部的元素。
4. top():返回队列头部元素（和front一样）
5. back()：返回队列尾部的元素。
6. empty()：判断队列是否为空。
7. size()：返回队列中元素的个数。 使用queue需要包含头文件，可以通过以下方式创建一个queue对象：

对于队列(queue)，由于它是一种先进先出(FIFO)的数据结构，因此只能通过front()和back()函数来访问队列的头部和尾部元素，而不能直接通过下标访问。如果要使用下标访问队列元素，需要先将队列转换为数组或向量。

---

priority_queue

#include <queue>
//对于基础类型 默认是大顶堆
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;
    

    priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆
    priority_queue<string> b;

对于优先队列，复杂结构类型要重载运算符(436条消息) C++ 运算符重载_c 重载运算符_高祥xiang的博客-CSDN博客

struct complex{
int real;
int imag;
......
bool operator<(Complex c)const{
return real*real+imag*imag<c.real*c.real+c.imag*c.imag;
}
}

注意上面这个const是必须要有的

---

string

C++中的string类是一个封装了字符串操作的类，提供了一系列方法来处理和操作字符串。以下是常用的string类方法：

1. length()：返回字符串的长度。

2. size()：返回字符串的长度。

3. clear()：清空字符串。

4. empty()：判断字符串是否为空。

5. assign(str)：将字符串的值设置为str。

6. assign(str, pos, len)：将字符串的值设置为str中从pos位置开始的长度为len的子串。

7. append(str)：在字符串的末尾添加str。

8. append(str, pos, len)：在字符串的末尾添加str中从pos位置开始的长度为len的子串。

9. push_back(ch)：在字符串的末尾添加一个字符。

10. insert(pos, str)：在字符串的pos位置插入str。

11. erase(pos, len)：删除从pos位置开始长度为len的子串。

    erase(n):删除indexn后面的字符

12. replace(pos, len, str)：替换从pos位置开始长度为len的子串为str。

13. substr(pos, len)：返回从pos位置开始长度为len的子串。

14. find(str)：查找str在字符串中第一次出现的位置，返回该位置的索引值。(找不到就是-1)

15. rfind(str)：查找str在字符串中最后一次出现的位置，返回该位置的索引值。

16. compare(str)：比较字符串和str的大小，返回0（相等）、1（大于）或-1（小于）。 除了以上列举的方法，string类还支持重载运算符，例如+（字符串拼接）、+=（字符串拼接赋值）、==（字符串相等判断）、[]（访问字符串中指定位置的字符）等。string类的使用非常方便，可以像使用普通变量一样对字符串进行赋值、拼接、查找、替换等操作。例如：

注意string s，其s[i]类型为char，char强制类型转换可以这样转换

string(1,s[i])，1表示char长度

s[i]可以直接比较

输入str1,如果str1为空则退出

scanf不会读回车，如果下一行是gets会直接读取缓冲区中的回车，所有会用一个getchar()在中间把缓冲区中的回车抵消掉

stoi(str) 将其转换为整数，注意，如果是”04”,直接变成4

string::npos用于判断结尾（其实找不到直接-1也行）：

//find函数返回 jk 在 s 中的下标位置
	position = s.find("jk");
	// 如果没找到，返回一个特别的标志
	// c++中用npos表示，我这里npos取值是4294967295
	if(position != s.npos)
	{
		cout << "position: " << position << endl;
	}
	else
	{
		cout << "Not found the flag" << endl;
	}

如果输入的字符串有空格，那么用如下代码

getline(cin,str)

可以直接通过下标修改字符

删除字符串内重复字符:

string str="aadfgggh";
//去重复
sort(str.begin(),str.end());
str.erase(unique(str.begin(),str.end()),str.end());  

删除字符串内某个指定字符:

string str="aadfgggh";
str.erase(remove(str.begin(),str.end(),'a'),str.end()); //在容器中, 删除[begin,end)之间的所有值等于'a'的值.

#include<string>
string::erase(begin,end)：删除[begin,end)之间的所有值c

在Find the Smallest Number中，我发现string的超出index一位的位置依然可以访问，但是没有数

---

algorithm

C++标准库中的algorithm库提供了许多常用的算法，这些算法可以用于处理容器中的数据，例如排序、查找、遍历等。以下是algorithm库中常用的方法：

1. sort(first, last, func)：对[first, last)区间内的元素进行升/降序排序（取决于func返回）。
2. reverse(first, last)：对[first, last)区间内的元素进行翻转。
3. find(first, last, val)：在[first, last)区间内查找值为val的元素，返回该元素的迭代器。如果没有找到，返回last。
4. find_if(first, last, pred)：在[first, last)区间内查找满足条件pred的第一个元素，返回该元素的迭代器。如果没有找到，返回last。
5. count(first, last, val)：统计[first, last)区间内值为val的元素个数。
6. count_if(first, last, pred)：统计[first, last)区间内满足条件pred的元素个数。
7. accumulate(first, last, init)：对[first, last)区间内的元素进行累加，初始值为init。
8. max_element(first, last)：返回[first, last)区间内的最大元素的迭代器。
9. min_element(first, last)：返回[first, last)区间内的最小元素的迭代器。
10. unique(first, last)：对[first, last)区间内的元素去重，返回去重后的末尾迭代器。
11. remove(first, last, val)：删除[first, last)区间内值为val的元素，返回删除后的末尾迭代器。
12. remove_if(first, last, pred)：删除[first, last)区间内满足条件pred的元素，返回删除后的末尾迭代器。
13. for_each(first, last, func)：对[first, last)区间内的元素执行操作func。
14. transform(first1, last1, first2, result, op)：将[first1, last1)区间内的元素和[first2, …)区间内的元素进行op操作，并将结果存储到[result, …)区间内。

climits

中定义的常量主要有以下几种：

1. 整数类型的最大值和最小值：INT_MAX、INT_MIN、LONG_MAX、LONG_MIN、SHRT_MAX、SHRT_MIN等等。
2. 字符类型的最大值和最小值：CHAR_MAX、CHAR_MIN、SCHAR_MAX、SCHAR_MIN、UCHAR_MAX等等。
3. 位数相关的常量：CHAR_BIT、INT_BIT、LONG_BIT等等。
4. 其他常量：MB_LEN_MAX表示一个多字节字符的最大长度，FLT_MAX、FLT_MIN、DBL_MAX、DBL_MIN等等表示浮点类型的最大值和最小值。

设置输出精度

设置输出精度为1位小数

cout << fixed << setprecision(1) << ans << endl

设置输出位数

printf(“%02d”,&)

前面补零，两位，不够两位就补零

KMP

KMP 算法详解 - 知乎 (zhihu.com)

(427条消息) 从头到尾彻底理解KMP（2014年8月22日版）_kmp算法难吗是什么级别_v_JULY_v的博客-CSDN博客

//next
void GetNext(char* p,int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1)
	{
		//p[k]表示前缀，p[j]表示后缀
		if (k == -1 || p[j] == p[k]) 
		{
			++k;
			++j;
			next[j] = k;
		}
		else 
		{
			k = next[k];
		}
	}
}

//kmp
int KmpSearch(char* s, char* p)
{
	int i = 0;
	int j = 0;
	int sLen = strlen(s);
	int pLen = strlen(p);
	while (i < sLen && j < pLen)
	{
		//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++    
		if (j == -1 || s[i] == p[j])
		{
			i++;
			j++;
		}
		else
		{
			//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]    
			//next[j]即为j所对应的next值      
			j = next[j];
		}
	}
	if (j == pLen)
		return i - j;
	else
		return -1;
}

动态规划

最大连续子序列

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int dp[1000001];
int nums[1000001];
int main(){
	int N;
	while(cin>>N){
		if (N==EOF)break;
		int maxnum=INT_MIN;
		for (int i=1;i<=N;i++){
			cin>>nums[i];
		}
		dp[1]=nums[1];
		if (N==1){
			cout<<dp[1]<<endl;
			break;
		}
		for (int i=2;i<=N;i++){
			dp[i]=max(nums[i],dp[i-1]+nums[i]);
			maxnum=max(dp[i],maxnum);
		}
		cout<<maxnum<<endl;
		
	}
	return 0;
}
 

最大子矩阵

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

int dp[101];
int matrix[101][101];
int support[101][101];
int arr[101];

int hangmax(int n){
	int maxnum;
	for (int i=1;i<=n;i++){
		dp[i]=max(arr[i],dp[i-1]+arr[i]);
		maxnum=max(maxnum,dp[i]);
	}
	return maxnum;
}

int allmax(int n){
	int maxnum;
	for (int i=1;i<=n;i++){
		for (int j=i;j<=n;j++){
			for (int k=1;k<=n;k++){
				if (i==1){
					arr[k]=support[j][k];
				}else{
					arr[k]=support[j][k]-support[i-1][k];
				}
			}
			maxnum=max(hangmax(n),maxnum);
			
		}
	}
	return maxnum;
}

int main(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin>>matrix[i][j];
			
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (i==1)support[i][j]=matrix[i][j];
			else{
				support[i][j]=matrix[i][j]+support[i-1][j];
			}
		}
	}
	int maxnum;
	maxnum=allmax(n);
	cout<<maxnum<<endl;
	return 0;
	
	
}

最长递增/减序列

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

int dp[26];
int daodan[26];

int countmax(int n){
	int maxnum=0;
	for (int i=1;i<=n;i++){
		dp[i]=1;
	}
	for (int i=2;i<=n;i++){
		for (int j=1;j<i;j++){
			if (daodan[i]<=daodan[j])
			dp[i]=max(1,dp[j]+1);
			maxnum=max(maxnum,dp[i]);
		}
	}
	return maxnum;
}

int main(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>daodan[i];
	}
	int maxnum;
	maxnum=countmax(n);
	cout<<maxnum<<endl;
	return 0;
}

最大上升子序列和（O(N^2)）

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

int dp[1001];
int nums[1001];

int countmax(int n){
	int maxsum;
	for (int i=1;i<=n;i++){
		dp[i]=nums[i];
	}
	for (int i=2;i<=n;i++){
		for (int j=1;j<i;j++){
			if (nums[i]>nums[j])
			dp[i]=max(nums[i],dp[j]+nums[i]);
			maxsum=max(maxsum,dp[i]);
		}
	}
	return maxsum;
}

int main(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>nums[i];
	}
	int maxsum;
	if (n==1){
		cout<<nums[1];
		return 0;
	}
	maxsum=countmax(n);
	cout<<maxsum<<endl;
	return 0;
}

最长公共子序列（LCS）

1
7
3
5
9
4
8
3

(461条消息) 最长公共子序列 (LCS) 详解+例题模板（全）_lxt_Lucia的博客-CSDN博客

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string s1;
string s2;

int countmax(string s1,string s2){
	int length1=s1.size();
	int length2=s2.size();
	int dp[length1][length2];
	for (int i=0;i<length1;i++){
		for (int j=0;j<length2;j++){
			dp[i][j]=0;
		}
	}
	int maxnum=0;
	for (int i=0;i<length1;i++){
		for (int j=0;j<length2;j++){
			if (s1[i]==s2[j]){
				if (i==0||j==0){
					dp[i][j]=1;
				}else{
					dp[i][j]=dp[i-1][j-1]+1;
				}
			}else{
				if (i==0||j==0){
					dp[i][j]=0;
				}else{
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				}
				
			}
			maxnum=max(maxnum,dp[i][j]);
		}
	}
	return maxnum;
}
int main(){
	while(cin>>s1>>s2){
		int maxnum=countmax(s1,s2);
		cout<<maxnum<<endl;
		
	}
	return 0;
}

LIS（Nlogn）

(465条消息) 最长上升子序列 (LIS) 详解+例题模板 (全)_lxt_Lucia的博客-CSDN博客

01背包

#include <iostream>
using namespace std;

struct d{
	int price;
	int score;
};

int main(){
	int C,N;
	while (cin>>C>>N){
		if (C==0&&N==0)break;
		int dp[C+1];
		d deal[N];
		for (int i=0;i<=C;i++){
			dp[i]=0;
		}
		for (int i=0;i<N;i++){
			int price;
			int score;
			cin>>price>>score;
			deal[i].price=price;
			deal[i].score=score;
		}
		for (int i=0;i<N;i++){
			for (int j=C;j>=1;j--){
				if (j>=deal[i].price){
					dp[j]=max(dp[j-deal[i].price]+deal[i].score,dp[j]);
				}			
		}
	}
		cout<<dp[C]<<endl;
		
	}
	return 0;
}

有个背包的变种

(465条消息) 复旦大学2021年计算机学院机试题解_复旦oj_PyKt的博客-CSDN博客

这里是直接顺序的

DFS BFS

排序

归并

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
void merge(int* a, int low, int mid, int hight)  //合并函数
{
	int* b = new int[hight - low + 1];  //用 new 申请一个辅助函数
	int i = low, j = mid + 1, k = 0;    // k为 b 数组的小标
	while (i <= mid && j <= hight)  
	{
		if (a[i] <= a[j])
		{
			b[k++] = a[i++];  //按从小到大存放在 b 数组里面
		}
		else
		{
			b[k++] = a[j++];
		}
	}
	while (i <= mid)  // j 序列结束，将剩余的 i 序列补充在 b 数组中 
	{
		b[k++] = a[i++];
	}
	while (j <= hight)// i 序列结束，将剩余的 j 序列补充在 b 数组中 
	{
		b[k++] = a[j++];
	}
	k = 0;  //从小标为 0 开始传送
	for (int i = low; i <= hight; i++)  //将 b 数组的值传递给数组 a
	{
		a[i] = b[k++];
	}
	delete[]b;     // 辅助数组用完后，将其的空间进行释放（销毁）
}
void mergesort(int* a, int low, int hight) //归并排序
{
	if (low < hight)
	{
		int mid = (low + hight) / 2;
		mergesort(a, low, mid);          //对 a[low,mid]进行排序
		mergesort(a, mid + 1, hight);    //对 a[mid+1,hight]进行排序
		merge(a, low, mid, hight);       //进行合并操作
	}
}
int main()
{
	int n, a[100];
	cout << "请输入数列中的元素个数 n 为：" << endl;
	cin >> n;
	cout << "请依次输入数列中的元素：" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	mergesort(a, 0, n-1);
	cout << "归并排序结果" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

快速幂

const long long m=1e9+7;
long long quickpow(long long a,long long b){
	long long sum=1;
	while(b){
		if(b&1)//与运算，可判断奇偶，详细见注释
		sum=sum*a%m;//取模运算
		a=a*a%m;
		b>>=1;//位运算，右移，相当于除以2
	}
	return sum;
}
 

模拟问题

就是找规律，还行

日期问题

要预处理

最大公因数/最小公倍数

最小公倍数=a*b/c

c为最大公因数

//最大公因数
int biggest(int a,int b){
	return b!=0?biggest(b,a%b):a;
}
//最小公倍数
int smallest(int a, int b){
   	int big=biggest(a,b);
    return a*b/big;
}

素数筛法

#include<iostream>
using namespace std;
int n;

int main(){
	while (cin>>n){

		if (n==0)break;
		if (n==2){
			cout<<-1<<endl;
			continue;
		}
		bool sushu[n+1];
		for (int i=2;i<=n;i++){
			sushu[i]=true;
		}
		for (int i=2;i<=n;i++){
			if (sushu[i]==false)continue;
			for (int j=i;j*i<=n;j++){ //j直接从i开始，提高效率
				if (j*i<n){
					sushu[j*i]=false;
				}
			}
		}
		for (int i=2;i<n;i++){
			if (sushu[i]){
				if (i%10==1){
					cout<<i<<" ";
				}
			}
		
		}
		cout<<endl;
		
	}
	return 0;
}

对于一个数n，其质因数最多只有一个大于其平方根！

矩阵乘法（构造函数）

#include <iostream>
using namespace std;

struct Matrix{
	int matrix[10][10];
	int row;
	int col;
	Matrix(int a,int b):row(a),col(b){}//注意构造函数的写法
};
Matrix Multiply(Matrix a,Matrix b){
	Matrix ans=Matrix(a.row,b.col);
	for (int i=0;i<a.row;i++){
		for (int j=0;j<b.col;j++){
			int temp=0;
			for (int k=0;k<a.col;k++){
				temp+=a.matrix[i][k]*b.matrix[k][j];
			}
			ans.matrix[i][j]=temp;
		}
	}
	return ans;
}

void printMatrix(Matrix m){
	int row=m.row;
	int col=m.col;
	for (int i=0;i<row;i++){
		for (int j=0;j<col;j++){
			if (j!=0){
				cout<<" ";
			}
			cout<<m.matrix[i][j];
		}
		cout<<endl;
	}
}


int main(){
	Matrix a=Matrix(2,3);
	Matrix b=Matrix(3,2);
	for (int i=0;i<2;i++){
		for (int j=0;j<3;j++){
			cin>>a.matrix[i][j];
		}
	}
	for (int i=0;i<3;i++){
		for (int j=0;j<2;j++){
			cin>>b.matrix[i][j];
		}
	}
	Matrix c=Multiply(a,b);
	printMatrix(c);
	return 0;
	
}

高精度

最小生成树

prim算法求最小生成树- CSDN搜索

kruscal

#include <iostream>
#include <queue>
using namespace std;

struct edge{
	int a;
	int b;
	int weight;
	bool operator>(edge c)const{
		return weight>c.weight;
	}
	edge(int q,int w,int e):a(q),b(w),weight(e){}
};

priority_queue<edge,vector<edge>,greater<edge>>edges;
int graph[100];


int find(int x){
	if (graph[x]==-1)return x;
	else{
		int temp;
	temp=find(graph[x]);
	graph[x]=temp;
	return temp;
	}
	
}

int main(){
	int n;
	while (cin>>n){
		if (n==0)break;
		int a,b,weight;
		int num=n*(n-1)/2;
		memset(graph,-1,sizeof(graph));
		for (int i=1;i<=n;i++){
			graph[i]=-1;
		}
		while (num--){
			cin>>a>>b>>weight;
			edge edge1=edge(a,b,weight);
			edges.push(edge1);
		}
		int sum=0;
		int count=0;
		while (!edges.empty()&&count<n-1){
			edge temp=edges.top();
			edges.pop();
			int a=find(temp.a);
			int b=find(temp.b);
			int weight=temp.weight;
			if (a!=b){
				graph[a]=b;
				count++;
				sum+=weight;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}

弗洛伊德

for (int k = 1;k <= n;k ++) { 
 for (int i = 1;i <= n;i ++) { 
 for (int j = 1;j <= n;j ++) { 
 if (ans[i][k] == 无穷 || ans[k][j] == 无穷) continue; 
 if (ans[i][j] == 无穷 || ans[i][k] + ans[k][j] < ans[i][j]) 
 ans[i][j] = ans[i][k] + ans[k][j]; 
 } 
 } 
 } 

迪杰斯特拉

for (int i = 1;i <= n;i ++) { //初始化
 Dis[i] = -1; //所有距离为-1，即不可达
 mark[i] = false; //所有结点不属于集合K
 } 
 Dis[1] = 0; //得到最近的点为结点1,长度为0
 mark[1] = true; //将结点1加入集合K
 int newP = 1; //集合K中新加入的点为结点1 
 for (int i = 1;i < n;i ++) { //循环n-1次,按照最短路径递增的顺序确定其他n-1个点的最短路径长度
 for (int j = 0;j < edge[newP].size();j ++) { //遍历与该新加入集合
K中的结点直接相邻的边
 int t = edge[newP][j].next; //该边的另一个结点
 int c = edge[newP][j].c; //该边的长度
 if (mark[t] == true) continue; //若另一个结点也属于集合K,则跳过
 if (Dis[t] == - 1 || Dis[t] > Dis[newP] + c) //若该结点尚不可
达,或者该结点从新加入的结点经过一条边到达时比以往距离更短
 Dis[t] = Dis[newP] + c; //更新其距离信息
 } 
 int min = 123123123; //最小值初始化为一个大整数,为找最小值做准备
 for (int j = 1;j <= n;j ++) { //遍历所有结点
 if (mark[j] == true) continue; //若其属于集合K则跳过
 if (Dis[j] == -1) continue; //若该结点仍不可达则跳过
 if (Dis[j] < min) { //若该结点经由结点1至集合K中的某点在经过一条
边到达时距离小于当前最小值
 min = Dis[j]; //更新其为最小值
 newP = j; //新加入的点暂定为该点
 }

欧拉回路（hierholzer）

(462条消息) 欧拉回路（hierholzer算法）_逐步插入回路法_run around的博客-CSDN博客

关键路径（AOE网）

最早开始时间=最晚开始时间

用拓扑图

最早开始时间（所有先序活动的最晚完成时间）

最晚开始时间（所有后续活动的最早开始时间减去该活动花费的时间）

注意源点的最早开始时间不一定为0，要初始化

汇点的最晚开始时间初始化为totalTime-该汇点任务的时间

非汇点的最晚开始时间为无穷

如果只是要求关键路径的长度，其实在earliest[i]初始化的时候就设置为任务的时间就行，但如果要算其他的，就还是设置为0

7 5
11 20 17 10 11 17 17
5 4
6 1
7 3
2 4
2 1

#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#define yushu 1e9+7
using namespace std;

queue<int>zero;
vector<int>re;
struct edge{
	int to;
	int weight;
};
int in[100001];
vector<edge>edges[100001];
int task[100001];
int earliest[100001];
int latest[100001];

int max(int a,int b){
	return a>b?a:b;
}
int min(int a,int b){
	return a<b?a:b;
}

int main(){
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		in[i]=0;
		cin>>task[i];
	}
	int num=m;
	int allTime=0;
	cout<<"input edge"<<endl;
	while (num--){
		int a,b;
		cin>>a>>b;
		in[b]++;
		edge temp;
		temp.to=b;
		temp.weight=task[b];
		edges[a].push_back(temp);
	}
	cout<<"input finished."<<endl;
	for (int i=1;i<=n;i++){
		cout<<"earliest["<<i<<"]:"<<earliest[i]<<endl;
		if (in[i]==0){
			zero.push(i);


		}
	}
	while (!zero.empty()){
		int node=zero.front();
		cout<<"zero:"<<node<<endl;
		zero.pop();
		re.push_back(node);
		for (int i=0;i<edges[node].size();i++){
			int to=edges[node][i].to;
			int weight=edges[node][i].weight;
			cout<<"edge:"<<node<<"-"<<to<<":"<<weight<<endl;
			earliest[to]=max(earliest[to],earliest[node]+task[node]);
			cout<<"earliest["<<to<<"]:"<<earliest[to]<<endl;
			in[to]--;
			if (in[to]==0){
				zero.push(to);
			}
		}
	}
	for (int i=1;i<=n;i++){
		allTime=max(allTime,earliest[i]+task[i]);
	}
	cout<<"reverse:"<<endl;
	for (int i=re.size()-1;i>=0;i--){
		int u=re[i];
		if (edges[u].size()==0){
			latest[u]=allTime-task[u];
			cout<<"latest:["<<u<<"]:"<<latest[u]<<endl;
		}else{
			latest[u]=99999999;
		
		}
		for (int j=0;j<edges[u].size();j++){
			int to=edges[u][j].to;
			int weight=edges[u][j].weight;
			latest[u]=min(latest[u],latest[to]-task[u]);
			cout<<"latest:["<<u<<"]:"<<latest[u]<<endl;
		}
	
	}
	
	cout<<endl;
	for (int i=1;i<=n;i++){
			cout<<"earliest["<<i<<"]:"<<earliest[i]<<endl;
			cout<<"latest["<<i<<"]:"<<latest[i]<<endl;
	}
	

	int sum=1;

	for (int i=1;i<=n;i++){
		sum*=(latest[i]-earliest[i]+1);
	}
	cout<<allTime<<endl;
	cout<<sum<<endl;
	return 0;
	
	
}

(466条消息) AOE问题总结_DrCrypto的博客-CSDN博客

(466条消息) AOE网关键路径求解例题_关键路径例题图解_HardyDragon_CC的博客-CSDN博客

数位dp

(443条消息) 2019年南京大学计算机考研复试机试真题_南大计算机专业考研机试_yc_cy1999的博客-CSDN博客

一个整数可以变为多少个整数相加

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];//存所有状态
int main()
{
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i ++)
        for(int j = i; j <= n; j ++)//j是容量
            f[j] = (f[j] + f[j - i]) % mod;
    cout << f[n] << endl;
    return 0;
}

状压DP

(462条消息) 291. 蒙德里安的梦想（状压dp）_seez的博客-CSDN博客

[(462条消息) 状压dp] 蒙德里安的梦想(模板题+状压dp)_状压dp模板题_Ypuyu的博客-CSDN博客

(462条消息) C++笔试题模版汇总(五)动态规划/贪心_c++笔试题 考动态规划么_ai_XZP_master的博客-CSDN博客

状态压缩DP学习总结+经典例题精解_状压dp-CSDN博客

汉诺塔问题

结论：把i个盘子移到另一个柱面上，需要2^i-1步

关于汉诺塔问题 - 知乎 (zhihu.com)

放置街灯（Placing Lampposts, UVa 10859）:star:

经典贪心

(450条消息) UVA-10382经典贪心问题，区间覆盖_uva 10382_KXL5180的博客-CSDN博客

//酸奶工程
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//定义long long，防止爆int
ll n,s;
ll c[10010],y[10010];//存储费用和交互数量
ll f[10010];
ll sum=0;
int main(){
    scanf("%lld%lld",&n,&s);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&c[i],&y[i]);
    }
    for(int i=1;i<=n;i++){
        if(i==1){
            f[i]=c[i];
        }
        else{
            f[i]=min(c[i],f[i-1]+s);
        }
        sum=sum+f[i]*y[i];
    }
    printf("%lld",sum);
}

跳跃问题

(462条消息) Leetcode——跳跃问题II_跳跃问题2_Purple.’’的博客-CSDN博客

分发糖果

(462条消息) 「leetcode」135.分发糖果【贪心算法】详细图解_代码随想录的博客-CSDN博客

线段树

(462条消息) 线段树 从入门到进阶（超清晰，简单易懂）_线段树进阶_繁凡さん的博客-CSDN博客

匈牙利算法

(462条消息) 匈牙利算法详解_Amelie_xiao的博客-CSDN博客

一个二分图中的最大匹配数等于这个图中的最小点覆盖数

int M, N;            //M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN];         //记录当前右侧元素所对应的左侧元素
bool vis[MAXN];      //记录右侧元素是否已被访问过
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
        if (Map[i][j] && !vis[j]) //有边且未访问
        {
            vis[j] = true;                 //记录状态为访问过
            if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;    //当前左侧元素成为当前右侧元素的新匹配
                return true; //返回匹配成功
            }
        }
    return false; //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}

回溯

[(462条消息) 2018南京大学计算机夏令营机试第二题（回溯）_只会写臭虫的博客-CSDN博客](https://blog.csdn.net/weixin_43175029/article/details/94670710?ops_request_misc=&request_id=&biz_id=102&utm_term=Missing number Given a positi&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-0-94670710.142^v88^control_2,239^v2^insert_chatgpt&spm=1018.2226.3001.4187)

回溯就是dfs，并且在每次dfs时记得恢复原状态；如果只需要输出一种状态，设置flag标志位

N皇后

#include <iostream>
using namespace std;
const int N = 20; 
 
// bool数组用来判断搜索的下一个位置是否可行
// col列，dg对角线，udg反对角线
// g[N][N]用来存路径
 
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
 
void dfs(int u) {
    // u == n 表示已经搜了n行，故输出这条路径
    if (u == n) {
        for (int i = 0; i < n; i ++ ) puts(g[i]);   // 等价于cout << g[i] << endl;
        puts("");  // 换行
        return;
    }
 
    // 枚举u这一行，搜索合法的列
    int x = u;
    for (int y = 0; y < n; y ++ )
        // 剪枝(对于不满足要求的点，不再继续往下搜索)  
        // 这里y-x+n是左上角到右下角,y+x是左下角到右上角
        if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) {
            col[y] = dg[y - x + n] = udg[y + x] = true;
            g[x][y] = 'Q';
            dfs(x + 1);
            g[x][y] = '.';  // 恢复现场
            col[y] = dg[y - x + n] = udg[y + x] = false;
        }
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';
 
    dfs(0);
 
    return 0;
}   
 

建立索引树

[(462条消息) 2020北航计算机夏令营机试题目个人理解_北航夏令营 机试_四处碰壁嘤嘤怪的博客-CSDN博客](https://blog.csdn.net/Bernie_double/article/details/118190022?ops_request_misc=%7B%22request%5Fid%22%3A%22168715279416800185829257%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=168715279416800185829257&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-5-118190022-null-null.142^v88^control_2,239^v2^insert_chatgpt&utm_term=北航夏令营 机试&spm=1018.2226.3001.4187)

注意 建树不一定要指针，数组也可

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0