快读模板

void read(long long &x){ 
    long long f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

~垃圾~排序

快速排序

int split(int l,int r){
    swap(a[l],a[(l+r)/2]);
    int t=a[l];//以中间作基准
    while(l<r){
        while(a[r]>t&&l<r)r--;//在左边找大的
        if(l<r)a[l++]=a[r];//大的换到右边
        while(a[l]<t&&l<r)l++;//在右边找小的
        if(l<r)a[r--]=a[l];//小的换到左边
    }
    a[l]=t;
    return l;
}
void q_sort(int l,int r){
    if(l>=r)return;
    int mid=split(l,r);
    q_sort(l,mid-1);
    q_sort(mid+1,r);
}

归并排序

void merge(int L1,int R1,int L2,int R2){
    int az=L1,bz=L2,cz=L1;
    int c[100010]={};
    while(az<=R1&&bz<=R2){
        if(a[az]>a[bz])c[cz++]=a[bz++];
        else c[cz++]=a[az++];
    }
    while(az<=R1)c[cz++]=a[az++];
    while(bz<=R2)c[cz++]=a[bz++];
    for(int i=L1;i<=R2;i++)a[i]=c[i];
}
void msort(int l,int r){
    if(l>=r)return;
    int mid=(l+r)/2;
    msort(l,mid);
    msort(mid+1,r);
    merge(l,mid,mid+1,r);
}

上二分学的~唯一有用的~东西：

lower_bound(首地址，尾地址，值);//第一个大于等于值的下标
upper_bound(首地址，尾地址，值);//第一个大于值的下标
nth_element(数组名,数组名+第k小元素,数组名+元素个数)

~每次都会写错~的双端队列和冲锋枪：

deque<int> dq;//声明一个队列dq，用于存储int型变量
    dq.push_front(x);//将表达式x的值插入队首 
    dq.push_back(x);//将表达式x的值插入队尾
    dq.pop_front();//弹出队首元素
    dq.pop_back();//弹出队尾元素
    dq.clear();//清空队列 
    x=dq.front();//获取队首元素的值，并赋值给x
    x=qu.back();//获取队尾元素的值，并赋值给x
    dq.empty();//判断队列dq是否为空，若为空则返回true
    dq.size();//返回队列dq中存储的元素的个数 

vector<int> v;  // 声明一个向量 v，用于存储 int 型变量
    v.push_back(x); // 将表达式 x 的值存入向量末尾
    v.pop_back();   // 删除向量的末尾元素
    x = v.front();  // 获取首元素的值，并赋给变量 x
    x = v.back();   // 获取尾元素的值，并赋给变量 x
    v.empty();      // 判断向量 v 是否为空，若为空则返回 true
    v.size();   // 返回向量 v 中存储的元素的个数
    v.clear();      // 清空向量

我最讨厌的高精（函数包装，复制即可食用）：

string add(string s1,string s2){//加法
    long long a[10010]={},b[10010]={},c[10010]={};
    long long la=s1.length(),lb=s2.length(),lc=max(la,lb),x=0;
    string ans="";
    for(int i=0;i<la;i++)a[i]=s1[la-i-1]-'0';
    for(int i=0;i<lb;i++)b[i]=s2[lb-i-1]-'0';
    for(int i=0;i<lc;i++){
        c[i]=a[i]+b[i]+x;
        x=c[i]/10;
        c[i]=c[i]%10;
    }
    if(x)c[lc++]=1;
    for(int i=lc-1;i>=0;i--)ans+=(c[i]+'0');
    return ans;
}
string sub(string s1,string s2){//减法
    long long a[10010]={},b[10010]={},c[10010]={};
    long long la=s1.length(),lb=s2.length(),lc=max(la,lb),x=0,f=0;
    string ans="";
    if((s1 < s2 && s1.length() == s2.length()) || s1.length() < s2.length()){
        f=1;
        string t=s1;
        s1=s2;
        s2=t;
        swap(la,lb);
        cout<<'-';
    }
    for(int i=0;i<la;i++)a[i]=s1[la-i-1]-'0';
    for(int i=0;i<lb;i++)b[i]=s2[lb-i-1]-'0';
    for(int i=0;i<lc;i++){
        c[i]=a[i]-b[i]-x;
        if(c[i]<0){
            x=1;
            c[i]+=10;
        }else x=0;
    }
    while(c[lc-1]==0&&lc>1)lc--;
    for(int i=lc-1;i>=0;i--)ans+=(c[i]+'0');
    return ans;
}
string mul(string s1,string s2){//乘法
    long long a[10010]={},b[10010]={},c[20010]={};
    long long la=s1.length();
    long long lb=s2.length();
    long long lc=la+lb;
    string ans="";
    for(int i=0;i<la;i++) a[i]=s1[la-1-i]-'0';
    for(int i=0;i<lb;i++) b[i]=s2[lb-1-i]-'0';
    for(int i=0;i<la;i++){ 
        for(int j=0;j<lb;j++){
            c[i+j]+=a[i]*b[j];
            c[i+j+1]+=c[i+j]/10;
            c[i+j]%=10;
        }
    }
    while(c[lc-1]==0&&lc>1){
        lc--;
    }
    for(int i=lc-1;i>=0;i--) ans+=(c[i]+'0');
    return ans;
}
string div(string s,int b){//高精除低精
    int n,a[101000],c[101000],la,lc;
    la=s.length(),lc=0;
    for(int i=0;i<la;i++)a[i]=s[i]-'0';
    long long x=0;
    string ans="";
    for(int i=0;i<la;i++){
        c[i]=(x*10+a[i])/b;
        x=(x*10+a[i])%b;
    }
    while(c[lc]==0&&lc+1<la) lc++;
    for(int i=lc;i<la;i++)ans+=(c[i]+'0');
    return ans;
}
//高精除高精忒麻烦了懒得写

七类~费脑子~的贪心(sort!)

1. 最优装载 (P2676)

2. 部分背包 (P2240)

3. 乘船问题 (P1094)

4. 交换类贪心 (P1080)

5. 不相交区间 (P1803)

6. 区间选点 (P1250)

7. 区间覆盖 (P1589)

~超级费脑子~的动态规划

重点：状态转移方程！

最长上升子序列方程：if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1)

最长公共子序列方程：if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1,else dp[i][j]=max(dp[i-1][j],dp[i][j-1])

最大子段和方程：dp[i]=max(a[i],dp[i-1]+a[i])

~前缀差分懒得写~

补充：Dilworth 定理=最长上升的子序列的个数=最长不下降子序列的条数

背包

01背包模板：

//n=物品总数,c=背包容量,w[i]=第i个物品的重量,v[i]=第i个物品的价值 
    for(int i=1;i<=n;i++){//前i个物品 
        for(int j=c;j>=w[i];j--){//重量为j 
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//dp[j](dp[i][j])=前i个物品背包重量为j的最大价值 
        }
    }

对于一个物品，只有选或不选两种情况不选就是前i-1个物品加起来的价值,那么就等于dpj，而选的话就是前i-1个物品加上第i个物品的价值, 那么就等于dp[j]+vi，但是在i-1个物品中背包重量为j的情况下背包可能被装满了,所以要牺牲w[i]的空间来装第i个物品,那么背包重量就得改成j-w[i],整个就是dp[j-w[i]]+vi，选或不选两种情况求个最大值就行了，所以状态转移方程就是dp[j]=max(dp[j],dp[j-w[i]]+v[i]) 而j的循环是倒着写的，是因为倒着写每一个重量不会被多次访问

完全背包模板：

for(int i=1;i<=n;i++){//前i个物品 
        for(int j=w[i];j<=c;j++){//重量为j 
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }

完全背包就是01背包的变形，你可以一直选这一个物品.既然可以一直选，那循环就要正着写，因为前面的状态可以被多次访问

多重背包模板：

for(int i=1;i<=n;i++){//前i种物品 
        for(int j=c;j>=w[i];j--){//重量为j 
            for(int k=0;k<=t[i]&&k*w[i]<=j;k++){//第i种物品选k个,t[i]表示第i种物品有几个 
                dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
            }
        }
    }

多重背包也是01背包的变形，种选和不选两种情况变成了选几个 ，所以要用一个循环k来表示选几个

~巨恶心~的树

树的定义

树，是由n(n\ge0)n(n≥0)个结点构成的非线性，具有层次关系的有限集合。

当n=0n=0时，这棵树被称为空树。

当n\ne0n​=0时，这棵树被称为非空树，有几个特点：

1. 树中仅有一个被称为根的结点
2. 除根节点外，其余结点可以划分成多个不相交子树

树的一些术语

• 子结点：对于某一个结点的子树的根叫做子节点
• 父结点：对于他的子节点来说叫做父节点
• 兄弟结点：具有相同父结点的结点互称为兄弟结点
• 结点的度：其子节点的个数
• 树的度：所有结点的度的最大值
• 叶结点：度为0的结点，也就是没有子节点的结点
• 分支结点：度不为0的结点，也就是有子节点的结点
• 结点层次：根结点在第一层，其他结点=其父结点+1
• 树的深度：所有结点的最大层数
• 结点高度：叶结点高度为1，其他节点=max(其所有子节点高度)+1
• 树的高度：等于根的高度
• 路径与路径长度：对于两个结点n和m之间所经过的结点称为结点n到m的路径，其长度为该路径包含的边的数量

~难上加难~的二叉树

性质

• 一棵二叉树第ii层的最大结点数为2^{i-1},i>12i**−1,i>**1
• 一颗深度为ii的最大结点总数为2^i-1,i>12i**−1,i>**1
• 对任何非空的二叉树，若n_0n0​表示叶节点的个数，n_2n2​是度为2的非叶节点的个数，那么两者满足关系：n_0=n_2+1n0​=n2​+1

遍历（dfs）

先序：根节点\to**→左子树\to→**右子树

code：

void dfs(int x){
    if(x==0)return;
    cout<<x<<" ";
    dfs(a[x].l);
    dfs(a[x].r);
}

中序：左子树\to**→根节点\to→**右子树

code：

void dfs(int x){
    if(x==0)return;
    dfs(a[x].l);
   cout<<x<<" ";
    dfs(a[x].r);
}

后序：左子树\to**→右子树\to→**根节点

code：

void dfs(int x){
    if(x==0)return;
    dfs(a[x].l);
    dfs(a[x].r);
   cout<<x<<" ";
}

二叉搜索树

定义：左子树<(\le)<(≤)根节点<(\le)<(≤)右子树

中序遍历二叉搜索树是非下降的

图（吐）论

图的定义

一个图G是一个二元组，即序偶<V,E>，或记作G=<V,E> ，其中V是有限非空集合，称为G的顶点集,V中的元素称为顶点或结点；E称为 G的边的集合，所有的边ei都属于E，都有v中的结点与之对应，称ei为 G的边。

图的基本概念/术语

• 无向图：每条边都是无向边的图。

• 有向图：每条边都是有向边的图。

• 平凡图：仅有一个结点而没有边构成的图。

• 自环：若一条边所关联的两个结点重合，则称此边为自环。

• 邻接：关联于同一条边的两个点 和 称为邻接的；关联于同一个点的两条边 和 是邻接的（或相邻的）。

• 路径:若顶点，则称从顶点vi0到vin存在一条路径。

• 路径长度：路径上的边数。

• 简单路径：若路径上的顶点除vi0和vin可以相同外，其它顶点都不相同。

• 回路或环：起点和终点相同的简单路径。

• 根：有向图中，若存在一顶点v，从该顶点有路径可以 到图中其它所有顶点，则称此有向图为有根图，v 称为图的根。

• 完全图：若图中各个顶点都与除自身外的其他顶点有关系，这样的无向图称为完全图（如图a)）。同时，满足此条件的有向图则称为有向完全图（图b)）。## 图的存储方式

  邻接矩阵

一般用一个二维数组mp来存储

mp[i][j]表示i和j之间有没有边

//无向图
#include<bits/stdc++.h>
using namespace std;
int mp[1010][1010];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        mp[x][y]=1;//x和y之间有一条边
        mp[y][x]=1;//无向图，反着再存
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<mp[i][j]<<" ";//如果i与j相邻，则输出1，否则输出0
        }
        cout<<endl;
    }
    return 0;
}

邻接表

一般用二维vector存储

v[x]存的是与x相邻的点

v[x][y]表示x与y相邻

邻接表可以方便求出每个点的出度

#include<bits/stdc++.h>
using namespace std;
vector<int>mp[1010];
int n,m,;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        mp[x].push_back(y);//x与y之间有一条边，也就是x与y相邻
        mp[y].push_back(x);//无向图再反着存
    }
    for(int i=1;i<=n;i++){
        sort(mp[i].begin(),mp[i].end());
        cout<<mp[i].size()<<" ";//i的出度
        for(int j=0;j<mp[i].size();j++){
            cout<<mp[i][j]<<" ";//与i连接的点
        }
        cout<<endl;
    }

    return 0;
}