一、头文件

#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<math.h>
using namespace std;

注：math.h中，abs(x)求整数x绝对值，
fabs(x)求double型x绝对值,
ceil(x)取上整，floor(x)取下整，
pow(x,y) x的y次方，sqrt(x)开根
fabs、ceil、floor、pow、sqrt均返回double型

二、排序

1、快速排序

void quickSort(int A[],int left,int right){     //主。
    if(left<right){
        int pos = Partition(A,left,right);
        quickSort(A,left,pos-1);
        quickSort(A,pos+1,right);
    }
}

int Partition(int A[],int left,int right){      //快排的一趟。
    int temp = A[left];
    while(left<right){
        while (left<right && A[right]>temp) right--;
        A[left] = A[right];
        while(left<right && A[left]<=temp) left++;
        A[right] = A[left];
    }
    A[left] = temp;
    return left;
}

三、二叉树

1、存储结构与基本操作

struct node{
    int data;
    node* lchild;
    node* rchild;
};

node* newNode(int v){   //生成新结点，v为结点权值
    node* Node = new node;
    Node->data = v;
    Node-> lchild = Node->rchild = NULL;
    return Node;
}

void search(node* root,int x,int newdata){  //查找值为x的所有结点，并把它们的值修改为newdata
    if(root == NULL){
        return;
    }
    if(root->data == x){
        root->data = newdata;
    }
    search(root->lchild,x,newdata);
    search(root->rchild,x,newdata);
}

void insert(node* &root,int x){ //插入值为x的新结点，查找失败的位置即插入位置，注意引用
    if(root == NULL){
        root = newNode(x);
        return;
    }
    if(x应该插在左子树){
        insert(root->lchild,x);
    }
    else{
        insert(root->rchild,x);
    }
}

node* Create(int data[],int n){ //创建二叉树，插入的数据在数组中
    node* root = NULL;
    for(int i = 0; i < n; i++){
        insert(root,data[i]);
    }
    return root;
}

2、遍历

void preorder(node* root){  //先序遍历 根左右
    if(root == NULL){
        return;
    }
    visit(root);
    preorder(root->lchild);
    preorder(root->rchild);
}

void inorder(node* root){   //中序遍历 左根右
    if(root == NULL){
        return;
    }
    inorder(root->lchild);
    visit(root);
    inorder(root->rchild);
}

void postorder(node* root){ //后序遍历 左右根
    if(root == NULL){
        return;
    }
    postorder(root->lchild);
    postorder(root->rchild);
    visit(root);
}

void LayerOrder(node* root){    //层序遍历，为记录结点所在层数，在二叉树结构体中添加 int layer;
    queue<node*> q;
    root->layer = 1;
    q.push(root);
    while(!q.empty()){
        node* now = q.front();
        q.pop();
        visit(now);
        if(now->lchild != NULL){
            now->lchild->layer = now->layer + 1;
            q.push(now->lchild);
        }
        if(now->rchild != NULL){
            now->rchild->layer = now->layer + 1;
            q.push(now->rchild);
        }
    }
}

node* create(int preL,int preR,int inL,int inR){    //给定先序遍历序列pre[]、中序遍历序列in[]，重建二叉树。[preL,preR]为先序序列区间，[inL,inR]为中序序列区间。
    if(preL > preR){
        return NULL;
    }
    node* root = new node;
    root->data = pre[preL];
    int k;
    for(k = inL; k <= inR; k++){
        if(in[k] == pre[preL]){
            break;
        }
    }
    int numLeft = k - inL;
    root->lchild = create(preL + 1,preL + numLeft,inL,k-1);
    root->rchild = create(preL + numLeft + 1,preR,k + 1,inR);
    return root;
}

四、树相关

1、静态存储结构与基本操作

struct node{
    int data;
    vector<int> child;
} Node[maxn];

//新建一个结点
int index = 0;
int newNode(int v){
    Node[index].data = v;
    Node[index].child.clear();
    return index++;
}

2、遍历

void PreOrder(int root){    //树的先根遍历  根 子树，注：递归边界隐含在for循环的结束条件中，但是调用传入的root不能是空结点。
    visit(Node[root]);
    for(int i = 0; i < Node[root].child.size(); i++){
        PreOrder(Node[root].child[i]);
    }
}

void LayerOrder(int root){  //树的层序遍历，为记录结点所在层数，在树的结构体中添加 int layer;
    queue<int> Q;
    Q.push(root);
    Node[root].layer = 0;
    while(!Q.empty()){
        int front = Q.front;
        Q.pop();
        visit(Node[front]);
        for(int i = 0; i < Node[front].child.size(); i++){
            int child = Node[front].child[i];
            Node[child].layer = Node[front].layer + 1;
            Q.push(child);
        }
    }
}

3、堆

//以大顶堆为例，堆是一棵完全二叉树，用数组存储，根节点在数组中下标为1，结点i的左子树下标为 i * 2，右子树下标为i * 2 + 1（如果存在）
//建堆：对于一棵乱序的完全二叉树，通过调整使其成为堆。由于用的是数组存储，是在一个乱序序列上建堆。
//设n为元素个数，heap[]是表示堆的数组
void createHeap(){  //时间复杂度：O(n)
    for(int i = n/2; i>= 1; i--){
        downAdjust(i,n);
    }
}

void downAdjust(int low, int high){ //向下调整，对heap在[low,high]范围内进行向下调整（high一般设置为n）。这一趟把low往下调整到正确位置。
    int i = low, j = i * 2;
    while(j <= high){
        if(j+1 <= high && heap[j+1] > heap[j]){
            j = j + 1;
        }
        if(heap[j] > heap[i]){
            swap(heap[j], heap[i]);
            i = j;
            j = i * 2;
        }
        else{
            break;
        }
    }
}

//删除堆顶元素：用最后一个元素覆盖堆顶元素，再对根节点向下调整。时间复杂度O(logn)
void deleteTop(){
    heap[1] = heap[n];
    n--;
    downAdjust(1, n);
}

//往堆中添加一个元素：把添加的元素放在最后，进行向上调整。
void insert(int x){
    n++;
    heap[n] = x;
    upAdjust(1, n);
}

void upAdjust(int low, int high){   //向上调整，对heap在[low,high]范围内进行向上调整（low一般设置为1）
    int i = high, j = i / 2;
    while(j >= low){
        if(heap[j] < heap[i]){
            swap(heap[j], heap[i]);
            i = j;
            j = i / 2;
        }
        else{
            break;
        }
    }
}

/*堆排序*/
//思路：（以大顶堆为例）建堆后，取出堆顶元素，将堆的最后一个元素移至堆顶，对堆顶向下调整，直到堆只有一个元素。
//给定一个初始乱序数组序列heap，调整后使其有序
void heapSort(){
    createHeap();
    for(int i = n; i > 1; i--){
        swap(heap[i], heap[1]);
        downAdjust(1, i - 1);
    }
}

五、图

1、图的存储

//1邻接矩阵
int G[N][N];

//2邻接表，一个表存放一个顶点的所有出边
//第一种：邻接表只存边的终点编号，不存边权
vector<int> Adj[N];        //Adj有N个vector，vector元素为int，存放结点的出边终点。

//第二种：邻接表存边的终点编号、边权
struct Node{
    int v;  //出边的终点的编号
    int w;  //边权
    Node(int _v, int_w) : v(_v), w(_w){}    //构造函数
}
vector<Node> Adj[N];    //Adj有N个vector，vector元素为Node，存放结点的出边终点以及对应边权。

2、DFS遍历图

const int maxn = 1000;
const int INF = 0x3f3f3f3f;
//2.1邻接矩阵版
int n,G[maxn][maxn];    //n为顶点数
bool vis[maxn] = {false};

void DFS(int u, int depth){ //u为顶点编号，depth为深度，从1开始
    vis[u] = true;
    //在此进行对u顶点的操作
    for(int v = 0; v < n; v++){
        if(vis[v] == false && G[u][v] != INF){
            DFS(v, depth + 1);
        }
    }
}

void DFSTrave(){
    for(int u = 0; u < n; u++){
        if(vis[u] == false){
            DFS(u, 1);
        }
    }
}

//2.2邻接表版（使用第一种邻接表，即邻接表只存边的终点编号，不存边权）
vector<int> Adj[maxn];
int n;  //n为顶点数
bool vis[maxn] = {false};

void DFS(int u, int depth){
    vis[u] = true;
    //在此进行对u顶点的操作
    for(int i = 0; i < Adj[u].size(); i++){
        int v = Adj[u][i];
        if(vis[v] == false){
            DFS(v, depth + 1);
        }
    }
}

void DFSTrave(){
    for(int u = 0; u < n; u++){
        if(vis[u] == false){
            DFS(u, 1);
        }
    }
}

3、BFS遍历图

//3.1邻接矩阵版
int n,G[maxn][maxn];
bool vis[maxn] = {false};

void BFS(int u){
    queue<int> q;
    q.push(u);
    vis[u] = true;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        //在此对now顶点进行操作
        for(int v = 0; v < n; v++){
            if(vis[v] == false && G[now][v] != INF){
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

void BFSTrave(){
    for(int u = 0; u < n; u++){
        if(vis[u] == false){
            BFS(u);
        }
    }
}

//3.2邻接表版
vector<int> Adj[maxn];
int n;
bool vis[maxn] = {false};

void BFS(int u){
    queue<int> q;
    q.push(u);
    vis[u] = true;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        //在此对now顶点进行操作
        for(int i = 0; i < Adj[now].size(); i++){
            int v = Adj[now][i];
            if(vis[v] == false){
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

void BFSTrave(){
    for(int u = 0; u < n; u++){
        if(vis[u] == false){
            BFS(u);
        }
    }
}

4、最短路径Dij + DFS

//4.1 使用Dijkstra 记录所有最短路径,记在pre[]里
int G[maxn][maxn];
int d[maxn];            //记录起点到结点i的最短距离
vector<int> pre[maxn];  //pre[i]表示起点到结点i的最短路径里，结点i的前驱结点
bool vis[maxn] = {false};
void Dijkstra(int s){   //s为起点
    fill(d, d + maxn, INF);
    d[s] = 0;
    for(int i = 0; i < n; i++){
        int u = -1, MIN = INF;      //找出未访问的点里最小的
        for(int j = 0; j < n; j++){
            if(vis[j] == false && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1) return;     //剩下的结点不连通，结束
        vis[u] = true;
        for(int v = 0; v < n; v++){
            if(vis[v] == false && G[u][v] != INF){
                if(d[u] + G[u][v] < d[v]){
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(d[u] + G[u][v] == d[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}

//4.2在记录的路径中找到使第二标尺最优的路径，使用DFS
//设st为路径起点
int optvalue = 初值0或INF;   //第二标尺最优值
vector<int> pre[maxn];  //已经存放最短路径结点的前驱
vector<int> path, temppath; //最优路径、临时路径，倒着存的
void DFS(int v){
    if(v == st){
        temppath.push_back(v);
        int value;
        //此处计算temppath上的value值，涉及边权或者点权
        if(value优于optvalue){
            optvalue = value;
            path = temppath;
        }
        temppath.pop_back();
        return;
    }
    temppath.push_back(v);
    for(int i = 0; i < pre[v].size(); i++){
        DFS(pre[v][i]);
    }
    temppath.pop_back();
}

5、Floyd算法

//思想：若存在点k，使得k作中介能使i->j的最短路径缩短，则用k作中介。可以有负边权，但不能有负权回路。
int dis[maxn][maxn];//dis[i][j]表示i->j的最短距离
void Floyd(){
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(dis[i][k] + dis[k][j] < dis[i][j] && dis[i][k] != INF && dis[k][j] != INF){
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}

六、其他

1、大整数运算

struct bign{
    int d[1000]; //数的低位存在低下标，如235813存储为 d[0]~d[5] 分别为 318532
    int len;    //记录长度
    bign(){     //构造函数，方便初始化
        memset(d,0,sizeof(d));
        len = 0;
    }
};

bign change(char str[]){    //读入字符数组，转化为大整数bign
    bign a;
    a.len = strlen(str);
    for(int i = 0; i < a.len; i++){
        a.d[i] = str[a.len - 1 - i] - '0';
    }
    return a;
}

int compare(bign a, bign b){    //比较大整数a与b的大小。    a>b，a=b，a<b 分别返回 1,0，-1
    if(a.len > b.len) return 1;
    else if(a.len < b.len) return -1;
    else{
        for(int i = a.len - 1; i >= 0; i--){
            if(a.d[i] > b.d[i]) return 1;
            else if(a.d[i] < b.d[i]) return -1;
        }
        return 0;
    }
}

void print(bign a){     //输出大整数
    for(int i = a.len - 1; i >= 0; i--){
        printf("%d", a.d[i]);
    }
}

bign add(bign a, bign b){   //大整数加法
    bign c;
    int carry = 0;
    for(int i = 0; i < a.len || i < b.len; i++){
        int temp = a.d[i] + b.d[i] + carry;
        c.d[c.len++] = temp % 10;
        carry = temp / 10;
    }
    if(carry != 0){
        c.d[c.len++] = carry;
    }
    return c;
}

bign sub(bign a, bign b){   //大整数减法a-b
    bign c;
    for(int i = 0; i < a.len || i < b.len; i++){
        if(a.d[i] < b.d[i]){
            a.d[i + 1]--;
            a.d[i] += 10;
        }
        c.d[c.len ++] = a.d[i] - b.d[i];
    }
    while(c.len - 1 >= 1 && c.d[c.len - 1] == 0){
        c.len--;
    }
    return c;
}

bign multi(bign a, int b){  //大整数 乘以 普通整数
    bign c;
    int carry = 0;
    for(int i = 0; i < a.len; i++){
        int temp = a.d[i] * b + carry;
        c.d[c.len++] = temp % 10;
        carry = temp / 10;
    }
    while(carry != 0){
        c.d[c.len++] = carry % 10;
        carry /= 10;
    }
    return c;
}

2、最大公约数与最小公倍数

int gcd(int a, int b){  //求a与b的最大公约数，a无须大于b
    if(b == 0) return a;
    else return gcd(b, a % b);
}

//a、b的最小公倍数 = a / 最大公约数 * b

3、分数运算

struct Fraction{    //用long long更好
    int up, down;   //规定1.分子up可以是负数，但分母down是非负数。2.若分数为0，规定up=0，down=1。3、分子分母互素（公约数只有1）
}

Fraction reduction(Fraction result){    //化简与约分，使一个分数满足上述三条规定
    if(result.down < 0){    //若分母是负数，则分母变成非负数
        result.up = -result.up;
        result.down = -result.down;
    }
    if(result.up == 0){     //若分数为0，则分母置1
        result.down = 1;
    }else{      //约分，分子分母除以它们的最大公约数即可
        int d = gcd(abs(result.up), result.down);   //d为分子分母的最大公约数
        result.up /= d;
        result.down /= d;
    }
    return result;
}

void print(Fraction r){     //打印分数r
    r = reduction(r);
    if(r.down == 1){    //是整数（含0）
        printf("%lld", r.up);
    }
    else if(abs(r.up) > r.down){    //是假分数
        printf("%d %d/%d",r.up / r.down, abs(r.up) % r.down, r.down);
    }
    else{   //是真分数
        printf("%d/%d", r.up, r.down);
    }
}

Fraction add(Fraction f1, Fraction f2){     //分数相加，通分相加后再化简约分
    Fraction res;
    res.up = f1.up * f2.down + f2.up * f1.down;
    res.down = f1.down * f2.down;
    return reduction(res);
}