---
title: "总复习"
created: 2025-11-28
tags:
  - 算法
---

# 总复习

## 目标

最后一晚上了 把知识点大概过一遍 盲点或者快忘掉的东西捡一下

## **高精度**

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

//用一个t去接每个位的和 当然前提是俩加数的某位上有
//得到的结果%10存入C的该位 剩下的留到下一位当进位
//如果最后俩加数的某位都没东西了 而t还在 就意味着有一个进位 在C中再进一位
//结果仍是逆序存着的
vector<int> add(vector<int> &A,vector<int> &B){
	vector<int> C;
	int t=0;
	for(int i=0;i<A.size() || i<B.size();i++){
		if(i<A.size())	t+=A[i];
		if(i<B.size())	t+=B[i];
		C.push_back(t%10);
		t/=10;
	}
	if(t)	C.push_back(1);
	return C;
}

//减法需要考虑大减小还是小减大 一律让大的减小的 由题意而定加负号
//所以 得先进行比较
bool cmp(vector<int> &A,vector<int> &B){
	if(A.size()!=B.size())
		return A.size()>B.size();
	for(int i=A.size()-1;i>=0;i--)
		if(A[i]!=B[i])
			return A[i]>B[i];
	return true;
}
//同样用t来存储 每位相减的结果 由于确定了A更大 所以只可能B中某位没有
//减完之后可能为负数（也就是不够减)
//对于不够减的情况 我们会选择借位 也就是+10 不过我们把+10的操作滞后  减完再+10 再%10就是该位结果
//而如果真的不够减了 借了一位的话 就需要把t置为1 让下轮多减去1
vector<int> del(vector<int> &A,vector<int> &B){
	vector<int> C;
	int t=0;
	for(int i=0;i<A.size();i++){
		t=A[i]-t;
		if(i<B.size())
			t-=B[i];
		C.push_back((t+10)%10);
		if(t<0)	t=1;
		else t=0;
	}
	while(C.size()>1 && C.back()==0)
		C.pop_back();
	return C;
}

//这里的乘法不太一样 不是两位两位乘 而是直接用小数作为整体 去与大数的每一位相乘
//用t存储这某位的乘积 同样 模10得到当前位答案 /=10得到下一位的进位
vector<int> mul(vector<int> &A,int c){
	vector<int> C;
	int t=0;
	for(int i=0;i<A.size() || t;i++) {
		if(i<A.size())
			t+=A[i]*c;
		C.push_back(t%10);
		t/=10;
	}
	while(C.size()>1 && C.back()==0)
		C.pop_back();
	return C;
}

// 除法与加减乘不同 它是从高位开始算 按道理是正序存比较好 但是为了统一 这里也是逆序存
// 那么我们就再逆序取出来做运算 就变成从高位开始做了
// 用r表示余数 在除法中 每轮的被除数都是 上轮的余数*10 + 当前位的数 得到的结果是/b 剩下的余数是%b
// 这个性质对于第一位也是适用的 因为r-0 0*10+第一位 仍等于第一位 不影响结果
vector<int> div(vector<int> &A,int b,int &r){
	vector<int> C;
	r=0;
	for(int i=A.size()-1;i>=0;i--){
		r=r*10+A[i];
		C.push_back(r/b);
		r%=b;
	}
	reverse(C.begin(),C.end());
	while(C.size()>1 && C.back()==0)
		C.pop_back();
	return C;
}

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

	string a,b;
	int c;
	vector<int> A,B;
	cin>>a>>b>>c;
	for(int i=a.size()-1;i>=0;i--){
		A.push_back(a[i]-'0');
	}
	for(int i=b.size()-1;i>=0;i--){
		B.push_back(b[i]-'0');
	}

	auto ADD=add(A,B);
	for(int i=ADD.size()-1;i>=0;i--)
		cout<<ADD[i];

	cout<<endl;

	if(cmp(A,B)){
		auto DEL=del(A,B);
		for(int i=DEL.size()-1;i>=0;i--)
			cout<<DEL[i];
	}
	else{
		auto DEL=del(B,A);
		cout<<"-";
		for(int i=DEL.size()-1;i>=0;i--)
			cout<<DEL[i];
	}

	cout<<endl;

	auto MUL=mul(A,c);
	for(int i=MUL.size()-1;i>=0;i--)
		cout<<MUL[i];

	cout<<endl;

	int r=0;
	auto DIV=div(A,c,r);
	for(int i=DIV.size()-1;i>=0;i--)
		cout<<DIV[i];
	cout<<endl<<r<<endl;

	return 0;
 }
```

## \_\_int128

无需读写的情况下 用int128是非常香的

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

#define int __int128

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

	return 0;
 }
```

实在要用 看看记得住这个吗 如果不行就高精度吧

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

#define int __int128

int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}

void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) 	write(x/10);
	putchar(x%10+'0');
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int a=read();
	int b=read();

	int sum=a+b;
	write(sum);

	return 0;
 }
```

## 基础算法篇

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

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

	//基础算法篇

	//二分
	// ----| ---- 找最大 l=mid r=mid-1 mid=l+r+1>>1
	int l=0,r=n;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid))	l=mid;
		else	r=mid-1;
	}
	// ---- |----- 找最小 r=mid l=mid+1 mid=l+r>>1
	int l=0,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))	r=mid;
		else	l=mid+1;
	}

	//双指针 三模型
	//1、 i不断走 j符合条件才走 不走回头路 将n*n降到2n
	//2、 ij对撞 假定排序后求和 i为小端 j为大端 若结果偏大 j动 若结果偏小 i动
	//3、 匹配问题 i一直走 j满足了才走 和1类似
	int i=0;
	for(int j=0;j<m;j++)
		if(i<n && a[i]==b[j])
			i++;
	if(i==n)	cout<<"yes";
	else	cout<<"no";

	//前缀和
	//一维
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	int l,r;cin>>l>>r;
	cout<<s[r]-s[l-1];

	//二维
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
	cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];

	//差分
	//一维
	void insert(int l,int r,int c){
		b[l]+=c;
		b[r+1]-=c;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(i,i,a[i]);
	}
	int T;cin>>T;
	while(T--){
		int l,r,c;cin>>l>>r>>c;
		insert(l,r,c);
	}
	for(int i=1;i<=n;i++)
		b[i]+=b[i-1];

	//二维
	void insert(int x1,int y1,int x2,int y2,int c){
		b[x1][y1]+=c;
		b[x2+1][y1]-=c;
		b[x1][y2+1]-=c;
		b[x2+1][y2+1]+=c;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			insert(i,j,i,j,a[i][j]);
		}
	}
	while(T--){
		int x1,y1,x2,y2,c;cin>>x1>>y1>>x2>>y2>>c;
		insert(x1,y1,x2,y2,c);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
		}
	}

	return 0;
}
```

## 位运算

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

int lowbit(int x){
	return x&-x;
}

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

	//位运算篇
	// ^ 异或 相同为0 不同为1
	int x=1,y=1,z=0;
	cout<<(x^y)<<endl;
	cout<<(x^z)<<endl;

	x=5;

	// & 取某一位 &1取最后一位
	if(x&1) cout<<"奇数"<<endl;

	//lowbit 取最后一位1 配套while 可求有多少个1
	int cnt=0;
	while(x){
		x-=lowbit(x);
		cnt++;
	}
	cout<<cnt<<endl;

	//bitset 将k进制转为二进制存入容器
	bitset<8> bits(7);
	cout<<bits<<endl;
	//主要是方便转为字符串进行操作 具体操作查文档
	cout<<bits.to_string()<<endl;

	return 0;
}
```

## 单调栈/队列

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

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

	//单调栈
	//找每个数 左/右 最近的 小/大于它的数
	//把当前点 当作是单调栈的最值元素
	//以它为基准去剔除栈中不符合条件的数 当踢完之后 栈顶就是答案 再把该数加入栈中
	while(tt && x<=stk[tt])
		tt--;
	//栈顶为答案 进行操作
	stk[++tt]=x;

	//单调栈+二分
	// 找每个数 左右 最远的 小大于它的数
	//不以该点为中心 而是以栈为中心
	//若该点的加入能保持栈的单调性 就说明前面没有比它大或小的数
	//若尝试加入该点 会破坏单调性
	//就说明前面一定有若干元素要大于或小于它 那么就可以借助单调栈的单调性进行二分 找到第一个大于\小于它的数
	//找第一个 显然是用 ---- |----模板 r-mid l=mid+1
	for(int i=1;i<=n;i++){
		if(stk.empty() || a[i]<a[stk.back()]){
			stk.push_back(i);
			ans[i]=i;
		}
		else{
			int l=0,r=stk.size()-1;
			while(l<r){
				int mid=l+r>>1;
				if(a[stk[mid]]<a[i])
					r=mid;
				else
					l=mid+1;
			}
			ans[i]=stk[r];
		}
	}

	//单调队列
	//找窗口最小值 (在队头)
	void get_min(int a[],int b[],int tot,int k)
	{
	    int hh=0,tt=-1;
	    for(int i=0;i<tot;i++)
	    {
	        if(hh<=tt && i-q[hh]>=k)
	            hh++;
	        //求最小 递增区间 若出现向下 出队
	        while(hh<=tt && a[i]<=a[q[tt]])
	            tt--;
	        q[++tt]=i;
	        //当前区间的最大值为队头
	        b[i] = a[q[hh]];
	    }
	}

	//找窗口最大
	void get_max(int a[],int b[],int tot,int k)
	{
	    int hh=0,tt=-1;
	    for(int i=0;i<tot;i++)
	    {
	        if(hh<=tt && i-q[hh]>=k)
	            hh++;
	        //求最大 递减区间 若出现向上 出队
	        while(hh<=tt && a[i]>=a[q[tt]])
	            tt--;
	        q[++tt]=i;
	        //当前区间的最大值为队头
	        b[i] = a[q[hh]];
	    }
	}

	return 0;
}
```

## 串

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

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

	//判断字符是什么
	//isalpha 是不是英文字母 isdigit是不是数字 isupper 是不是大写  toupper/tolower大小写转换

	//数字变字符 +'0'   字符变数字 -'0'
	//int变string to_string
	//string变int  stoi  若过大 就直接用高精度 vector反向存储
	string s="123";
	int num=stoi(s);
	cout<<num;

	//反转 reverse
	reverse(s.begin(),s.end());

	//筛有效字符
	string filter(const string& str) {
	    string res;
	    for (int i = 0; i < str.size(); ++i) {
	        auto c = str[i];
	        if (isalpha(c)) {
	            res += tolower(c);
	            indexes.push_back(i); // 记录当前字符在原始字符串中的位置
	        }
	    }
	    return res;
	}

	//回文串问题
	//中心拓展算法 以每个点为潜在回文中心 向两边拓展 实际是暴力
	typedef pair<int,int> PII;
	PII findLongestPalindrome(const string& s, int left, int right) {
	    while (left >= 0 && right < s.size() && s[left] == s[right]) {
	        left--;
	        right++;
	    }
	    return {left + 1, right - 1};
	}

	main:
		for (int i = 0; i < str.size(); ++i) {
	        auto [left1, right1] = findLongestPalindrome(str, i, i);
	        auto [left2, right2] = findLongestPalindrome(str, i, i + 1);

	        if (right1 - left1 > end - start) {
	            start = left1;
	            end = right1;
	        }
	        if (right2 - left2 > end - start) {
	            start = left2;
	            end = right2;
	        }
	    }

    //回文串还可以用字符串哈希加二分解决
	//字符串哈希是 用131为进制的方式做的
	typedef unsigned long long ULL;
	const int N=2000010,P=131;
	char str[N];
	ULL ho[N],hr[N],p[N];

	ULL find(ULL h[],int l,int r){
	    return h[r]-h[l-1]*p[r-l+1];
	}

    main:
    	int n=strlen(str+1);
        n*=2;
        for(int i=n;i>0;i-=2){
            str[i]=str[i/2];
            str[i-1]='#';
        }

        p[0]=1;
        for(int i=1,j=n;i<=n,j>=1;i++,j--){
            ho[i]=ho[i-1]*P+str[i];
            hr[i]=hr[i-1]*P+str[j];
            p[i]=p[i-1]*P;
        }

        int res=0;
        for(int i=1;i<=n;i++){
            int l=0,r=min(i-1,n-i);
            while(l<r){
                int mid=l+r+1>>1;
                if(find(ho,i-mid,i-1)==find(hr,n-(i+mid)+1,n-(i+1)+1))
                    l=mid;
                else
                    r=mid-1;
            }
            if(isalpha(str[i-r]))
                res=max(res,r+1);
            else
                res=max(res,r);
        }

	//循环同构
	//一个字符串是否可以由另一个字符串循环拼接得到 比较常规的思路是拼接一份 然后在长的里面find短的
	//还有一个思路就是 把两个串都用最小表示法表示出来 如果相等 就说明是可以循环拼接得到的
	#include<bits/stdc++.h>
	using namespace std;

	const int N=2000010;
	char a[N],b[N];
	int n;

	int get_min(char s[]){
	    int i=0,j=1,k;
	    while(i<=n && j<=n)
	    {
	        k=0;
	        while(k<n && s[i+k]==s[j+k])
	            k++;
	        if(k==n)
	            break;
	        if(s[i+k]>s[j+k])
	            i+=k+1;
	        else
	            j+=k+1;
	        if(i==j)
	            j++;
	    }
	    int res=min(i,j);
	    s[res+n]='\0';
	    return res;
	}

	int main()
	{
	    scanf("%s%s",a,b);
	    n=strlen(a);
	    memcpy(a+n,a,n);
	    memcpy(b+n,b,n);

	    int ap=get_min(a),bp=get_min(b);
	    if(strcmp(a+ap,b+bp))
	        puts("No");
	    else
	    {
	        puts("Yes");
	        puts(a+ap);
	    }
	    return 0;
	}

	//字符串哈希 重点熟悉一下
	/*
		用P进制换10进制的方式
		P取经验值 131
		即131进制的数转变成10进制(把字符串当成一个131进制数)
		模上2^{64}
		等价于一个8字节的东西溢出 直接用unsigned long long存
		将本该是问题的溢出巧妙转变成对2^{64}取模
		由此可以处理出所有字符串的一个哈希值
		为了求某一段显然是前缀和问题
		预处理出所有前缀字符串的哈希值的前缀和数组
		求某一段s[r]-s[l]
		发现错了几位 得把前缀（l）部分 左移到与r 的高位匹配位置上去（后几位补0）
		左移一次就是p 左移两位就是p^2
		以此类推 要让l与r对齐 实际上是要左移r-l+1位
		要快速求到p^{r-l+1}
		每一位是乘上一个p的n次方
		可以把p预处理出来
	*/
	#include<bits/stdc++.h>
	using namespace std;

	typedef unsigned long long ULL;
	const int N=100010,P=131;
	char str[N];
	ULL h[N],p[N];
	int n,m;

	ULL get(ULL h[],int l,int r){
	    return h[r]-h[l-1]*p[r-l+1];
	}

	int main()
	{
	    cin>>n>>m;
	    cin>>str+1;
	    p[0]=1;
	    for(int i=1;i<=n;i++){
	        h[i]=h[i-1]*P+str[i];
	        p[i]=p[i-1]*P;
	    }

	    while(m--){
	        int l1,r1,l2,r2;
	        cin>>l1>>r1>>l2>>r2;
	        if(get(h,l1,r1)==get(h,l2,r2))
	            puts("Yes");
	        else
	            puts("No");
	    }
	    return 0;
	}

	return 0;
}
```

## 自定义排序

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

//单关键字排序

struct Interval {

    int start, end;

    // 重载 < 操作符以按结束时间升序排序

    bool operator<(const Interval& rhs) const {

        return end < rhs.end;

    }

};

//多关键字排序

struct Person {

    string name;

    int age;

    // 重载 < 操作符以先按年龄升序排序，再按姓名字典序排序

    bool operator<(const Person& rhs) const {

        if (age != rhs.age)

            return age < rhs.age;

        return name < rhs.name;

    }

};

//优先队列

priority_queue<int> maxHeap;//大根堆

priority_queue<int, vector<int>, greater<int>> minHeap;//小根堆

struct Person {

    string name;

    int age;

    Person(string n, int a) : name(n), age(a) {}

    //基于年龄构建最小堆

    bool operator<(const Person& rhs) const {

        return age > rhs.age;

    }

};

priority_queue<Person> people;

struct Person {

    string name;

    int age;

    Person(string n, int a) : name(n), age(a) {}

};

//基于年龄构建最大堆

struct CompareAge {

    bool operator()(const Person& a, const Person& b) {

        return a.age < b.age; // 较大的年龄优先

    }

};

priority_queue<Person, vector<Person>, CompareAge> people;

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	vector<Interval> intervals = {{1, 4}, {2, 3}, {8, 10}};

	sort(intervals.begin(), intervals.end());

	vector<Person> people = {{"John", 30}, {"Jane", 25}, {"John", 25}};

	sort(people.begin(), people.end());

	return 0;

}
```

## **日期问题**

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

bool is_leap(int y){

	return y%100 && y%4==0 || y%400==0;

}

int get_days(int y,int m){

	return days[m]+(m==2 && is_leap(y));

}

void next_day(int &y,int &m,int &d){

	d++;

	if(d>get_days(y,m)){

		d=1;

		m++;

		if(m>12){

			m=1;

			y++;

		}

	}

}

bool check_date(int y,int m,int d){

	if(m<1 || m>12)	return false;

	if(d<1 || d>get_days(y,m))	return false;

	return true;

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	while ((curYear < 给定年份) ||

	       (curYear == 给定年份 && curMonth < 给定月份) ||

	       (curYear == 给定年份 && curMonth == 给定月份 && curDay < 给定日子)) {

	    // 执行 next_day 操作

	}

	return 0;

 }

拓展 日期差值 用前缀和思想

// 计算从公元1年1月1日到指定日期的总天数

int daysFromStart(int year, int month, int day) {

    int totalDays = 0;

    // 添加之前年份的天数

    for(int y = 1; y < year; y++) {

        totalDays += isLeapYear(y) ? 366 : 365;

    }

    // 添加当前年份的月份天数

    for(int m = 1; m < month; m++) {

        totalDays += days[m];

        if(m == 2 && isLeapYear(year)) {

            totalDays++;

        }

    }

    // 添加当前月份的天数

    totalDays += day;

    return totalDays;

}

int dateDiff=daysFromStart(endYear,endMonth,endDay) - daysFromStart(startYear,startMonth,startDay) + 1;
```

## 数论

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

//判断素数

bool is_prime(int n){

    if(n < 2) return false;

    for(int i = 2;i <= n / i;i ++){

        if(n % i == 0){

            return false;

        }

    }

    return true;

}

// 筛素数

set<int> primes;

void get_primes(int n){

    for(int i=2;i<=n;i++){

        if(!isnot_prime[i]){

            primes.insert(i);

            for(int j=i;j<=n;j+=i)

                isnot_prime[j]=true;

        }

    }

}

//分解质因数

void divide(int x)

{

    for(int i=2;i<=n/i;i++){

	    while(n%i==0){

	        h[i]++,n/=i;

	    }

	}

	if(n>1)

	    h[n]++;//大于sqrt(n) 的质因子 要么没有 要么只有一个

}

//判断约数

set<int> get_divisors(int n){

    set<int> res;

    for(int i=1;i<=n/i;i++){

        if(n%i==0){

            res.insert(i);

            res.insert(n/i);

        }

    }

    return res;

}

//约数个数

unordered_map<int,int> weight;

	for(int i=2;i<=n/i;i++){

	  	while(n%i==0){

	      	weight[i]++;

	      	n/=i;

	  	}

	}

	if(n>1)

	  	weight[n]++;

	for(auto x:weight){

		res=res*(x.second+1);

	}

//约数之和

 unordered_map<int,int> weight;

    for(int i=2;i<=n/i;i++){

        while(n%i==0){

            weight[i]++;

            n/=i;

        }

    }

    if(n>1)

        weight[n]++;

    LL res=1;

    for(auto prime:weight){

        int base=prime.first,index=prime.second;

        LL temp=1,sum=1;

        while(index--){

            temp=temp*base%mod;

            sum=(sum+temp)%mod;

        }

        res=res*sum%mod;

    }

    cout<<res;

//gcd lcm

 	while(b){

        int c=a%b;

        a=b;

        b=c;

    }

    cout<<a<<endl;

//或者

	int gcd(int a,int b){

	    return b?gcd(b,a%b):a;

	}

//另外还有库函数 __gcd

 	cout<<__gcd(a,b)<<endl;

 	//三个数的gcd、lcm

 	gcd(a,b,c)=gcd(gcd(a,b),c);

	lcm(a,b)=(a*b)/gcd(a,b);

	lcm(a,b,c)=lcm(lcm(a,b),c);

//快速幂

long long qmi(long long a,int k,int p){ //注意a要传入long long  a是指数级增长的 容易爆int

    long long res=1%p;  //防止p=1 res=1%1=0 而不是 1

    while(k){

        if(k&1)

           res=res*a%p;

        k>>=1;

        a=a*a%p;   //不传long long 的话 这里用 a=(long long)a*a%p;

    }

    return res;

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	return 0;

 }
```

其余见根据时间复杂度分析算法 以及最近补充的国赛部分内容

---
⬅️ [[树与图的存储|树与图的存储]] 🏠 [[00-冲刺国赛]]