机式指南 - OpticHong

机式重点永远是树结构、图结构以及动态规划！！！

夏令营经典题型

结构体排序问题

这类问题往往都是一个模板，即待排序的数据都是结构体，排序规则涉及到结构体中的多个元素。

其中，结构体的构造部分尽可能使用struct而不是用class（这是因为，算法题中一般都只是涉及到“组织”的问题，因此完全不需要使用对“封装、继承”等相对完善的class）。

此外，排序规则需要构建一个返回值为bool，传递两个结构体元素的比较函数bool cmp(Elem e1,Elem e2)，具体函数内的返回规则需要根据题目所给的判断逻辑进行编写。

#include <bits/stdc++.h>
using namespace std;
cosnt int N =1e5+10;
struct Elem{
	string str;// 如果不支持c++，则需要改成字符数组 char str[30];此外进行字符串比较时，需要利用strcmp(s1,s2)进行比较。
  int age;
  double socre;
}Stu[N];

bool cmp(Elem e1, Elem e2){
  if(e1.socre != e2.socre) return e1.socre < e2.socre;//这是升序排列
  else if(e1.str != e2.str) return e1.str < e2.str;
  else return e1.age < e2.age;
}

int main(){
  //首先是输入逻辑部分，对结构体进行填充。
  int n;
  cin>>n;
  for(int i=0;i<n;i++) cin>>Stu[i].str>>Stu[i].age>>Stu[i].socre;
  //对结构体中的数据，利用内置函数sort进行排序。
  sort(Stu,Stu+n,cmp);
  //最后根据题目所给要求进行输出。
  cout<<Stu[0].str<<Stu[0].age<<Stu[0].score;
  return 0;
}

# 定义结构体类
class Elem:
    def __init__(self, name, age, score):
        self.name = name
        self.age = age
        self.score = score

# 自定义比较函数
def cmp(elem):
    # 按照分数升序排列，如果分数相同，则按照名字升序排列，再按照年龄升序排列
    return (elem.score, elem.name, elem.age)

###
在 Python 中，sort 和 sorted 函数支持通过 key 参数指定排序规则，而 key 参数需要传入一个函数，该函数会对每个元素进行处理，返回一个可以比较的值（如数字或元组）。根据这个返回值，Python 会对所有元素进行排序。
###

def main():
    # 输入数据
    n = int(input())
    students = []
    for _ in range(n):
        name, age, score = input().split()  
        age = int(age)
        score = float(score)
        students.append(Elem(name, age, score))
    
    # 对数据进行排序
    students.sort(key=cmp)  #默认是整体升序排列，如果需要整体降序，参数reverse可以置为True。如果排序中的某一非数值属性需要降序，则将字符串进行反转[::-1]，数值属性需要降序直接加负号即可。如果需要按照字符串第一个字符进行排序可以使用ord()函数。
    
    # 输出第一个学生的信息
    print(students[0].name, students[0].age, students[0].score)

if __name__ == "__main__":
    main()

注意事项

这种题目的变体，多集中在模板中最关键的两步，即是否待排序的元素需要构建结构体，以及需要构建多个排序规则。

是否需要构建结构体？
当涉及到待排序元素有多个属性时，这个时候毫无疑问构建结构体是一种不错的结果方案；
但是，待排序元素就只用单一属性时，这个时候也可能需要构建结构体。此时，我们需要明白构建结构体的目的是为了更方便的排序，是因为但从其自身的属性上已经不好进行快速比较时，才将比较的逻辑单独抽离出来。比如说，字符串的排序，但排序的逻辑不再是字符串的字典序，而是其字符串的长度。
构建多个排序规则。
多个和单个排序规则本质上没有太大区别。注意到题目中如果有多种情况需要利用到不同的排序规则时，在代码中需要使用case进行实现。

日期类问题

这类问题往往属于模拟的大类，其最明显的特点就是没有难以理解的算法，更多的是进行模拟。

其中涉及到的知识点有：闰年判断、1年1月1日为星期一

额外需要注意的就是这几个周期和月份单词的拼写。

间隔时间

#include <bits/stdc++.h>
using namespace std;
int date[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}}; //首先定义每月天数，将闰月年区分开来，方便后面判断完闰年后的月份天数确定。
bool isLeap(int year){ //判断闰年的函数，被400整除或者被4整除但不被100整除
  return ((year%4==0)&&(year%100!=0)) || (year%400==0);
}

int main(){
  int time1,time2,y1,y2,m1,m2,d1,d2;
  while(cin>>time1>>time2){
    if(time1>time2){int tmp=time2;time2=time1;time1=time2;}
    //需要前面的数字就用除，需要后面的数字就用模
    y1=time1/10000,m1=time1%10000/100,d1=time1%100;
    y2=time2/10000,m2=time2%10000/100,d2=time2%100;
    int sum=1;
    while(y1<y2 || m1<m2 || d1<d2){ //使用天数累加的方式进行模拟
      d1++;
      if(d1==date[isLeap(y1)][m1]+1){m1++;d1=1;}
      if(m1==13){y1++;m1=1;}
      sum++;
    }
    cout<<sum<<endl;
  }
  return 0;
}

date=[
    [0,31,28,31,30,31,30,31,31,30,31,30,31],
    [0,31,29,31,30,31,30,31,31,30,31,30,31]
]
def is_leap(year):
    return (year%4==0 and year%100!=0) or year%400==0

def main():
    sum_date=1
    while True:
        try:
            time1,time2=map(int,input().split())
            if time1>time2:
                time1,time2=time2,time1
            year1,month1,day1=time1//10000,time1%10000//100,time1%100
            year2,month2,day2=time2//10000,time2%10000//100,time2%100
            while year1<year2 or month1<month2 or day1<day2:
                day1+=1
                if day1==date[is_leap(year1)][month1]+1:
                    day1=1
                    month1+=1
                if month1==13:
                    month1=1
                    year1+=1
                sum_date+=1
            print(sum_date)
        except:
            break
                
main() 

判断星期

#include <bits/stdc++.h>
using namespace std;
bool isleap(int y) { return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0; }
int m[2][13] = {{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
                {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
string week[7] = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
string mouth[13] = {"","January","February","March","April","May","June","July","August","September","October","November","December"};
int main() {
  int d2, m2, y2, d1 = 1, m1 = 1, y1 = 1;
  string mm;
  cin >> d2 >> mm >> y2;
  for (int i = 1; i <= 12; i++)
    if (mm == mouth[i]) {m2 = i;break;}
  int sum = 1;
  while (d1 < d2 || m1 < m2 || y1 < y2) {
    d1++;
    if (d1 == m[isleap(y1)][m1] + 1) {d1 = 1;m1++;}
    if (m1 == 13) {m1 = 1;y1++;}
    sum++;
  }
  cout << week[sum % 7] << endl;
  return 0;
}

C/C++快速入门

绝对值在$10^9$范围以内的整数都可以定义为int型。其他情况，使用typedef long long ll;类型，以及unsigned long long (ull)类型。
const int INF=0x3fffffff;
cout<<fixed<<setw(7)<<setprecision(2)<<x<<endl;设置输出x的宽度为7，其中小数部分占2位。
浮点数比较大小：
const double eps=1e-8;
等于：#define equ(a,b) fabs(a-b)<eps
大于：#define more(a,b) (a-b)>eps
小于：#define less(a,b) (a-b)<-eps
大于等于：#define more_eq(a,b) (a-b)>-eps
小于等于：#define less_eq(a,b) (a-b)<eps
π值：const double pi=acos(-1.0);
如果两个操作数都是整数类型（例如 int、long、long long 等），则进行的是整数除法，结果将是一个整数，并且会向下取整（截断小数部分）。
在C语言中，scanf("%s", str1)用于从标准输入中读取一个字符串，并将其存储到字符数组str1中。然而，scanf函数在读取字符串后会在缓冲区中留下一个换行符（’\n’），这可能会导致后续的输入函数（如fgets或另一个scanf）出现问题。为了解决这个问题，可以在scanf之后添加一个getchar()函数调用，以读取并消耗掉缓冲区中的换行符。这样可以确保下一个输入函数从清空了缓冲区的状态开始读取。
大规模输入输出时，不要用cin和cout，否则时间真的会超限！
long long 和int不要混用！

mex(arr) 表示数组arr中末出现过的最小非负整数。例如[0,1,2,4]的mex为3。

int mex(const vector<int>& arr) {
    unordered_set<int> s(arr.begin(), arr.end());
    int mex = 0;
    while (s.count(mex)) mex++;
    return mex;
}

Python快速入门

Python构建二维数组的方法：[[0] * (n + 1) for _ in range(m + 1)]，这样构建的二维数组，在修改任意元素时不会造成其他位置的元素被修改。

Python的排序函数：sorted()，可用于对任何可迭代对象（如列表、元组、字符串等）进行排序。sorted()返回排序后的新列表，不会改变原列表。

numbers = [5, 2, 9, 1, 5, 6]
sorted_numbers = sorted(numbers)
print(sorted_numbers)  # 输出：[1, 2, 5, 5, 6, 9]
print(numbers)         # 输出：[5, 2, 9, 1, 5, 6]（原列表未改变）

此外，list.sort()可以实现就地排序。

numbers = [5, 2, 9, 1, 5, 6]
numbers.sort()
print(numbers)  # 输出：[1, 2, 5, 5, 6, 9]

Python获取子字符串只需要通过切片就行。字符串的拼接和复制也只需通过简单的数学运算符+和*实现。

入门模拟

日期计算

有两个日期，求两个日期之间的天数，如果两个日期是连续的，则规定它们之间的天数为两天。

#include <iostream>
using namespace std;
int date[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};
bool isLeap(int year){
  return ((year%4==0)&&(year%100!=0)) || (year%400==0);
}
int main(){
  int time1,time2,y1,y2,m1,m2,d1,d2;
  while(cin>>time1>>time2){
    if(time1>time2){int tmp=time2;time2=time1;time1=time2;}
    //需要前面的数字就用除，需要后面的数字就用模
    y1=time1/10000,m1=time1%10000/100,d1=time1%100;
    y2=time2/10000,m2=time2%10000/100,d2=time2%100;
    int sum=1;
    while(y1<y2 || m1<m2 || d1<d2){
      d1++;
      if(d1==date[isLeap(y1)][m1]+1){m1++;d1=1;}
      if(m1==13){y1++;m1=1;}
      sum++;
    }
    cout<<sum<<endl;
  }
  return 0;
}

由日期换算成星期时，也是需要用两日期的差值进行计算的。记1年1月1日为星期一，创建周期数组（注意第一个值为Sunday）：

string week[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};

进制转换

两种非十进制需要借助十进制进行转换。如果涉及到小数，只能用字符串存储，然后根据整数部分除基取余和根据小数部分乘基取整完成运算。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char alpha[6]={'A','B','C','D','E','F'};
int main(){
    int a,b;char n[80];
    while(scanf("%d%s%d",&a,n,&b)!=EOF){
        ll res_10=0; int len=strlen(n);
        for(int i=0;i<len;i++) res_10 = res_10*a + (n[i]<='9'? n[i]-'0': n[i]<='F'? n[i]-'A'+10: n[i]-'a' + 10);
        if(b==10) cout<<res_10<<endl;
        else{
            char res_b[80]; int cnt=0;
            memset(res_b,0,sizeof(res_b));
            do{
                res_b[cnt++]= res_10%b <= 9 ?res_10%b + '0': alpha[res_10%b-10];
                res_10/=b;
            }while(res_10);
            for(int i=cnt-1;i>=0;i--) cout<<res_b[i];
            cout<<endl;
        }
        memset(n,0,sizeof(n));
    }
    return 0;
}

当需要转换的是“大数”时，就应该仔细地去分析进制转换的具体实现细节！

#include <bits/stdc++.h>
using namespace std;
char str1[37],str2[37],str3[100010];
//其中str1用来存储被除数，str2用来存储除数，str3用来存储二进制结果。
bool isEmpty(char str[]){
    int len=strlen(str);
    for(int i=0;i<len;i++) if(str[i]!='0') return false;
    return true;
}
int main(){
    while(scanf("%s",str1)!=EOF){
        int idx1=0,idx2=0,len=strlen(str1);
        do{
            int num=0;
            while(idx1<len){
                num=num*10+str1[idx1]-'0';
                str2[idx1++]=num/2 + '0';
                num%=2;
            }
            str3[idx2++]=num + '0';
            for(int i=0;i<=len;i++) if(str2[i]){idx1=i;break;}
            memset(str1,0,sizeof(str1));
            strcpy(str1, str2);  //交换被除数和除数
            memset(str2,0,sizeof(str2));
        }while(!isEmpty(str1));
        int len1=strlen(str3);
        for(int i=len1-1;i>=0;i--) cout<<str3[i];
        cout<<endl;
        memset(str3,0,sizeof(str3));
    }
  	return 0;
}

[!caution]
这段代码对10进制以下的进制都是通用的，只需要把最里层while循环中的两个‘2’换成所需要转换的进制数即可。
当然对于11-16进制，只需要再添加一个char alpha[6]={'A','B','C','D','E','F'};这样的aplha转换表即可。

字符串转数值

这是一类经典的题目，不要再单独写一个函数用来str_to_int了

“123456789”转成对应的数值其实相当方便：

int sum=0,len=strlen(str);
for(int i=0;i<len;i++)
  sum=sum*10+str[i]-'0';

而数值转字符串就更加方便了：

int num=123456789;
char str[20];
sprintf(str,"%d",num);

数学知识

质数

质数的判定

时间复杂度为$O(\sqrt 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;
}

def is_prime(n):
    if n<2: return False
    i=2
    while i*i <=n:
        if n%i==0: return False
        i+=1
    return True

分解质因子

时间复杂度为$O(logn\sim \sqrt n)$

void divide(int n){
  	for(int i=2;i<=n/i;i++){
      	if(n%i==0) {
          	int s=0;
          	while(n%i==0){
              	n/=i; s++;
            }
          	printf("%d %d\n",i,s);
        }
    }
  	if(n>1) printf("%d %d\n",n,1);
}

def divide(n):
    i=2
    while i*i <=n:
        if n%i==0:
            s=0
            while n%i==0:
                n//=i
                s+=1
            print(i,s)
        i+=1
    if n>1: print(n,1)

埃氏筛

时间复杂度$O(nloglogn)$

const int N=1e5+10;
int primes[N],cnt;
bool st[N];
void get_primes(int n){
  	for(int i=2;i<=n;i++){
      	if(!st[i]){
          	primes[cnt++]=n;
          	for(int j=2*i;j<=n;j+=i) st[j]=true;
        }
    }
}

欧拉筛

时间复杂度$O(n)$，每个数只会被其最小质因子筛掉。

const int N=1e5+10;
int primes[N],cnt;
bool st[N];
void get_primes(int n){
  	for(int i=2;i<=n;i++){
      	if(!st[i]) primes[cnt++]=i;
      	for(int j=0;primes[j]<=n/i;j++){
          	st[primes[j]*i]=true;
          	if(i%primes[j]==0) break;
        }
    }
}

约数

分解约数

vector<int> get_divisors(int n){
  	vector<int> res;
  	for(int i=1;i<=n/i;i++){
      	if(n%i==0){
          	res.push_back(i);
          	if(i!=n/i) res.push_back(n/i);
        }
    }
  	sort(res.begin(),res.end());
  	return res;
}

约数个数

约数之和

最大公约数

int gcd(int a,int b){
  	return b ? gcd(b,a%b) : a;
}

算法初步

排序

冒泡排序

冒泡排序通过多次比较和交换相邻元素的方式将待排序的数据按照升序或降序进行排序。时间复杂度：$O(n^2)$。

void BubbleSort(int arr[],int len){
    for(int i=1;i<len;i++)
        for(int j=0;j<i;j++)
            if(arr[j]>arr[j+1]){int tmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;}
}

选择排序

选择排序将待排序的数据序列分为已排序部分和未排序部分，每次从未排序部分选择最小（或最大）的元素，将其放置在已排序部分的末尾，直到整个序列排序完成。时间复杂度：$O(n^2)$。

void SelectionSort(int arr[],int len){
    for(int i=0;i<len;i++){
        int idx=i;
        for(int j=idx+1;j<len;j++) if(arr[j]<arr[idx]) idx=j;
        int tmp=arr[idx]; arr[idx]=arr[i]; arr[i]=tmp;
    }
}

直接插入排序

插入排序将待排序的数据序列分为已排序部分和未排序部分，每次从未排序部分选择一个元素插入到已排序部分的合适位置，直到整个序列排序完成。时间复杂度：$O(n^2)$。

void InsertionSort(int arr[],int len){
    for(int i=1;i<len;i++){
        int idx=0;
        while(idx<= i){if(arr[i]<arr[idx]){int tmp=arr[i];arr[i]=arr[idx];arr[idx]=tmp;}idx++;}
    }
}

希尔排序

希尔排序（Shell Sort）是一种基于插入排序的排序算法，旨在提高插入排序在大规模数据集上的效率。它通过比较距离较远的元素来进行排序，从而减少了数据移动的次数。

分组排序：
- 将整个待排序的数组按照一定的增量（gap）分成若干个子序列，对每个子序列分别进行插入排序。
- 初始的增量较大，随着算法的进行逐渐减小，直到增量为1，此时整个数组被当作一个子序列进行插入排序。
增量序列：
- 增量序列的选择对希尔排序的性能有很大影响。常用的增量序列有希尔增量（gap = n/2, n/4, …, 1）、Hibbard增量（1, 3, 7, 15, …）等。
- 理想的增量序列可以减少比较次数和移动次数，从而提高排序效率。
排序过程：
- 初始时选择一个较大的增量，将数组元素分组。
- 对每个分组内的元素进行插入排序。
- 减小增量，重复上述步骤，直到增量为1。

快速排序

快速排序是通过分治的策略将一个大问题分解为多个子问题，然后逐步解决子问题，最终达到整体问题的解决。

快速排序的基本思想可以概括为以下几个步骤：

选择一个基准元素：从待排序的数组中选择一个元素作为基准，通常选择第一个元素、最后一个元素或者随机选取。
分区：将数组中的其他元素按照与基准元素的大小关系分为两个子数组，一个子数组中的元素小于基准元素，另一个子数组中的元素大于基准元素。同时，基准元素所在的位置也确定了。
递归排序：对分区后的两个子数组递归地应用上述步骤，直到子数组的大小为1或0（即已经有序）。
合并结果：将所有子数组的结果合并起来，即得到最终的有序数组。

void QuickSort(int arr[],int l,int r){
    if(l>=r) return;  //递归出口
    int num=arr[l],front=l-1,rear=r+1; //注意前后两指针的初始位置
    while(front<rear){
        while(arr[++front]<num);
        while(arr[--rear]>num);
        if(front<rear) swap(arr[front],arr[rear]);
    }
    QuickSort(arr,l,rear);
    QuickSort(arr,rear+1,r);
}

[!IMPORTANT]
从快排中抽离出来的一个双指针的思想
1
2
3
4
5
while(front<rear){
		while(Condition1) Action1; 
		while(Condition2) Action2;
		Action3;
}
Condition1用来确定左指针在一轮循环中什么时候停止，Action1是遍历左端序列时需要做的行为；
Condition2用来确定右指针在一轮循环中什么时候停止，Action2是遍历右端序列时需要做的行为；
Action3是完成一轮循环后需要执行的动作。

归并排序

归并排序是一种经典的、稳定的排序算法，其基本思想是将一个大问题分解为多个小问题，通过递归地将小问题排序并合并，最终得到整体问题的解决。

归并排序的基本思想可以概括为以下几个步骤：

分解：将待排序的数组递归地分解为较小的子数组，直到每个子数组只包含一个元素（即已经有序）或为空。
合并：将分解得到的子数组逐个合并，得到更大的有序子数组。合并过程是通过比较每个子数组的元素，选取最小（或最大）的元素放入新的数组中，并移动相应的指针。
递归排序和合并：重复执行步骤1和步骤2，直到所有的子数组合并为一个完整的有序数组。

void MergeSort(int arr[],int l,int r){
    if(l>=r) return;
    int mid=l+r>>1;
    MergeSort(arr,l,mid);
    MergeSort(arr,mid+1,r);
    int idx=0, idx1=l,idx2=mid+1;
    int tmp[100010];
    while(idx1<=mid && idx2<=r)
        if(arr[idx1]<arr[idx2]) tmp[idx++]=arr[idx1++];
        else tmp[idx++]=arr[idx2++];
    while(idx1<=mid) tmp[idx++]=arr[idx1++];
    while(idx2<=r) tmp[idx++]=arr[idx2++];
    for(int i=l,j=0;i<=r;i++,j++) arr[i]=tmp[j];
}

[!IMPORTANT]
从归并排序中抽离出来的一个双指针的思想，也就是说双路归并使用双指针即可。
假如是多路归并呢？想想数据结构这门课中所学的赢者树和败者树，其本质都是堆。因此多路归并完全可以用堆（优先队列）进行优化。
1
2
3
4
5
6
while(idx1<len1 && idx2<len2){
   		if(Condition1) Action1;
   		else Action2;
}
while(Condition2) Action3;
while(Condition3) Action4;
Condition1是两个数组进行比较的条件，Action1是对应条件为真执行的动作，Action2是对应条件为假执行的动作。
Condition2是对数组1进行的扫尾条件判断，Action3是对应的扫尾动作；
Condition3是对数组2进行的扫尾条件判断，Action4是对应的扫尾动作；
OJ例题：寻找两个正序数组的中位数

sort函数

在OJ的题目中，一般不会手动写排序函数，可以直接调用C++的sort函数进行排序！其中，最关键的点就是排序规则的定义。默认情况下是升序排序，可以通过在第三个参数填入greater<int>()来实现降序排序，而且是针对一般的整数数组。要自定义排序规则，则需要实现一个自定义的比较函数bool cmp()。

[!Note]
如学生类比较函数的规则：先按分数升序排序，相同按名字字母序排序。

bool cmp(Student s1, Student s2){
  	if(s1.score != s2.score) return s1.score > s2.score;
  	else return strcmp(s1.name,s2.name) < 0;
}

二分

二分通过不断将搜索范围减半来快速定位目标元素。

[!CAUTION]
二分的主要思想不是单调性（当然序列满足单调性一定能二分做），而是能否根据某一性质划分为左右两个区间！
每进行一次二分就是把答案所在的区间给缩小，因此需要准确地判断出答案应该在哪个区间！当区间的长度为1时，那么该区间中的元素就是答案！

整数二分

无论是l+r>>1还是l+r+1>>1都是为了数组元素个数为奇时，处理好边界问题。

int bsearch_l(int l,int r){  //找左边边界
		while(l<r){
      	int mid=l+r>>1;
      	if(check(mid)) r=mid; //这个check函数需要严格考虑边界情况，以及方向是否正确
      	else l=mid+1;
    }
  	return l; //这里无论返回是l还是r都是一样的
}

int bsearch_r(int l,int r){  //找右边边界
		while(l<r){
      	int mid=l+r+1>>1;
      	if(check(mid)) l=mid;
      	else r=mid-1;
    }
  	return l;
}

[!Tip]
主要通过check函数判断应该递归哪个区间来判断使用哪个模板。二分找不到元素的情况是下标l对应的元素不等于需要查找的元素！

单调性二分

int search(vector<int>& nums, int target) {
    int l=0,r=nums.size()-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(nums[mid]>=target) r=mid; //需要严格注意边界和区间
        else l=mid+1;
    }
    if(nums[l]!=target) return -1;
    else return l;

}

特性二分

这个题目典型就是根据旋转之后，根据哪一边是有序的这一特性进行二分的。

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = left + right >> 1;
        if (nums[mid] == target) return mid;
        // 判断哪一半是有序的
        if (nums[left] <= nums[mid])// 左半部分是有序的
            if (nums[left] <= target && target < nums[mid]) 
                right = mid - 1; // 目标值在左半部分
            else 
                left = mid + 1; // 目标值在右半部分
        else // 右半部分是有序的
            if (nums[mid] < target && target <= nums[right]) 
                left = mid + 1; // 目标值在右半部分
            else
                right = mid - 1; // 目标值在左半部分
    }
    return -1; 
}

非指针二分

[!Note]
这里的非指针二分其实也是特性二分中的一种，只是这种二分更加抽象，以至于连left和right都不再只是表示区间两端的指针。
如这个题目中的，假设把left定义成子区间长度的下限，而right定义为子区间长度的上限，那么问题就变成，求解一个最小的区间长度，使得check满足条件。

//判断长度为mid的子数组和是否能够大于等于target
bool isOver(vector<int>& sum, int mid, int target){
    int n = sum.size();
    for(int i=mid; i<n; i++)
        if((sum[i]-sum[i-mid])>=target)
            return true;
    return false;
}
int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    vector<int> sum(n+1, 0);
    for(int i=1; i<=n; i++)
        sum[i] = sum[i-1]+nums[i-1];  //前缀和
    int left = 1;
    int right = n;  //子数组的长度范围为闭区间[1, n]
    while(left<=right){  //二分查找
        int mid = (left+right)>>1;
        if(!isOver(sum, mid, target)) left = mid+1;
        else right = mid-1;
    }
    return left==n+1 ? 0 : left;
}

左右边界不一致

[!NOTE]
在前面的举例中，无一例外都是左右边界一直的情况，所以无论是bsearch_l还是bsearch_r都能完成任务。但是一旦当左右边界不一致时，bsearch_l所求的是左边界，而bsearch_r所求的是右边界。

vector<int> searchRange(vector<int>& nums, int target) {
    if(nums.size()==0) return vector<int>{-1,-1};
    int l=0,r=nums.size()-1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(nums[mid]<=target) l=mid;
        else r=mid-1;
    }
    int right=l;
    l=0;r=nums.size()-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(nums[mid]>=target) r=mid;
        else l=mid+1;
    }
  	int left=l;
    if(target==nums[left]) return vector<int>{left,right};
    return vector<int>{-1,-1};
}

浮点二分

浮点二分常见于一些求实根的题目中。eg. xmu2024年人工智能实验室夏令营机式的第一题就是利用浮点二分求实根！需要额外注意的就是eps的精度问题，一般需要比保留的位数多两位。

double bsearch_1(double l,double r){
		while(r-l>eps){
      	double mid=(l+r)/2;
      	if(check(mid)) r=mid;  
      	else l=mid;
    }
  	return l;
}

当然，如果一些题目只需要保留整数部分，那么也是可以用整数二分去求解的。

int mySqrt(int x) {
    int left = 0, right = x;
    while(left <= right){
        int mid = left + right >> 1;
        double p = 1.0 * mid * mid;
        if(p == x) return mid;
        else if(p < x) left = mid + 1;
        else right = mid - 1;
    }
    return right;
}

大数运算

注意大数在数组中的存储顺序：从低位存储到高位。

大数加

#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &a, vector<int> &b){
    vector<int> res;int sum=0;
    for(int i=0;i<a.size()||i<b.size();i++){
        if(i<a.size()) sum+=a[i];
        if(i<b.size()) sum+=b[i];
        res.push_back(sum%10);
        sum/=10;
    }
    if(sum) res.push_back(1);
    return res;
}
int main(){
    string a,b; vector<int> A,B;
    cin>>a>>b;
    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 res= add(A,B);
    for(int i=res.size()-1;i>=0;i--) cout<<res[i];
    return 0;
}

大数减

#include <iostream>
#include <vector>
using namespace std;
bool cmp(const vector<int> &a,const vector<int>&b){
    if(a.size()!=b.size()) return a.size()>b.size();
    else for(int i=a.size()-1;i>=0;i--) if(a[i]!=b[i]) return a[i]>b[i];
    return true;
}
vector<int> sub(vector<int> &a, vector<int>&b){
    vector<int> res;int sum=0;
    for(int i=0;i<a.size();i++){
        sum+=a[i];
        if(i<b.size()) sum-=b[i];
        res.push_back((sum+10)%10);
        if(sum<0) sum=-1;  //借位与否
        else sum=0;
    }
    while(res.size()>1 && res.back()==0) res.pop_back();  //去掉前导0
    return res;
}
int main(){
    string a,b;vector<int> A,B;
    cin>>a>>b;
    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');
    vector<int> res;
    if(cmp(A,B)) {res=sub(A,B); for(int i=res.size()-1;i>=0;i--) cout<<res[i];}
    else {res=sub(B,A); cout<<"-"; for(int i=res.size()-1;i>=0;i--) cout<<res[i];}
    return 0;
}

大数乘

vector<int> mul(vector<int> a,int b){
    vector<int> res;int sum=0;
    for(int i=0;i<a.size() || sum;i++){
        sum+=a[i]*b;
        res.push_back(sum%10);
        sum/=10;
    }
    return res;
}

大数除

vector<int> div(vector<int> a,int b，int &c){  //c是余数
    vector<int> res; int sum=0;
    for(int i=a.size()-1;i>=0;i--){
        sum=sum*10+a[i];
        res.push_back(sum/b);
        sum%=b;
    }
  	c=sum; reverse(res.begin(),res.end());
    while(res.size()>1 && res.back()== 0) res.pop_back();
    return res;
}

哈希

整数哈希

整数哈希的作用是将数据范围较大的值域转换到范围较小的值域空间。其中避免哈希冲突的方案有拉链法和开放地址法。

原数据大且稀疏，转到到小且稠密的空间上。

除了数据空间的映射之外，哈希还可能应用到一些在集合以$O(1)$时间复杂度去判断元素是否存在的场景。

拉链法

const int N=1e5+3;  // N一定要是素数且大于数据范围
int h[N],e[N],ne[N],idx; // 其中h是指针数组，e存储节点，ne存储指针
void init(){
  	memset(h,-1,sizeof h);
  	memset(ne,-1,sizeof ne);
}
void insert(int x){
  	int k=(x%N+N)%N;
  	e[idx]=x;ne[idx]=h[k];h[k]=idx++; // 这三句是头插法实现，如果用尾插法不要直接循环找末尾元素，可以增加一个尾指针。
}
bool find(int x){
  	int k=(x%N+N)%N;
  	for(int i=h[k];i!=-1;i=ne[i])
      	if(e[i]==x) return true;
  	return false;
}

N = 100003  # N 是素数且大于数据范围
h, e, ne, idx = [-1]*N, [0]*N, [-1]*N, 0     

def init():
    global h, ne, idx
    h = [-1] * N
    ne = [-1] * N
    idx = 0

def insert(x):
    global idx
    k = (x % N + N) % N  # 处理负数取模
    e[idx] = x
    ne[idx] = h[k]
    h[k] = idx
    idx += 1

def find(x):
    k = (x % N + N) % N  # 处理负数取模
    i = h[k]
    while i != -1:
        if e[i] == x:
            return True
        i = ne[i]
    return False

经典例题：1012.哈希表（链地址法处理冲突） - Problems | SWUST OJ

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int m,n,idx;
void insert(int h[],int e[],int ne[],int c){
    int k=(c%m+m)%m;
    int i=h[k];
    while(i!=-1 && ne[i]!=-1) i=ne[i];
    e[idx]=c;
    if(i==-1) {h[k]=idx++;}
    else {ne[i]=idx++;}
}
PII find(int h[],int e[],int ne[],int c){
    int k=(c%m+m)%m;int i=h[k];int sum=0;
    while(i!=-1){
        sum++;
        if(e[i]==c) return make_pair(k,sum);
        i=ne[i];
    }
    return make_pair(k,-1);
}
int main(){
    cin>>m>>n;
    int h[m],e[m],ne[m],num;
    memset(h,-1,sizeof h);
    memset(ne,-1,sizeof ne);
    for(int i=0;i<n;i++) {
        cin>>num;
        insert(h,e,ne,num);
    }
    cin>>num;
    PII res=find(h,e,ne,num);
    if(res.second!=-1) cout<<res.first<<","<<res.second;
    else cout<<"-1";
    return 0;
}

开放地址法

const int N=2e5+3;   //这个N需要是大于2到3倍数据范围的一个最小质数
const int INF=0x3f3f3f3f;  //约定改数表示位置无数据存储
int h[N];
void init(){
  	memset(h,0x3f,sizeof h);
}

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置。因此find的返回值还需要再进行一次if判断。
int find(int x){
  	int k=(x%N+N)%N;
  	while(h[k]!=INF && h[k]!=x){
      	k++;
      	if(k==N) k=0;
    }
  	return k;
}

最长连续序列

也就是说是可以自己实现C++ STL容器unordered_set。

const static int maxn=2e5+3;
const int INF=0x3f3f3f3f;
int h[maxn];
void init(){
    memset(h,0x3f,sizeof h);
}
int find(int x){
    int k=(x%maxn+maxn)%maxn;
    while(h[k]!=INF && h[k]!=x){
        k++;
        if(k==maxn) k=0;
    }
    return k;
}
int longestConsecutive(vector<int>& nums) {
    init();
    for(auto item:nums){
        int idx=find(item);
        if(h[idx]==INF) h[idx]=item;
    }
    int res=0;
    for(auto item :nums){
        if(h[find(item-1)]==INF){
            int curnum=item;
            int curlen=1;
            while(h[find(curnum+1)]!=INF){curlen++;curnum++;}
            res=max(res,curlen);
        }
    }
    return res;
}

字符串哈希

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

可以用来快速判断区间字符串是否一致。

字符串下标必须从1开始，可以更好地处理边界问题。

typedef unsigned long long ULL;  //用unsigned long long存储就避免了取模运算
const int N=1e5+10;
const int P=131; // P的经验值是131或13331
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
void init(string 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;
    }
}

// 计算子串 str[l ~ r] 的哈希值
ULL strHash(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];  // r-l+1是这两个位数之间差的值
}

前缀和与差分

前缀和的作用：能够快速求出原数组中一段的和。前缀和数组还有个最基本的性质，就是单调递增的。

差分的作用：可以用于处理区间修改和查询操作。通过对差分数组进行修改，可以在常数时间内更新原始序列的某个区间。这对于需要频繁修改某个区间的问题非常有用，如区间加法、区间减法等。

[!TIP]
数组下标必须从1开始，可以更好地处理边界问题。

一维前缀和

一维前缀和数组：sum[i] = sum[i - 1] + arr[i];

const int size=4;
int sum[size];
int main(){
    for (int i = 1; i <= size; i++)
        sum[i] = sum[i - 1] + arr[i];
    return 0;
}

二维前缀和

二维前缀和数组：sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + arr[i][j];

const int x_size = 4;
const int y_size = 4;
int sum[y_size][x_size];
int main(){
    for (int i = 1; i <= y_size; i++)
        for (int j = 1; j <= x_size; j++)
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + arr[i][j];
    return 0;
}

一维差分

一维差分数组：dif[i] = arr[i] - arr[i - 1]

对差分数组进行前缀和运算可以获得原数组，但局限于多次操作单次(少次)还原

一维差分运算：

arr[L,R]+value

等价于

dif[L]+value,

dif[R+1]-value

const int size=4;
int dif[size];
int main(){
    for (int i = 1; i <= size; i++)
        dif[i] = arr[i] - arr[i - 1];	
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e6+10;
int arr[N],dif[N];
void insert(int l,int r,int c){
    dif[l]+=c;
    dif[r+1]-=c;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int i=1;i<=n;i++) insert(i,i,arr[i]);  //这就是在初始化差分数组
    for(int i=0;i<m;i++){
        int l,r,c; cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++) arr[i]=arr[i-1]+dif[i];
    for(int i=1;i<=n;i++) cout<<arr[i]<<" ";
    return 0;
}

二维差分

二维差分数组：dif[i][j]=arr[i][j]-arr[i-1][j]-arr[i][j-1]+arr[i-1][j-1]

二维差分运算：

arr[x1,x2][y1,y2]+value

等价于

dif[x1][y1]+value,

dif[x1+1][y1]-value,

dif[x1][y1+1]-value,

dif[x1+1][y1+1]+value

const int x_size = 4;
const int y_size = 4;
int dif[y_size][x_size];
int main(){
    for (int i = 1; i <= y_size; i++)
        for (int j = 1; j <= x_size; j++)
            dif[i][j] = arr[i][j] - arr[i][j - 1] - arr[i - 1][j] + arr[i - 1][j - 1];
    return 0;
}

#include <iostream>
using namespace std;
const int N=1e3+10;
int arr[N][N],diff[N][N];
void insert(int x1,int y1,int x2,int y2,int c){
    diff[x1][y1]+=c; diff[x1][y2+1]-=c; diff[x2+1][y1]-=c; diff[x2+1][y2+1]+=c;
}
int main(){
    int n,m,k;cin>>n>>m>>k;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>arr[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) insert(i,j,i,j,arr[i][j]);  //初始化dif数组
    for(int t=0;t<k;t++) {
        int x1,y1,x2,y2,num; cin>>x1>>y1>>x2>>y2>>num; insert(x1,y1,x2,y2,num);
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) arr[i][j]=arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1]+diff[i][j];
    for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) cout<<arr[i][j]<<" "; cout<<endl;}
    return 0;
}

双指针

双指针将$O(n^2)$的算法优化到$O(n)$ 。

双指针最重要的是找到某一种方案去更新两个指针。

双指针可以是从两端往中间靠（大部分情况），也可以是从中间往两端靠（eg. 最长回文子串），也可是同时从一边以不同速度走（大部分情况，eg. KMP算法、链表一趟遍历的删插操作），也可以是作用在不同的序列上（eg. 归并排序中的合并操作）。

最长回文子串

[!TIP]
首先确定回文串，找中心然后想两边扩散看是不是对称的就可以了。
一个元素可以作为中心点，两个元素也可以作为中心点。

int maxL=0,left=0,right=0;
void extend(const string& s,int i,int j,int n){
    while(i>=0 && j<n &&s[i]==s[j]){
        if(j-i+1>maxL){left=i,right=j,maxL=j-i+1;}
        i--;j++;
    }
}
string longestPalindrome(string s) {
    for(int i=0;i<s.size();i++){
        extend(s,i,i,s.size());  //一个元素为中心点
        extend(s,i,i+1,s.size());  //两个元素为中心点
    }
    return s.substr(left,maxL);
}

盛最多水的容器

int maxArea(vector<int>& height) {
    int len = height.size();
    int i=0,j=len-1,maxA=0;
    while(i<j){
        if((j-i)*min(height[i],height[j])>maxA)
            maxA=(j-i)*min(height[i],height[j]);
        if(height[i]>height[j]) j--; //移动短板
        else i++;
    }
    return maxA;
}

三数之和

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    int len =nums.size();
    sort(nums.begin(),nums.end()); //进行排序是为了后面双指针进行双向更新提供条件
    for(int i=0;i<len;i++){
        if(i > 0 && nums[i] == nums[i-1]) continue; //防止遍历的i出现重复
        int l=i+1,r=len-1;
        while(l<r){
            if(nums[l]+nums[r]==-nums[i]) {
                res.push_back({nums[i],nums[l++],nums[r]}); 
                while(nums[l-1]==nums[l] && l<r) l++; //防止双指针出现重复元素
            }
            else if (nums[l]+nums[r]>-nums[i]) r--;
            else l++;
        }
    }
    return res;
}

位运算

求n的2进制的第k位数字：n>>k & 1

提取一个整数 n 的二进制表示中最低位的 1 所代表的值：lowbit(n)=n & -n

离散化

离散化的本质是建立了一段数列到自然数之间的映射关系（value -> index)，通过建立新索引，来缩小目标区间，使得可以进行一系列连续数组可以进行的操作。eg：二分，前缀和等

[!caution]
离散化首先需要排序去重！

排序：sort(alls.begin(),alls.end())
去重：alls.earse(unique(alls.begin(),alls.end()),alls.end())

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x){ // 找到第一个大于等于x的位置
    int l = 0, r = alls.size() - 1;
    while (l < r){
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

区间和

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
typedef pair<int, int> PII;
int n, m;
int arr[N], sum[N];
vector<int> odd;
vector<PII> add, query;

//value->key的映射函数(通过二分实现)
int find(int x) {
    int len = odd.size();
    int l = 1, r = len;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (odd[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return l + 1;
}

int main() {
    cin >> n >> m;
    //读入数据，并将需要离散化的数据添加到odd中
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        add.push_back(make_pair(x, c));
        odd.push_back(x);
    }
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        query.push_back(make_pair(l, r));
        odd.push_back(l);
        odd.push_back(r);
    }
    //排序与去重，为了使用二分查找建立值到键的索引
    sort(odd.begin(), odd.end());
    odd.erase(unique(odd.begin(), odd.end()), odd.end());
  	
  	//将对原数的操作映射到对离散后数值的操作
    for (auto item : add) {
        int idx = find(item.first);
        arr[idx] += item.second;
    }
  	//建立前缀和数组
    for (int i = 1; i <= odd.size(); i++) {
        sum[i] += sum[i - 1] + arr[i];
    }
   	//利用前缀和求区间和
    for (int i = 0; i < m; i++) {
        int l = find(query[i].first), r = find(query[i].second);
        cout << sum[r] - sum[l - 1] << endl;
    }
    return 0;
}

区间合并

首先需要将所有的区间根据其左区间的值进行升序排序；然后遍历每一个区间进行合并；遍历期间需要维护一个用于合并的区间。

对于待合并的区间，只可能与维护的区间有三种可能性：

待合并区间完全包括在维护的区间中
无需更新维护区间
待合并区间与维护的区间有部分交集（且只可能是End端不在维护的区间中）
**将维护区间的End换成待合并区间的End**。
待合并区间与维护的区间完全无交集
当前维护的区间可以纳入答案中，将该待合并的区间作为新的维护区间。

typedef pair<int,int> PII;
void merge(vector<PII> &segs){ // 将所有存在交集的区间合并
    vector<PII> res;
    sort(segs.begin(), segs.end());  //默认以左区间进行排序
    int st = -2e9, ed = -2e9;  // 设置区间的边界
    for (auto seg : segs)
        if (ed < seg.first){  // 新的区间与维护的区间无交集
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second); 
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
}

KMP算法

KMP算法用来解决子串与父串进行匹配的问题，可以将时间复杂度为$O(n^2)$的暴力匹配变成时间复杂度为$O(n+m)$。KMP算法的核心思想是利用已经匹配的信息来避免重复匹配，从而提高匹配效率。next数组记录了模式字符串中每个位置的前缀和后缀的最长公共部分的长度（最长相同前后缀or模式串匹配失败后应该重新开始匹配的位置）。

特别需要注意的是：主串和模板串都从第一个位置开始存储。

手算next数组

#include <iostream>
const int N=1e6+10,M=1e6+10;
char str1[N],str2[M];
int ne[M];
int n,m;
using namespace std;
void get_next(){  
    for(int i=2,j=0;i<=m;i++){ //从模式字符串的第二个字符开始遍历（因为部分匹配表的第一个值总是0）
        while(j && str2[i]!=str2[j+1]) j=ne[j]; //如果当前字符和前缀字符不匹配，并且j不为0，则回溯到前一个部分匹配的位置
        if(str2[i]==str2[j+1]) j++; //如果当前字符和前缀字符匹配，则j加1
        ne[i]=j;
    }
}
void kmp(){
    for(int i=1,j=0;i<=n;i++){
        while(j && str1[i]!=str2[j+1]) j=ne[j];
        if(str1[i]==str2[j+1]) j++;
        if(j==m){
            printf("%d ",i-m);
            j=ne[j];  //子串完全匹配后，下一个字符肯定不再相等，因此j需要重新回溯
        }
    }
}
int main(){
    cin>>n>>str1+1>>m>>str2+1;  //两个字符数组下标从1开始存储
    get_next();
    kmp();
    return 0;
}

最短回文串

理解KMP算法的关键一步是理解next数组的含义，即字符串中每个位置的最长相等前后缀的长度，这种特性能很好地与回文串结合。

将任意串baacbca翻转再拼接原串acbcaabbaacbca的next数组为00001100112345，很有意思的是next数组的最后一个值就是原串中存在的一个最长回文串[arr.end()-5+1,arr.end()]的长度。假若需要将原串在一个方向添加字符拼凑成新的回文串，则只需在原串的末尾拼凑上原串[arr.begin(),arr.begin()+arr.size()-5]的字符即可。

string shortestPalindrome(string s) {
    const static int maxn=1e5+10;
    int ne[maxn];
    string s1=" "+s+" "+string(s.rbegin(),s.rend());  //第一个空格是为了next数组计算，第二个空格是防止原串全为相同字符，导致回文串长度超过原串长度
    int len=s1.size();
    for(int j=0,i=2;i<len;i++){
        while(j && s1[i]!=s1[j+1]) j=ne[j];
        if(s1[i]==s1[j+1]) j++;
        ne[i]=j;
    }
    string s2=s.substr(0,ne[len-1]);
    string s3=s.substr(ne[len-1]);
    return string(s3.rbegin(),s3.rend())+s2+s3;
}

重复的子字符串

KMP算法在应用层面最重要的就是场景识别，即在具体问题中能够抽象出使用KMP算法的场景，即模式串匹配。

const static int maxn=2e4+10;
int ne[maxn];
void getnext(const string& s){
    int len=s.size();
    for(int j=0,i=2;i<len;i++){
        while(j && s[i]!=s[j+1]) j=ne[j];
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
    }
}
bool repeatedSubstringPattern(string s) {
    string ss=s+s;
    int len = ss.size();
    s=" "+s;
    getnext(s);
    for(int j=0,i=1;i<len-1;i++){
        while(j && ss[i]!=s[j+1]) j=ne[j];
        if(ss[i]==s[j+1]) j++;
        if(j==s.size()-1) return true;
    }
    return false;
}

基础数据结构

STL

vector

deque

stack

queue

priority_queue

list

集合系列

set

底层结构：set底层是由红黑树实现（红黑树是一种平衡二叉树），存储空间不连续；
访问遍历：不支持随机访问迭代器，不能通过下标直接访问，支持按顺序迭代，迭代器遍历的顺序是从小到大的顺序；
操作效率：查询/插入/删除的效率都为$O(logn)$；
排序方式 : 默认使用less仿函数 , 即<运算符进行排序 ; 也可以自定义排序规则仿函数 ;
使用场景：需要集合有序且元素不重复的场景；

multiset

底层结构 : 底层由红黑树实现 , 红黑树是一种平衡二叉搜索树 , 存储空间不连续;
访问遍历 : 不支持随机访问迭代器 , 不能听过下标访问 , 支持按顺序迭代，迭代器遍历的顺序是从小到大的顺序；
操作效率：查询 / 插入 / 删除效率为 O(log n) 复杂度;
排序方式 : 默认使用less仿函数 , 即<运算符进行排序 ; 也可以自定义排序规则仿函数;
使用场景 : 需要 集合有序 且 元素重复 的场景;

unordered_set

底层结构 : 底层由 哈希表 实现 , 存储空间不连续;
访问遍历 : 不支持随机访问迭代器 , 不能听过下标访问;
操作效率：插入、删除和查找操作的平均时间复杂度为 O(1)，但在最坏情况下可能达到 O(n)；
使用场景 : 更适合 频繁插入和查找操作 且 不关心元素顺序 的场景；

字典系列

[!Tip]
字典容器与集合容器的区别是字典容器存储的是 键值对元素 , 是 pair 对象；集合容器存储的是单纯的 键单个元素 ;

map

底层结构 : 底层由红黑树实现 , 红黑树是一种平衡二叉搜索树 , 存储空间不连续 ; 存储的元素是键值对元素;
访问遍历 : 不支持随机访问迭代器 , 不能听过下标访问 , 只能通过迭代器进行访问;
操作效率：查询 / 插入 / 删除效率为 O(log n) 复杂度 ; 与 set 集合容器相同;
排序方式 : 默认使用less仿函数 , 即<运算符进行排序 ; 也可以自定义排序规则仿函数 ; map 映射容器不允许重复的键 , multimap 多重映射容器允许重复的键;
使用场景 : 需要有序键值对且 元素不重复 的场景;

multimap

底层结构: 底层由红黑树实现，红黑树是一种平衡二叉搜索树，存储空间不连续，存储的元素是键值对元素 ;
访问遍历: 不支持随机访问迭代器 , 不能听过下标访问 , 只能通过迭代器进行访问 ;
操作效率：查询 / 插入 / 删除效率为 O(log n) 复杂度 ; 与 set 集合容器相同 ;
排序方式：默认使用less仿函数 , 即<运算符进行排序 ; 也可以自定义排序规则仿函数 ; map 映射容器不允许重复的键 , multimap 多重映射容器允许重复的键;
使用场景: 需要有序键值对且 元素重复 的场景 ;

unordered_map

底层结构：set底层是由红黑树实现（红黑树是一种平衡二叉树），存储空间不连续，存储的元素是键值对元素 ;
操作效率：插入、删除和查找操作的平均时间复杂度为 O(1)，但在最坏情况下可能达到 O(n)；
使用场景 : 更适合 频繁插入和查找操作 且 不关心元素顺序 的场景；

bitset

模拟链表

单链表

const int N =1e6+10;
int head,idx; // head是链表的头结点，idx是当前链表指针
int e[N],ne[N]; // e静态链表数组，ne是链表指针数组。即e数组存储节点的值，而ne存储节点的next指针
void init(){
  	head=-1; idx=0;
}
void add2head(int c){
  	e[idx]=c;
  	ne[idx]=head; 
  	head=idx++;
}
void add(int k,int c){
  	e[idx]=c;
  	ne[idx]=ne[k];
  	ne[k]=idx++;
}
void earse(int k){
  	ne[k]=ne[ne[k]];
}

双链表

const int N=100010;
int e[N],l[N],r[N],idx;

//初始化
void init(){
    l[1]=0;r[0]=1;idx=2;
}

//在节点a的右边插入一个数x
void insert(int a,int x){
    e[idx]=x;
    l[idx]=a,r[idx]=r[a];
    l[r[a]]=idx,r[a]=idx++;
} 

//删除节点a
void remove(int a){
    l[r[a]]=l[a];
 
}

邻接表

int h[N], e[N], ne[N], idx;
void init(){
    idx = 0;
  	memset(h, -1, sizeof h);
}
// 添加一条边a->b
void add(int a, int b){
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}

模拟栈

const int N=1e6+10;
int stk[N],tt;
//push
stk[++tt]=x;
//pop
tt--;
//judge empty
if(tt>0) not empty
else empty
//top of stack
stk[tt];

模拟队列

const int N=1e6+10;
int que[N],hh,tt=-1;  //hh是队头，tt是队尾
//push
que[++tt]=x;
//pop
hh++;
//judge empty
if(hh<=tt) not empty
else empty
//front of queue
que[hh];

如果要实现循环队列，只需要每次在插入值时对tt进行判断，如果其等于N就将其赋值为0。或者直接que[++tt%N]=x;，当然这样就要注意操作次数，防止整数溢出。

const int N = 1e6 + 10;
int que[N], hh = 0, tt = 0;  // hh是队头，tt是队尾
bool isEmpty() {
  	return hh == tt;
}
bool isFull() {
    return (tt + 1) % N == hh;
}
void push(int x) {
    que[tt] = x;
    tt = (tt + 1) % N;  // 更新队尾，使用取模实现循环
}
void pop() {
    hh = (hh + 1) % N;  // 更新队头，使用取模实现循环
}
int front() {
    return que[hh];
}

单调栈

[!Caution]
常见题型：找出区间每个数左边（右边）离它最近的比它大/小的数，特别是“最近”两字！
单调增栈求更大，单调减栈求更小
OJ例题：P5788 【模板】单调栈 - 洛谷

const int N=1e6+10;
int stk[N],tt = 0;
for (int i = 1; i <= n; i ++ )  //左边
{
    while (tt && check(stk[tt], i)) tt--;  // 单调栈就是始终需要维护一个单调的栈
  	if(tt) find the value stk[tt];
  	else not find;
    stk[++tt] = i;
}
for (int i = n-1; i >= 0; i -- )  //右边
{
    while (tt && check(stk[tt], i)) tt--;  // 单调栈就是始终需要维护一个单调的栈
  	if(tt) find the value stk[tt];
  	else not find;
    stk[++tt] = i;
}

pre.push_back(INT_MAX);  //这一步相当关键，这里push的值需要根据单调增还是减栈确定，增站用max，减栈用min
for (int i = 0; i <= len; i++) { //左右两边
    while (tt && pre[stk[tt]] <= pre[i]) { // 单调增栈
        int idx = stk[tt--];
        res1[idx] = (tt == 0 ? -1 : stk[tt]);  //左端
        res2[idx] = (i == len ? -1 : i);  //右端
    }
    stk[++tt] = i;
}

接雨水

const static int N = 2e4 + 10;
int stk[N], tt = 0;
int trap(vector<int> &height) {
    int res1[N], res2[N];
    int len = height.size();
    height.push_back(INT_MAX);
    for (int i = 0; i <= len; i++) {
        while (tt && height[stk[tt]] < height[i]) { // 单调增栈
            int idx = stk[tt--];
            res1[idx] = (tt == 0 ? -1 : stk[tt]);
            res2[idx] = (i == len ? -1 : i);
        }
        stk[++tt] = i;
    }
    int sum = 0;
    for (int i = 0; i < len; i++)
        if (res1[i] != -1 && res2[i] != -1)
        sum += (min(height[res1[i]], height[res2[i]]) - height[i])*(res2[i]-res1[i]-1);
    return sum;
}

[!WARNING]
这个LeetCode的题“接雨水 ”，看似可以利用左右两边比其大而形成蓄水部位的特性利用单调栈解题，~~但是忽略了“最近”这个局部的概念而导致很难正确求解~~。
补：利用这个局部也是能正确求解的，使用分层的思想。
height = [0,1,0,4,1,0,1,3,2,1,2,1]
假如把左/右没有比起更大的值记为-1，那么每个元素其左边最近更大的下标序列为：
-1 -1 1 -1 3 4 3 3 7 8 7 10
其右边最近更大的下标序列为：
1 3 3 -1 7 6 7 -1 -1 10 -1 -1
将左右两边序列结合观察，只有在2,4,5,6,9这几个位置蓄水（对应位置均不为-1）。第5个位置就暴露出“最近”这个局部概念的问题，其得到的左右两边更大的，能够形成的局部蓄水高度并不是其全局蓄水高度。
因此，想要从这直接计算每个位置的最大蓄水高度显然是不行的。但也很好解决，只要确定每个可蓄水位的最大蓄水高度就能够完成最终求解。
左侧最大蓄水高度：[0,1,1,4,4,4,4,4,4,4,4,4]
右侧最大蓄水高度：[4,4,4,4,3,3,3,3,2,2,2,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const static int N = 2e4+10;
int stk[N],tt=0;
int trap(vector<int>& height) {
    int lmax[N],rmax[N];
    vector<int> res1,res2;
    int len=height.size();
    lmax[0]=height[0],rmax[len-1]=height[len-1];
  
    for(int i=1;i<len;i++) lmax[i]=max(lmax[i-1],height[i]); 
    for(int i=len-2;i>=0;i--) rmax[i]=max(rmax[i+1],height[i]); 
  
    for(int i=len-1;i>=0;i--){ //需要找右边离他最近且比他大or相等的元素
        while(tt && height[stk[tt]]<=height[i]) tt--;
        if(tt) res1.push_back(stk[tt]);
        else res1.push_back(-1);
        stk[++tt]=i;
    }
    tt=0;
    for(int i=0;i<len;i++){
        while(tt && height[stk[tt]]<=height[i]) tt--;
        if(tt) res2.push_back(stk[tt]);
        else res2.push_back(-1);
        stk[++tt]=i;
    }
    reverse(res1.begin(),res1.end());
    int sum=0;
    for(int i=0;i<len;i++)
        if(res1[i]!=-1 && res2[i]!=-1)
            sum+=min(rmax[res1[i]],lmax[res2[i]])-height[i];
    return sum;
}
上面的方法从左到右和从右到左用了两次单调栈来寻找左边和右边的更大元素。其实这是没必要的，可以只用一趟就能够同时完成寻找作用两边更大的元素。
模板还是一样，但思路有点不同。在两次单调栈中，我们每次都是将外循环for遍历到的元素当成基准元素来找寻离当前基准元素左/右边更大的元素。但是在一次单调栈中，当前遍历到的元素不在基准元素，反而是左/右边更大的元素。
我们假设外层的for循环是从左到右，且栈是单调增栈。当外循环遍历到元素i时，此时i为右边界，从内循环while出来后的栈顶元素为基准，下一个栈顶元素为左边界。此时寻找到左边界和右边界都是比基准元素更小且最近的值。
因此，上面的代码可以进一步优化为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const static int N = 2e4 + 10;
int stk[N], tt = 0;
int trap(vector<int> &height) {
    int lmax[N], rmax[N];
    int res1[N], res2[N];
    int len = height.size();
    lmax[0] = height[0], rmax[len - 1] = height[len - 1];
    for (int i = 1; i < len; i++) lmax[i] = max(lmax[i - 1], height[i]);
    for (int i = len - 2; i >= 0; i--) rmax[i] = max(rmax[i + 1], height[i]);
    height.push_back(INT_MAX);  //这一步相当关键
    for (int i = 0; i <= len; i++) {
        while (tt && height[stk[tt]] <= height[i]) { // 单调增栈
            int idx = stk[tt--];
            res1[idx] = (tt == 0 ? -1 : stk[tt]);
            res2[idx] = (i == len ? -1 : i);
        }
        stk[++tt] = i;
    }
    int sum = 0;
    for (int i = 0; i < len; i++)
        if (res1[i] != -1 && res2[i] != -1)
        sum += min(lmax[res1[i]], rmax[res2[i]]) - height[i];
    return sum;
}
当然，尽管优化成一轮遍历，但其实如果按照这个思路求解，前面的找可蓄水位其实就是没必要的操作了！
因此我们尝试不去计算每个位置左右的最大蓄水高度，只用已求解的局部需水量进行分层计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const static int N = 2e4 + 10;
int stk[N], tt = 0;
int trap(vector<int> &height) {
    int res1[N], res2[N];
    int len = height.size();
    height.push_back(INT_MAX);
    for (int i = 0; i <= len; i++) {
        while (tt && height[stk[tt]] < height[i]) { // 单调增栈
            int idx = stk[tt--];
            res1[idx] = (tt == 0 ? -1 : stk[tt]);
            res2[idx] = (i == len ? -1 : i);
        }
        stk[++tt] = i;
    }
    int sum = 0;
    for (int i = 0; i < len; i++)
        if (res1[i] != -1 && res2[i] != -1)
        sum += (min(height[res1[i]], height[res2[i]]) - height[i])*(res2[i]-res1[i]-1);
    return sum;
}
类似的还有LeetCode柱状图中最大的矩形，这里构建的就是一个单调递减栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int largestRectangleArea(vector<int>& heights) {
    const int N=1e5+10;
    int stk[N],tt=0;
    int len = heights.size();
    int maxSize=0;
    heights.push_back(INT_MIN);  //单调递减栈，插INT_MIN；递增栈，插INT_MAX
    for(int i=0;i<=len;i++){
        while(tt && heights[stk[tt]]>=heights[i]) {  //最近更小，单调减栈，遍历元素需更小；最近更大，单调递增栈，遍历元素需更大
            int idx=stk[tt--];
            int left = (tt==0 ? -1 : stk[tt]);  //一般左边界都需要特判，右边界视题而定
            maxSize=max(maxSize,(i-left-1)*heights[idx]);
        }
        stk[++tt]=i;
    }
    return maxSize;
}
假如我们不使用单调栈，则可以想到使用双指针的算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int trap(vector<int> &height) {
    int len = height.size();
    int l=0,r=len-1,maxl=0,maxr=0;
    int res=0;
    while(l<=r){
        int wal=min(maxl,maxr);
        if(height[l]<=wal){
            res+=wal-height[l++];
            continue;
        }
        if(height[r]<=wal){
            res+=wal-height[r--];
            continue;
        }
        maxl=max(maxl,height[l]);
        maxr=max(maxr,height[r]);
    }
    return res;
}

单调队列

常见题型：求滑动窗口（窗口大小固定）中的最值，求单调队列中的任意值也可用二分。

单调队列中存储的都是Index，而不是Value。

OJ例题：滑动窗口、滑动窗口最大值、和至少为 K 的最短子数组

const int N=1e6+10;
int n,k;  // n是数的个数，k是区间长度
int arr[N],que[N];  // arr用来存储数，que是单调队列，其中存储区间元素的下标
for(int i=0;i<n;i++){
    if(hh<=tt && i-que[hh]+1>k) hh++;  // 如果队列超过区间长度
    while(hh<=tt && arr[que[tt]]>=arr[i]) tt--; // 维护单调队列，如果当前元素要小于单调队列的队尾元素，则队尾元素弹出，确保队列单调递增，队头能够取到最小值。
    que[++tt]=i; // 将当前元素插入
    if(i>=k-1) printf("%d ", arr[que[hh]]);  //当窗口全部滑入数组上后判定
}

和至少为 K 的最短子数组

这个题目很好的将单调队列和前缀和融合在一起！

这个题目必须用前缀和的原因有两点：

1、前缀和在计算区间和时只需O(1)的代价

2、不用前缀和不能满足题目所要求的连续区间。因为在获取单调队列时，必然会导致队列中的元素不再连续（虽然相对位置关系依旧保留）。只有使用前缀和，其中的每一个值代表一个区间的和，才在以离散的状态构建单调队列的同时保持连续区间的要求（两个前缀和数组的值作差能表示一个区间的和）。

typedef long long ll;
const static int N =1e5+10;
int shortestSubarray(vector<int>& nums, int k) {
    int len=nums.size();
    ll sum[N];
    for(int i=1;i<=len;i++) sum[i]=sum[i-1]+nums[i-1];
    ll que[N],hh=0,tt=-1;
    ll minL=INT_MAX;
    for(int i=0;i<=len;i++){ //前缀和得从0开始！
        while(hh<=tt && sum[i]-sum[que[hh]]>=k) minL=min(minL,i-que[hh++]);
        while(hh<=tt && sum[que[tt]]>=sum[i]) tt--;
        que[++tt]=i;
    }
    return minL == INT_MAX ? -1 : minL;
}

环形子数组的最大和

环形问题拉直处理。依旧是前缀和+单调队列。

限制是区间长度不大于数组长度。

当然其实拉直处理，可以用模运算实现，而不是真实地再复制数组一遍。

const static int N = 6e4+10;
int maxSubarraySumCircular(vector<int>& nums) {
    int k = nums.size(),len=k*2;
    nums.insert(nums.end(),nums.begin(),nums.end());
    vector<int> sum(len+1);
    for(int i=1;i<=len;i++)sum[i]=sum[i-1]+nums[i-1];
    int maxV=INT_MIN;
    int que[N],hh=0,tt=-1;
    memset(que,0,sizeof que);
    for(int i=0;i<=len;i++){
        if(hh<=tt && i-que[hh]>k) hh++;
        while(hh<=tt && sum[que[tt]] > sum[i]) tt--;
        if(i>k-1) maxV=max(maxV,sum[i]-sum[que[hh]]);
        que[++tt]=i;
    }
    return maxV;
}

堆

堆是一棵完全二叉树，使用数组从1进行存储。堆可以动态的维护一个区间内的最小值/最大值。

向堆中插入一个数：heap[++size]=x;up(size);

求堆中最小值：heap[1];

删除堆中的最小值：swap(heap[1],heap[size]);size--;down(1);

删除堆中任意一个元素：swap(heap[k],heap[size]);size--;down(k);up(k);

修改任意一个元素：heap[k]=c;down(k);up(k);

堆的数组存储是从下标1开始的。

const int N=1e5+10;
int h[N],n,size;
void down(int x){
  	int tmp=x;
  	if(x*2<=size && h[x*2]<h[tmp]) tmp=x*2;
  	if(x*2+1<=size && h[x*2+1]<h[tmp]) tmp=x*2+1;
  	if(tmp!=x) {
      swap(h[tmp],h[x]);
      down(tmp);
    }
}
void up(int x){
  	while(x/2 && h[x]<h[x/2]) {swap(h[x],h[x/2]);x>>=1;}  //小根堆
}
void build(){  //建堆，时间复杂度为O(n)
  	for(int i=n/2;i>0;i--) down(i); 
}
void push(int c){
  	h[++size]=c;
  	up(size);
}
void pop(){
  	swap(h[1],h[size]);
  	size--;
  	down(1);
}
void pop_k(int k){
  	swap(h[k],h[size]);
  	size--;
  	down(k);up(k);
}
void revise(int k,int c){
  	h[k]=c;
  	down(k);up(k);
}

P3378 【模板】堆 - 洛谷

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int h[N],n,size;
void down(int k){
    int tmp=k;
    if(k*2<=size && h[tmp]>h[k*2]) tmp=k*2;
    if(k*2+1<=size && h[tmp]>h[k*2+1]) tmp=k*2+1;
    if(tmp != k) {swap(h[tmp],h[k]);down(tmp);}
}
void up(int k){
    while(k/2 && h[k/2]>h[k]) {swap(h[k],h[k/2]);k>>=1;}
}
void push(int x){
    h[++size]=x;
    up(size);
}
void pop(){
    swap(h[1],h[size]);
    size--;
    down(1);
}
int main(){
    scanf("%d",&n);
    int c,op;
    for(int i=0;i<n;i++){
        scanf("%d",&c);
        if(c==1){
            scanf("%d",&op);
            push(op);
        }else if(c==2){
            printf("%d\n",h[1]);
        }else{
            pop();
        }
    }
    return 0;
}

Tire树

Tire树是一种用来快速存储字符串集合，统计和排序大量的字符串前缀来减少查询时间，最大限度地减少无谓的字符串比较的数据结构。其特点是字符类别不多（一般就是小写字母、大写字母以及数字），即一般宽度上限为62=26+26+10，而深度上限是字符串的长度。

Trie树是一种多叉树的结构，每个节点保存一个字符，一条路径表示一个字符串。

#include <bits/stdc++.h>
const int N=1e6+10;
int son[N][26],cnt[N],idx;  //son是从0开始存储，而cnt是从1开始存储

//这个insert是求完全匹配的字符串数
void insert(char str[]){  
  	int p=0;
  	for(int i=0;str[i];i++){
      	int u=str[i]-'a';
      	if(!son[p][u]) son[p][u]=++idx; //son数组中存储的是idx
      	p=son[p][u];
    }
  	cnt[p]++;
}

//这个insert是求前缀匹配的字符串数
void insert(char str[]){  
  	int p=0;
  	for(int i=0;str[i];i++){
      	int u=str[i]-'a';
      	if(!son[p][u]) son[p][u]=++idx;
      	p=son[p][u];
      	cnt[p]++;
    }	
}

//这个query是求完全匹配的字符串数
int query(char str[]){
  	int p=0;
  	for(int i=0;str[i];i++){
      	int u=str[i]-'a';
      	if(!son[p][u]) return 0;
      	p=son[p][u];
    }
  	return cnt[p];
}

//这个是求最长公共前缀
int cur=idx;
for(int i=cur;i>0;i--) if(cnt[i]>cnt[cur]) cur=i;
if(cnt[1]==len) cout<<strs[0].substr(0,cur);
else cout<< "";

P8306 【模板】字典树 - 洛谷

#include <bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int son[N][65],cnt[N],idx;
char str[N];
int t,n,q;
void insert(char str[]){
    int p=0, u=0;
    for(int i=0;str[i];i++){
        if(str[i]<='9') u=str[i]-'0';
        else if(str[i]<='Z') u=str[i]-'A'+11;
        else u=str[i]-'a'+37;
        if(!son[p][u]) son[p][u]=++idx;
        cnt[son[p][u]]++;
        p=son[p][u];
    }
}
int query(char str[]){
    int p=0,u=0,sum=0;
    for(int i=0;str[i];i++){
        if(str[i]<='9') u=str[i]-'0';
        else if(str[i]<='Z') u=str[i]-'A'+11;
        else u=str[i]-'a'+37;
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main(){
    scanf("%d",&t);
    for(int j=0;j<t;j++){
        scanf("%d%d",&n,&q);
        for(int i=0;i<n;i++) {scanf("%s",str);insert(str);}
        for(int i=0;i<q;i++) {
            scanf("%s",str);
            printf("%d\n",query(str));
        }
        memset(son,0,sizeof son);
        memset(cnt,0,sizeof cnt);
        idx=0;
    }
    return 0;
}

并查集

并查集是一种用于处理集合合并与查询问题的数据结构。并查集通常用于解决一些与集合划分和连接相关的问题，例如：

连通性问题：判断两个元素是否属于同一个连通分量。
图的最小生成树：在构建最小生成树时，可以使用并查集来判断是否形成了环路，从而避免将边加入最小生成树中。
元素的分类和分组：将元素划分为不相交的组或分类，以便进行高效的组内操作。

并查集的p数组下标从0开始还是从1开始是根据节点编号从0开始还是从1开始确定的。

const int N=1e6+10;
int p[N],n;
void init(){
  	for(int i=1;i<=n;i++) p[i]=i;
}
int find(int x){
  	if(p[x]!=x) p[x]=find(p[x]);
  	return p[x];
}
void join(int x,int y){
  	p[find(x)]=find(y);
}

如果需要维护集合大小，需要重新开辟一个以每个节点为根树大小的数组

const int N=1e5+10;
int p[N],size[N],n;
void init(){
  	for(int i=1;i<=n;i++){p[i]=i;size[i]=1;}
}
int find(int x){ 
  	if(p[x]!=x) p[x]=find(p[x]);
  	return p[x];
}
void join(int x,int y){
  	if(find(x)!=find(y)) size[find(y)]+=size[find(x)];
  	p[find(x)]=find(y);
}

P3367 【模板】并查集 - 洛谷

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int p[N],n,m;
void init(){
    for(int i=1;i<=n;i++) p[i]=i;
}
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
void join(int x,int y){
    p[find(x)]=find(y);
}
int main(){
    scanf("%d%d",&n,&m);
    init();
    int c,x,y;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&c,&x,&y);
        if(c==1) join(x,y);
        else find(x)==find(y)?printf("%s\n","Y"):printf("%s\n","N");
    }
    return 0;
}

树&图

遍历

树的深度优先遍历

[!Note]
树的遍历有先根遍历和后根遍历，其中二叉树还有中根遍历，森林的遍历可以基于树的遍历，有先序遍历和中序遍历。
树的先根遍历序列和其对应的二叉树（左孩子右兄弟存储）的先根遍历序列一致，树的后根遍历序列和其对应的二叉树的中根遍历序列一致。
森林的先序遍历序列等价于每棵树按序先根遍历的序列，此外还可以将森林使用左孩子右兄弟表示法转化成二叉树再进行先序遍历。
森林的中序遍历序列等价于每棵树按序后根遍历的序列，此外还可以将森林使用左孩子右兄弟表示法转化成二叉树再进行中序遍历。

void preorder(TreeNode *root, vector<int> &res) {
    if (root == nullptr) return;
    res.push_back(root->val);
    preorder(root->left, res);
    preorder(root->right, res);
}

void midorder(TreeNode *root, vector<int> &res) {
    if (root == nullptr) return;
    preorder(root->left, res);
    res.push_back(root->val);
    preorder(root->right, res);
}

void postorder(TreeNode *root, vector<int> &res) {
    if (root == nullptr) return;
    preorder(root->left, res);
    preorder(root->right, res);
  	res.push_back(root->val);
}

vector<int> preorderTraversal(TreeNode *root) {
    vector<int> res;
    preorder(root, res);
    return res;
}

树的宽度优先遍历

[!Note]
树的宽度优先遍历的实现逻辑和其二叉树的宽度优先遍历实现逻辑是一致的。

深度优先搜索

[!Note]
在搞懂DFS前，需要明白DFS是基于递归的，只有很好的理解递归，才能将DFS用到炉火纯青！
递归最终要的就是两个点：递归出口和递归点
递归出口即是什么时候截止。
假如遍历一颗BST，需要找到值为5的节点。那么递归出口就有两种情况：当递归到叶节点时终止和当递归找到值为5的节点终止。
递归点即需要找到当前问题如何转换成其子问题。
还是上面那个问题，需要找到值为5的节点。对于当前节点来说，找到值为5的节点有三种可能：当前节点本身值为5，值为5的节点在左子树中，值为5的节点在右子树中。因此问题就向其子空间（子问题）进行了转换，这就是递归点。
OJ例题：深度优先搜索知识点题库
如上面这道OJ例题，判断二叉树是否对称。
其递归出口就有四种情况：左右子树同时递归到叶子结点、左子树递归到叶子结点但右子树没有、右子树递归到叶子结点但左子树没有、左右子树都未递归到叶子结点，但当前存储的值不同。
递归点就是：左子树的左孩子与右子树的右孩子对称、左子树的右孩子与右子树的左孩子对称。
1
2
3
4
5
6
7
8
public boolean isSymmetric(TreeNode root) {
    return isSame(root.left, root.right);
}
private boolean isSame(TreeNode p, TreeNode q) {
    if (p == null && q == null) return  true;
    if ((p == null || q == null) || p.val != q.val) return false;
    return isSame(p.left, q.right) && isSame(p.right, q.left);
}

时间复杂度O(n+m)，n表示点数，m表示边数

深搜的关键在于本状态和下一状态的衔接以及递归出口的设置。

深搜在网格题目中备受关注！

int dfs(int u){
  	if(u==n) return; //递归出口
    st[u] = true; //状态记录
    for (int i = h[u]; i != -1; i = ne[i]){
        if (!st[e[i]]) dfs(j); //进入dfs前有条件限制，则进行了剪枝
    }
  	st[u] = false; //状态恢复
}

B3621 枚举元组 - 洛谷

#include <bits/stdc++.h>
using namespace std;
const int N=6;
int n,k,res[N];
void dfs(int t){
    if(t==n) {for(int i=0;i<n;i++) cout<<res[i]<<" ";cout<<endl;return;}
    for(int i=1;i<=k;i++){
        res[t]=i;
        dfs(t+1);  //这道题就没有涉及到状态恢复
    }
}
int main(){
    scanf("%d%d",&n,&k);
    dfs(0);
    return 0;
}

P10448 组合型枚举 - 洛谷

#include <bits/stdc++.h>
using namespace std;
const int N=26;
int n,k,res[N];
void dfs(int t){
    if(t==n+1) {for(int i=1;i<=n;i++) cout<<res[i]<<" ";cout<<endl;return;}
    for(int i=1;i<=k;i++){
        if(i>res[t-1]){ // 确保递增顺序
            res[t]=i;
            dfs(t+1); 
        }
    }
}
int main(){
    scanf("%d%d",&k,&n);
    dfs(1);
    return 0;
}

[!IMPORTANT]
DFS往往有很多变种，无返回值的DFS，带返回值的DFS，无需状态记录的DFS和带状态记录的DFS等。其中，有无返回值和有无状态记录两者并不是冲突对立的。一个DFS的题目可能是无返回值需要状态记录的，也有可能是带返回值无状态记录的。
无返回值DFS模板：
1
2
3
4
void dfs(['search space',] 'current state parameters'){
  	if('reach of terminal state') return;
  	dfs('next state parameters');
}
OJ例题：岛屿数量
带返回值DFS模板：
1
2
3
4
int dfs(['search space',] 'current state parameters'){
  	if('reach of terminal state') return value;
  	return dfs('next state parameters')+1;
}
OJ例题：岛屿的最大面积

岛屿数量

const static int maxn=1e3+10;
bool sta[maxn][maxn];
int n,m;
void dfs(vector<vector<char>>& grid,int x,int y){
    if(x<0 || x>=n || y<0 || y>=m || sta[x][y] || grid[x][y]=='0') return;
    sta[x][y]=true;
    dfs(grid,x+1,y);
    dfs(grid,x-1,y);
    dfs(grid,x,y+1);
    dfs(grid,x,y-1);
}
int numIslands(vector<vector<char>>& grid) {
    n=grid.size(),m=grid[0].size();
    int res=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(grid[i][j]=='1'&& !sta[i][j]) {res++;dfs(grid,i,j);}
    return res;
}

岛屿的最大面积

const static int maxn=60;
bool sta[maxn][maxn];
int n,m;
int dfs(vector<vector<int>>& grid,int x,int y){
    if(x<0 || x>=n || y<0 || y>=m || sta[x][y] || grid[x][y]==0) return 0;
    sta[x][y]=true; 
    return dfs(grid,x+1,y)+dfs(grid,x-1,y)+dfs(grid,x,y+1)+dfs(grid,x,y-1)+1;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
    n=grid.size(),m=grid[0].size();
    int res=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(grid[i][j]==1 && !sta[i][j])
                res=max(res,dfs(grid,i,j));
    return res;   
}

[!Tip]
对于DFS搜索空间是网格的情况，往往需要遍历其上下左右四个访问，因此可以创建两个偏量数组dx和dy，通过for循环进行简便表示。

int dx={0,0,1,-1};
int dy={1,-1,0,0};
//void dfs
for(int i=0;i<4;i++){
  	dfs(['search space',] x+dx[i],y+dy[i]);
}

//int dfs
int ans=1;
for(int i=0;i<4;i++){
  	ans+=dfs(['search space',] x+dx[i],y+dy[i]);
}

宽度优先搜索

宽搜本身具备最短路的性质，当边权一致时，可以用来求最短路径。

const int N=1e5+10;
int st[N];
void bfs(){
  	queue<int> q;
  	st[1]=true;
  	q.push(1);
  	while(!q.empty()){
      	int tmp=q.front();
      	q.pop();
      	for(int i=h[i];i!=-1;i=ne[i]){
          	int node=e[i];
          	if(!st[node]){
              	st[node]=true;
              	q.push(node);
            }
        }
    }
}

除法求值

这个题目很好的利用了宽度优先搜索的最短路特性！多个视角（并查集 | Floyd | DFS | BFS）看这道题。

[!Note]
顺便借着这个题目梳理一下图相关题目的做法。
首先，最重要的是能够识别出这题可以用图做。其实也很好判断，图最重要的就是结点与结点之间的关联，若题目能抽象出结点和结点之间的关联，且题目求解的答案也需要利用到结点之间的关系，那么这道题很大程度上就要用图解题。
那么下一步就要思考，答案的求解需要涉及到什么知识。基于图遍历的求解？最短路问题？最小生成树问题？拓扑排序问题？还是二分图问题？这一步就是问题建模的过程，因此相当关键。这需要我们对这些问题所涉及的模板特别熟悉，且能灵活的改动。
确定大体的解题思路之后，就要落足于题目实际。图需要用哪种结构进行存储？邻接矩阵、邻接表、还是结构体数组？这需要根据上一步确定的方法，以及题目数据规模共同敲定。是否需要用到额外的辅助数据结构？堆、队列、集合、哈希表？
最后就是编码的细节。是否需要状态记录？DFS的递归出口，返回值是否正确？数组下标从1开始还是从0开始？

const static int maxn= 30;
double g[maxn][maxn];
bool st[maxn];
unordered_map <string,int> node;
int idx=0;
void init(){
    memset(st,0,sizeof st);
}
double dfs(int x,int y){  //这里用dfs是不合题意的，因为不是最短构造
    if(x==y) return 1;
    st[x]=true;
    for(int i=0;i<idx;i++)
        if(g[x][i] && !st[i]) return dfs(i, y) * g[x][i];
    return -1.0;
}
double bfs(int x, int y) {
    double tmp[maxn];
    for (int i = 0; i < idx; i++) tmp[i] = 1;
    queue<int> q;
    q.push(x);
    st[x] = true;
    while (!q.empty()) {
        int top = q.front();
        q.pop();
        for (int i = 0; i < idx; i++)
            if (!st[i] && g[top][i]) {
                tmp[i] *= tmp[top] * g[top][i];
                st[i] = true;
                q.push(i);
            }
        if (top == y) return tmp[top];
    }
    return -1.0;
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {  //这个题是很明显的需要用邻接矩阵去存储的
    int len=equations.size();
    for(int i=0;i<len;i++){
        if(!node.count(equations[i][0])) {node.insert({equations[i][0],idx++});}
        if(!node.count(equations[i][1])) {node.insert({equations[i][1],idx++});}
        g[node[equations[i][0]]][node[equations[i][1]]] = values[i];
        g[node[equations[i][1]]][node[equations[i][0]]]=1/values[i];
    }
    vector<double> res;
    for(auto item:queries)
        if(node.count(item[0]) && node.count(item[1])){
            init();
            res.push_back(bfs(node[item[0]],node[item[1]]));
        }else res.push_back(-1.0);
    return res;
}

拓扑排序

有向图 | 宽度优先搜索的一种应用

const int N=1e5+10;
int dim[N],q[N],tp[N],n;
bool topsort(){
  	int hh=0,tt=-1,idx=0; // 初始空队列
  	for(int i=1;i<=n;i++) if(!dim[i]) q[++tt]=i; // 将入度为0的元素放入队列中
  	while(hh<=tt){ // 队不空
      	int tmp=q[hh++];  // 取出队头元素
      	tp[idx++]=tmp; // 其实这里也没必要额外开一个tp存储，q中存储的就是拓扑序
      	for(int i=h[tmp];i!=-1;i=ne[i])  // 遍历队头元素的出边
          	if(--d[e[i]]==0) q[++tt]=e[i]; 
    }
  	return tt==n-1;
}

最短路

Dijkstra算法

朴素Dijkstra

基于邻接矩阵存储的算法。

时间复杂度是$O(n^2)$，仅支持求正权边的最短路径。算法时间复杂度与边数无关，适用于稠密图。

算法的基本思想是通过逐步扩展已确定最短路径的顶点集合，从源点开始逐步确定源点到其他顶点的最短路径。Dijkstra算法使用了贪心策略，每次选择当前距离源点最近的顶点进行扩展，直到所有顶点都被扩展。

初始化：将源点的最短路径距离设置为0，其他顶点的最短路径距离设置为正无穷大（或一个足够大的值）。
选择最短路径顶点：从尚未确定最短路径的顶点中选择一个距离源点最近的顶点，将其标记为已确定最短路径。
更新最短路径距离：对于选择的顶点，遍历其所有邻接顶点，如果通过该顶点可以获得更短的路径，则更新邻接顶点的最短路径距离为源点经过选择顶点到该邻接顶点的距离。
重复进行步骤2和步骤3，直到所有顶点都被确定最短路径。

最短路径获取：通过记录每个顶点的前驱节点，可以从目标顶点逆向获取最短路径。

const int N=1e3+10;
int g[N][N],dist[N];
bool st[N]; // g存储每条边的权重，dist存储1号点到其他点的距离，st存储每个节点的最短路径是否确定。
int dijkstra(){
  	memset(dist,0x3f,sizeof dist);
  	dist[1]=0;
  	for(int i=0;i<n-1;i++){ // 遍历剩余节点
      	int d=-1;
      	for(int j=1;j<=n;j++) // 在还未确定最短路的节点中，寻找距离最小的点
          	if(!st[j]&&(d==-1||dist[d]>dist[j])) d=j;
      	for(int j=1;j<=n;j++) // 根据寻找到的节点d更新其他点的距离
          	dist[j]=min(dist[j],dist[d]+g[d][j]);
      	st[d]=true; // 将节点d设置为最短路径确定的点
    }
  	if(dist[n] == 0x3f3f3f3f) return -1;
  	else return dist[n];
}

堆优化Dijkstra

基于邻接表存储的算法。

时间复杂度是$O(mlogn)$，仅支持求正权边的最短路径。算法时间复杂度与边数有关，适用于稀疏图。

typedef pair<int,int> PII;
int h[N],e[N],ne[N],w[N],n,idx,dist[N];
bool st[N]; // st存储每个节点的最短路径是否确定。
int dijkstra(){
  	memset(dist,0x3f,sizeof dist);
  	priority_queue<PII,vector<PII>,greater<PII>>heap;
  	heap.push({0,1}); //插入距离和节点编号
  	while(!heap.empty()){
      	auto d=heap.top();
      	heap.pop();
      	int node=d.second,dis=d.first;
      	if(st[node]) continue;
      	st[node]=true;
      	for(int i=h[node];i!=-1;i=ne[i]){
          	int k=e[i];
          	if(dist[k]>dist[node]+w[i]){
              	dist[k]=dist[node]+w[i];
              	heap.push({dist[k],k});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
  	else return dist[n];
}

Bellman-Ford算法

基于结构体存储的算法。

算法的基本思想是通过不断地松弛边来逐步确定源点到其他所有顶点的最短路径。它使用了动态规划的思想，通过对所有边进行松弛操作，逐渐更新顶点的最短路径估计值，直到达到最优解。

初始化：将源点的最短路径估计值设置为0，其他顶点的最短路径估计值设置为正无穷大（或一个足够大的值）。
进行松弛操作：对图中的每条边进行松弛操作，即根据边的权值更新顶点的最短路径估计值。对于边(u, v)，如果通过 u 可以获得更短的路径，**则更新顶点 v 的最短路径估计值为 dist[u] + weight(u, v)**，其中 dist[u] 表示源点到顶点 u 的最短路径估计值。
重复进行步骤2：重复进行步骤2，执行 V-1 次松弛操作，其中 V 是图中顶点的数量。这样可以确保在最坏情况下，所有的最短路径都能被找到。
检测负权回路：进行第 V 次松弛操作后，如果仍然存在可以进行松弛操作的边，则说明图中存在负权回路，无法得到有效的最短路径。

const int N=1e3+10,M=1e5+10;
int n, m; // n表示点数，m表示边数
int dist[N],backup[N]; // dist[x]存储1到x的最短路距离
struct{ // 边，a表示出点，b表示入点，w表示边的权重
    int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ ){
      	memcpy(backup,dist,sizeof dist);
        for (int j = 0; j < m; j ++ ){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
           	dist[b] = min(dist[b],backup[a]+w);
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    else return dist[n];
}

SPFA算法 (Shortest Path Faster Algorithm)

基于邻接表存储的算法。

SPFA算法通过不断地松弛边来逐步确定源点到其他所有顶点的最短路径。与Bellman-Ford算法不同的是，SPFA算法使用了一个队列来优化松弛操作的选择，减少了不必要的松弛次数，从而提高了算法的效率。

创建一个队列，将源点加入队列，并初始化源点到其他所有顶点的距离为无穷大（或一个足够大的值），源点到自身的距离为0。
当队列不为空时，执行以下操作：
a. 从队列中取出一个顶点作为当前顶点。
b. 遍历当前顶点的所有邻接顶点：如果通过当前顶点可以获得更短的路径，则更新邻接顶点的距离，并将其加入队列（如果尚未在队列中）。
当队列为空时，算法结束。此时，源点到所有其他顶点的最短路径长度已确定。

const int N=1e3+10;
int h[N],w[N],e[N],ne[N],dist[N],idx,n;       // 邻接表存储所有边
bool st[N];     // 存储每个点是否在队列中

int spfa(){ // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
    memset(dist, 0x3f, sizeof dist);dist[1] = 0;
    queue<int> q; q.push(1); st[1] = true;
    while (!q.empty()){
        auto node = q.front();
        q.pop();
        st[node] = false; //当一个点从队列中出队时，需要将对应的 st 数组中的标记设置为 false，表示该点不在队列中了。
        for (int i = h[node]; i != -1; i = ne[i]){
            int k = e[i];
            if (dist[k] > dist[node] + w[i]){
                dist[k] = dist[node] + w[i];
                if (!st[k]){  // 如果队列中已存在j，则不需要将j重复插入
                    q.push(k);st[k] = true;
                }
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

判断负环：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

const int N=1e3+10;
int h[N],w[N],e[N],ne[N],dist[N],cnt[N],idx,n;       // 邻接表存储所有边
bool st[N];     // 存储每个点是否在队列中

int spfa(){ // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
    queue<int> q;
  	for(int i=1;i<=n;i++) {st[i]=true;q.push(i);}
    while (!q.empty()){
        auto node = q.front();
        q.pop();
        st[node] = false; //当一个点从队列中出队时，需要将对应的 st 数组中的标记设置为 false，表示该点不在队列中了。
        for (int i = h[node]; i != -1; i = ne[i]){
            int k = e[i];
            if (dist[k] > dist[node] + w[i]){
                dist[k] = dist[node] + w[i];
              	cnt[k]=cnt[node]+1;
              	if(cnt[k]>=n) return true;
                if (!st[k]){  // 如果队列中已存在j，则不需要将j重复插入
                    q.push(k);st[k] = true;
                }
            }
        }
    }
    return false;
}

Floyd算法

基于邻接矩阵存储的算法。

Floyd算法是一种经典的动态规划算法，用于求解所有节点对之间的最短路径。其基本思想是通过中转节点逐步更新路径，从而找到最短路径。

初始化距离矩阵：将每条边的权重存储在距离矩阵 dist 中，如果两个节点之间没有直接的边相连，则将其距离设置为一个较大的值（通常为无穷大）。
通过中转节点逐步更新路径：对于每一个节点k，考虑从节点i到节点j的路径，判断是否存在通过节点k的更短路径。如果存在，则更新距离矩阵中节点i到节点j的距离为节点i到节点k的距离加上节点k到节点j的距离。
重复执行第2步，直到所有节点对之间的最短路径都被计算出来。
最终，距离矩阵 dist 中存储的就是所有节点对之间的最短路径。

const int INF=0x3f3f3f3f,N=1e3+10;
int d[N][N];
void init(){
		for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0; else d[i][j] = INF;
}
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd(){
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

最小生成树

Prim算法

Prim算法是基于顶点的贪心算法。

给定一个连通的无向加权图$G = (V, E)$，其中$V$是顶点集合，$E$是边集合，每条边有一个权重 $w(u, v)$。Prim算法从一个初始顶点开始，逐步扩展生成树，每次选择具有最小权重的边并且该边连接了一个新的顶点。

初始化：
- 选择一个初始顶点，将其加入生成树。
- 创建一个集合$T$，用于存储生成树中的顶点，初始时包含初始顶点。
- 对于每个顶点，记录从$T$到该顶点的最小边权重（使用优先队列或最小堆来有效地获取最小边）。
扩展生成树：
- 从优先队列中选择权重最小的边，该边连接了一个在$T$中的顶点和一个不在$T$中的顶点。
- 将新顶点加入集合$T$。
- 更新优先队列中与新顶点相连的边的权重（如果这些边的权重比当前记录的最小权重小）。
重复：
- 重复上述步骤，直到所有顶点都被包含在生成树中。

朴素Prim

int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
            		t = j;
        if (i && dist[t] == INF) return INF;
        if (i) res += dist[t];
        st[t] = true;
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

Kruskal算法

kruskal基于贪心策略，通过逐步选择权重最小的边来构建生成树。

给定一个连通的无向加权图$G = (V, E)$，其中$V$是顶点集合，$E$是边集合，每条边有一个权重 $w(u, v)$。Kruskal算法通过选择不形成环且权重最小的边来构建最小生成树。

初始化：
- 创建一个空集合$T$用于存储最小生成树中的边。
- 将图中的所有边按权重从小到大排序。
选择边：
- 从权重最小的边开始，逐条检查这些边。
- 如果当前边连接的两个顶点属于不同的连通分量（即不形成环），则将该边加入集合$T$。
- 使用并查集数据结构来高效地检测和合并连通分量。
重复：
- 重复上述步骤，直到集合$T$中包含$V-1$条边为止，此时$T$就是图的最小生成树。

int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组
struct Edge{    // 存储边
    int a, b, w;
    bool operator< (const Edge &e)const{
    		return w < e.w;
		}
}edges[M];
int find(int x){ // 并查集核心操作
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int kruskal(){
    sort(edges, edges + m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if (a != b){   // 如果两个连通块不连通，则将这两个连通块合并
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }
    if (cnt < n - 1) return INF;
    return res;
}

二分图

染色法

只要图不含有奇数个环，那么一定能被染色。

选择一个起始节点作为初始顶点，并将其染成一种颜色（例如红色）。
对于起始节点的每个邻居节点，将其染成与起始节点不同的颜色（例如蓝色）。
递归或迭代地对每个邻居节点进行步骤2，将其邻居节点的邻居节点染色，直到所有节点都被染色。
在染色的过程中，如果发现任意两个相邻节点被染成相同的颜色，说明该图不是二分图。
如果所有节点都被正确染色，并且没有相邻节点被染成相同的颜色，那么该图是二分图。

int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if (color[j] == -1)
        		if (!dfs(j, !c)) return false;
        else if (color[j] == c) return false;
    }
    return true;
}
bool check(){
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
        if (!dfs(i, 0)){
        		flag = false;
        		break;
    		}
    return flag;
}

匈牙利算法

匈牙利算法是一种解决最大匹配问题的经典算法。它用于在二分图中找到一个最大的匹配，即将尽可能多的边匹配起来。匈牙利算法基于增广路径的思想，其基本思路是通过不断寻找增广路径来增加匹配的边数，直到无法找到增广路径为止。

初始化匹配：将所有的匹配边置为空。
对于二分图的每个未匹配顶点，尝试找到增广路径。
寻找增广路径：从一个未匹配的顶点开始，使用深度优先搜索或广度优先搜索的方法，依次访问与当前顶点相邻的未匹配顶点。如果找到一个未匹配的顶点，则将路径中的边进行翻转，即将原本匹配的边变为非匹配边，将原本非匹配的边变为匹配边。
重复步骤3，直到无法找到增广路径为止。
最终，得到的匹配即为二分图的最大匹配。

int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过
bool find(int x){
    for (int i = h[x]; i != -1; i = ne[i]){
        int j = e[i];
        if (!st[j]){
            st[j] = true;
            if (match[j] == 0 || find(match[j])){
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ ){
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}