using namespace std;
int main(){

}

数据类型：
整数： short,int,long long
浮点数： float,double
字符：char
布尔：bool
赋值运算符：
=，+=，-=，/=，*=
保留小数位：
cout<<fixed<<setprecision(3)<<a; a保留三位小数
printf("%.3f",a)  a保留三位小数
printf("%03d",a)  a不足三位前面补零
printf("%-d",a)   a向左对齐
abs(a) 对整数a取绝对值
fabs(a) 对小数取绝对值
ceil(a) 对a向上取整
floor(a) 对a向下取整
setw(5) 设置宽域
单分支： if(条件成立) {执行}
双分支：if(条件成立){执行}else{条件不成立执行}
可范围多分支：if(条件1成立){执行}else if（条件2成立）{执行} else{其他情况}
确定值：
switch(){
	case 1:情况1执行，break;
	case 2:情况2执行，break;
	case 3:情况3执行，break;
	default:
			默认情况
}

循环：
for(int i = 1;i<=10;i++){ 1开始到10总共执行10次
	循环体
}
while(条件成立){
	循环
	if(不成立){
		break;跳出循环
	}
}

do{
	循环体
}while(循环成立执行)

for(int i = 1;i<=10;i++){
	for(int j = 1;j<=10;j++){
		循环体1
	}
}
先里层在读外层
数组：
数据类型 数组名[长度]
数组初始化：
int arr[100]={1,2,3,4}
memset(数组名，初始值，sizeof(数组名))
数组排序：
sort(数组名+起点，数组名+终点+1)

排序算法：
选择排序：时间复杂度（O(n*n),不稳定排序）
 每一轮选择最小的元素，和已排好的序列后一个进行交换
for (int i = 0; i < n - 1; i++) {
	int minIndex = i;
	for (int j = i + 1; j < n; j++) {
	   if (arr[j] < arr[minIndex]) {
 			minIndex = j;
 	   }
       }
	swap(arr[minIndex], arr[i]);
 }
冒泡排序：每一次如果前一个大于后一个进行交换，选出最大值（O(n*n),稳定排序）
 for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                   }
        }
}
插入排序： 当前i 的值和前面进行比较如果比前面小，不断交换，直到不能交换为止（O(n*n),稳定排序）
	for (int i=2;i<=n;i++)   {
		int j,k=a[i];        
		for (j=i-1;j>0;j--){
			if (a[j]>k){
				a[j+1]=a[j];   	
			} else{
				break; 
                       }
		}
		a[j+1]=k;       
	}
快速排序：找基准点（首位/末位）,每次执行比基准点小的放左边，大的放右边（O(n*logn)）

邻接矩阵：
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int g[N][N];
int n,m;
int main(){
	cin>>n>>m;
	for(int i = 1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u][v]= g[v][u]=1;
	}
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			cout<<g[i][j]<<" ";
		}
		cout<<'\n';
	}
}
邻接表
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
vector<int> g[N]; // 邻接表
int n,m;
int main(){
	cin>>n>>m;
	for(int i = 1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i = 1;i<=n;i++){
		cout<<i<<":";
		for(int j = 0;j<g[i].size();j++){
			cout<<g[i][j]<<" ";
		}
		cout<<'\n';
	}
}

字符数组：处理一串字符避免空格隔开输入问题
字符数组定义：char 数组名[长度]
注意： 字符数组最末端会添加'\0',可以用于识别字符数组末端
获取一整行字符数组（可包括空格）：cin.getline(数组名，获取最大长度)
字符数组遍历：
for(int i = 0;a[i]!='\0';i++){
	cout<<a[i]<<" ";
}
for(int i = 0;i<strlen(a);i++){
	cout<<a[i]<<" ";
}
获取字符数组长度：strlen(数组名)

字符串：
字符串：和字符数组类似，区别不需要开辟空间，字符串末端没有加/0
字符串定义：string 字符串名
情况1： 如果输入的是不包含空格 cin>>str
情况2：如果输入包括空格： getline(cin,str)；
字符串遍历：
cout<<a<<endl; // 整行输出
for(int i = 0;i<a.size();i++){  // 遍历挨个输出
	cout<<a[i]<<" ";
}
获取字符串长度：str.size() / str.length()
string k = s.substr(3,3); 
// 从3的位置截取子串长度为3
int k = a.find("uu");  // 查看子串uu在主串哪个位置
s.append("str"); // += 在s后面追加strs.find("str") ; // 在s字符中找str 第一个出现的位置
s.rfind("str"); // 在s字符串中找str最后一个出现的位置
s.find_first_of("0123456789"); // 查找第一个数字字符，未找到返回 stringnpos
s.find_last_of("0123456789"); // 最后一个位置出现数字
s.replace(0, 5, "hi"); // 从0开始长度为5替换成hi

字符判断：
        char m = 'A';
	char k ='a';
	char p = '0';
	char h = '&';
	if(isupper(m)){ // 判断是否为大写
		cout<<"大写";
	}
	if(islower(k)){ // 判断是否为大写
		cout<<"小写";
	}
	if(isdigit(p)){ // 判断是否为数字
		cout<<"是数字";
	}
	if(isalpha(h)){ // 判断是否为字母
		cout<<"&是字母";
	}else{
		cout<<"&不是字母";
	}

字符串匹配算法：
#include<bits/stdc++.h>
using namespace std;

string a = "ABAABC"; // 模式串
string b = "ABAABABAABC"; // 主串
// 获取next数组
vector<int> getnext(string &a) {
    int la = a.size();
    vector<int> next(la, 0);
    int j = 0;
    for (int i = 1; i < la; i++) { 
        while (j > 0 && a[i] != a[j]) {
            j = next[j - 1];
        }
        if (a[i] == a[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}
// 求值
int kmp(vector<int>& next, string &b) {
    int i = 0, j = 0; 
    int n = b.size();
    int m = a.size();
    while (i < n) {
        if (a[j] == b[i]) {
            i++;
            j++;
        } else if (j > 0) {
            j = next[j - 1];
        } else {
            i++;
        }
        if (j == m) {
            return i - j; 
        }
    }
    return -1;
}

int main() {
    vector<int> v = getnext(a);
    for (int x : v) {
        cout << x << " ";
    }
    int k = kmp(v, b);
    if (k != -1) {
        cout << k << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
/*
GCD(6,12)
12/6 = 2....0
输出除数，如果余数=0
24 16
24 / 16 = 1.....8
16/8 = 2....0
除数变成被除数，余数变成除数，余数=0停止循环
输出除数
*/
int _GCD(int a,int b){ // 迭代
	while(b!=0){
		int temp = b;
		b = a%b;
	    a = temp;
	}
	return a;
}
// 递归
int GCD(int a,int b){
	return b==0?a:GCD(b,a%b);
}
// 最小公倍数 
int LCM(int a,int b){
	return a*b/GCD(a,b);
}
// 幂运算
long long nomer_v(int a, int b){
	int res  = 1;
	for(int i = 1;i<=b;i++){
		res *= a;
	} 
	return res;
}
// 求幂函数快速方式
long long fase_p(int a,int b){
	long long res = 1;
	long long base = a;
	while(b>0){
		if(b%2 == 1){
			res*= base;
		}
		base*=base;
		b/=2;
	}
	return res;	
}
// 带mod 取模快速幂
long long mod_power(int a,int b,int mod){
	long long res =1;
	a%=mod;
	while(b>=0){
		if(b%2==1){
			res = (res*a)%mod;
		}
		a = (a*a)%mod;
	}
	return res;
}

int main(){
	int a,	b;
	cin>>a>>b;
	int k = mod_power(a,b,1000);

	cout<<k;
}

完美匹配算法KM
int match[N];       // 右点匹配了哪个左点
int va[N], vb[N];   // 标记是否在交替路中
LL la[N], lb[N];    // 左顶标, 右顶标
LL w[N][N], d[N];   // 维护更新的delta值

bool dfs(int x) {
    va[x] = 1; // x在交替路中
    for (int y = 1; y <= n; y++) {
        if (!vb[y]) {
            if (la[x] + lb[y] - w[x][y] == 0) { // 相等子图
                vb[y] = 1; // y在交替路中
                if (!match[y] || dfs(match[y])) {
                    match[y] = x; // 配对
                    return 1;
                }
            } else { // 不是相等子图则记录最小的d[y]
                d[y] = min(d[y], la[x] + lb[y] - w[x][y]);
            }
        }
    }
    return 0;
}

// 初始化权重矩阵 w
// w[x][y] = -INF; // x,y无边
// w[x][y] = z;    // x,y有边

LL KM() {
    // 左顶标取i的出边的最大边权
    for (int i = 1; i <= n; i++) la[i] = -INF;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            la[i] = max(la[i], w[i][j]);

    for (int i = 1; i <= n; i++) lb[i] = 0;

    for (int i = 1; i <= n; i++) {
        while (true) { // 直到左点找到匹配
            fill(va + 1, va + n + 1, 0);
            fill(vb + 1, vb + n + 1, 0);
            fill(d + 1, d + n + 1, INF);

            if (dfs(i)) break;

            LL delta = INF;
            for (int j = 1; j <= n; j++)
                if (!vb[j]) delta = min(delta, d[j]);

            for (int j = 1; j <= n; j++) { // 修改顶标
                if (va[j]) la[j] -= delta;
                if (vb[j]) lb[j] += delta;
            }
        }
    }

    LL res = 0;
    for (int i = 1; i <= n; i++)
        res += w[match[i]][i];
    return res;
}

结构体笔记：
#include <bits/stdc++.h>
using namespace std;
struct Student{
	string name;
	int xuehao;
	int math;
	int china;
	float english;
	float total;  // 总分
}s1,s[49]; // s1代表是一名学生 ,s[49] 一个班有49名
//Student s2;
//Student sk[90];
bool cmp(Student k, Student k1 ){ // k 
	if(k.total == k1.total){
		return k.math < k1.math; // 按照数学成绩从大到小
	}
	return k.total>k1.total;    //  前一名学生总分>后一名学生总分
}
int main(){
	// 对s1这名学生添加信息
	for(int i = 1;i<=5;i++){
		cin>>s[i].name>>s[i].xuehao>>s[i].math>>s[i].china>>s[i].english;
		s[i].total = s[i].math+s[i].china+s[i].english;
	}
	sort(s+1,s+6,cmp);  // cmp用来自定义规则
	for(int i = 1;i<=5;i++){
		cout<<"姓名："<<s[i].name<<" 成绩： "<<s[i].total<<endl;
	}
//	cout<<s1.name<<" "<<s1.xuehao <<" "<<s1.math<<" "<<s1.china<<" "<<s1.english;

	
	
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int ch[N][26],cnt[N],idx;
int ne[N];
void insert(char *s){
	int p=0;
	for(int i = 0;s[i];i++){
		int j = s[i]-'a';
		if(!ch[p][j])ch[p][j]=++idx;
		p = ch[p][j];
	}
	cnt[p]++;
}
void build() { // 用 BFS 构造 AC 自动机
    queue<int> q;
    // 初始化，把根节点的儿子们入队
    for (int i = 0; i < 26; i++) {
        if (ch[0][i]) {
            q.push(ch[0][i]);
        }
    }
    
    // 只要队不空
    while (q.size()) {
        int u = q.front(); // 节点 u 出队
        q.pop();
        
        // 枚举 u 的 26 个儿子
        for (int i = 0; i < 26; i++) {
            int v = ch[u][i]; // u 的第 i 个儿子
            
            if (v) { // 1. 若儿子存在
                // 则爹帮儿子建回跳边（失败指针）
                ne[v] = ch[ne[u]][i];
                // 并把儿子入队
                q.push(v);
            } else { // 2. 若儿子不存在
                // 则爹自建转移边
                ch[u][i] = ch[ne[u]][i];
            }
        }
    }
}
int query(char *s) {
    int ans = 0; // 初始化答案，用于统计模式串出现总次数
    
    // 遍历主串 s 的每个字符
    for (int k = 0, i = 0; s[k]; k++) {
        // 1. i指针走主串对应的节点：沿着树边或转移边走，保证不回退
        // 根据当前字符 s[k] 计算转移边索引，从当前节点 i 移动到下一个节点
        i = ch[i][s[k] - 'a'];
        
        // 2. j指针沿着跳边搜索模式串：从当前节点走到根节点
        // 把当前节点中的所有后缀模式串一一网打尽，保证不漏解
        // ~cnt[j] 等价于 cnt[j] != -1，用于判断该模式串是否已被统计过
        for (int j = i; j && ~cnt[j]; j = ne[j]) {
            // 累加当前节点的模式串计数到答案中
            ans += cnt[j];
            // 将当前节点标记为已访问，避免重复统计（设为 -1）
            cnt[j] = -1;
        }
    }
    
    // 3. 扫描完主串，返回答案
    return ans;
}