常用模板（自己整理）

第一讲_基础算法

快速排序

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int n;          // 数组实际长度
int q[N];       // 存储待排序元素的数组

void quick_sort(int q[], int l, int r)
{
    // 如果 l>=r，说明区间内元素数量不超过1，无需排序
    if(l >= r) return ;
    
    // 选择基准值：取中间位置的元素
    int x = q[l + r >> 1];
    // 初始化左右指针
    int i = l - 1, j = r + 1;
    
    // 双指针扫描，将数组分为两部分
    while(i < j)
    {
        // i指针右移，找到第一个大于等于基准值的元素
        do i++; while(q[i] < x);
        // j指针左移，直到找到第一个小于等于基准值的元素
        do j--; while(q[j] > x);
        // 如果i和j指针还没有相遇，则交换这两个元素
        if(i < j) swap(q[i], q[j]);
    }
    
    // 递归处理左右两部分
    quick_sort(q, l, j);
    quick_sort(q, j+1 ,r);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    quick_sort(q, 0, n-1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    return 0;
}

---

归并排序

常规归并排序

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int n;                  // 数组实际长度
int q[N], temp[N];      // q[]为原始数组，temp[]为辅助合并的临时数组

void merge_sort(int q[], int l, int r)
{
    // 递归终止条件：区间内元素数量不超过1
    if(l >= r) return;
    
    // 计算中间位置，将数组分为左右两部分
    int mid = l + r >> 1;
    
    // 递归排序左右两部分
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    // 合并两个有序子数组
    int k = 0;              // temp数组的当前索引
    int i = l, j = mid + 1; // i指向左半部分起始，j指向右半部分起始
    
    // 双指针扫描，将较小元素依次放入temp数组
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) 
            temp[k++] = q[i++];
        else 
            temp[k++] = q[j++];
    }
    
    // 将剩余元素复制到temp数组
    while(i <= mid) temp[k++] = q[i++];
    while(j <= r) temp[k++] = q[j++];
    
    // 将排好序的temp数组复制回原数组
    for(i = l, j = 0; i <= r; i++, j++) 
        q[i] = temp[j];
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) 
        scanf("%d", &q[i]);
    
    merge_sort(q, 0, n - 1);
    
    for(int i = 0; i < n; i++) printf("%d ", q[i]);
    
    return 0;
}

应用：统计逆序对的数量

// 归并排序求逆序对的数量
#include<iostream>

using namespace std;

typedef long long LL;  // 使用长整型防止结果溢出

const int N = 1e6 + 10;

int n;                 // 数组长度
int q[N], tmp[N];      // q[]为原数组，tmp[]为辅助数组

LL merge_sort(int l, int r)
{
    // 递归终止条件：区间长度为1或0时逆序对数量为0
    if(l >= r) return 0;
    
    // 计算中间点，将数组分为两部分
    int mid = l + r >> 1;
    
    // 递归计算左右两部分的逆序对数量
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    
    int k = 0;      // 临时数组索引
    int i = l;      // 左半部分指针
    int j = mid + 1; // 右半部分指针
    
    // 双指针扫描，将较小元素依次放入temp数组
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j])
        {
            tmp[k++] = q[i++];
        }
        else
        {
            tmp[k++] = q[j++];
            // 左半部分从i到mid的所有元素都与q[j]构成逆序对
            res += mid - i + 1;
        }
    }
    
    // 处理剩余元素
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    
    // 将排好序的临时数组复制回原数组
    for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    printf("%lld", merge_sort(0, n - 1));
    return 0;
}    

堆排序

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], cnt;  // h[]存储堆元素（下标从1开始），cnt记录当前堆的大小

// 向下调整
void down(int u)
{
    int t = u;  // t记录当前节点、左孩子、右孩子中的最小值下标
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) // 如果最小值不是当前节点，交换并递归调整
    {
        swap(h[u], h[t]);
        down(t);    // 递归调整交换后的子节点
    }
}

// 向上调整
void up(int u)
{
    // 当不是根节点，且当前节点小于父节点时，向上调整
    while (u / 2 >= 1 && h[u] < h[u / 2])
    {
        swap(h[u], h[u / 2]);  // 与父节点交换
        u /= 2;  // 继续向上调整
    }
}

// 插入元素x
void insert(int x)
{
    h[++cnt] = x;  // 将新元素放到堆的末尾，堆大小+1
    up(cnt);  // 从新元素位置向上调整
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    cnt = n;

    // 构建小根堆：从最后一个非叶子节点开始向前调整
    for (int i = n / 2; i; i--) down(i);

    // 输出数列中前 m 小的数
    while (m--)
    {
        printf("%d ", h[1]);
        h[1] = h[cnt--];    //删除最小值，替换成最后一个元素
        down(1);
    }

    puts("");

    return 0;
}

---

二分

常规二分

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int n, m;    // n为数组长度，m为查询次数
int q[N];    // 存储有序数组

// 查找第一个大于等于k的位置（左边界）
int bsearch_1(int l, int r, int k)
{
    while(l < r)
    {
        int mid = l + r >> 1;  
        if(q[mid] >= k)
            r = mid;
        else
            l = mid + 1;
    }
    
    if(q[l] != k) return -1;
    else return l;
}

// 查找最后一个小于等于k的位置（右边界）
int bsearch_2(int l, int r, int k)
{
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(q[mid] <= k)
            l = mid;
        else
            r = mid - 1;
    }
    
    if(q[l] != k) return -1;
    else return l;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    // 处理多次查询
    while(m--)
    {
        int k;
        scanf("%d", &k);
        
        // 查找左边界
        int l = bsearch_1(0, n-1, k);
        if(l != -1)
        {
            // 若左边界存在，查找右边界
            int r = bsearch_2(0, n-1, k);
            cout<<l<<" "<<r<<endl;
        }
        else
            cout<<-1<<" "<<-1<<endl;
    }
    return 0;
}

应用：计算数的三次方根

#include<iostream>

using namespace std;

double n;

bool check(double x)
{
    if((x * x * x) >= n) return true;
    else return false;
}

double bsearch_3(double l, double r)
{
    // 结果精确到小数点后6位，则eps要开6+2=8位
    const double eps = 1e-8;
    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    
    return l;
}

int main()
{
    scanf("%lf", &n);
    double left = -100, right = 100;
    
    double res = bsearch_3(left, right);
    printf("%.6lf", res);
    return 0;
}

upper和lower_bound

#include <algorithm>

// 使用 lower_bound 查找第一个 >= target 的元素位置
auto low = lower_bound(arr.begin(), arr.end(), target);

// 使用 upper_bound 查找第一个 > target 的元素位置
auto up = upper_bound(arr.begin(), arr.end(), target);

---

高精度算法

高精度加法

#include<iostream>
#include<vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> c;  // 存储结果的向量（逆序存储）
    
    int t = 0;  // 进位标志
    
    // 遍历每一位，处理到较长数的最后一位
    for(int i = 0; i < A.size() || i < B.size(); i++)
    {
        if(i < A.size()) t += A[i];  // 累加A的当前位
        if(i < B.size()) t += B[i];  // 累加B的当前位
        
        c.push_back(t % 10);  // 当前位的结果（取模10）
        t /= 10;  // 计算进位（整除10）
    }
    
    // 处理最后可能的进位
    if(t) c.push_back(1);
    
    return c;
}

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 c = add(A, B);
    
    // 逆序输出结果（高位在前）
    for(int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    
    return 0;
}

高精度减法

#include<iostream>
#include<vector>

using namespace std;

// 比较两个大整数的大小
bool cmp(vector<int> A, vector<int> B)
{
    if(A.size() != B.size()) return A.size() > B.size();
    
    // 长度相同时，从最高位（向量末尾）开始逐位比较
    for(int i = A.size() - 1; i >= 0; i--)
        if(A[i] != B[i]) 
            return A[i] > B[i];
    
    return true;
}

// 高精度减法（要求 A >= B）
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> c;  // 存储结果的向量（逆序存储）
    
    int t = 0;  // 借位标志（0 或 1）
    
    // 遍历被减数的每一位
    for(int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;  // 减去上一位的借位
        
        // 若减数还有当前位，则减去该位
        if(i < B.size()) t -= B[i];
        
        // 当前位的计算结果（考虑借位后）
        c.push_back((t + 10) % 10);
        
        // 更新借位状态
        if(t < 0) t = 1;  // 需要借位，下一位减 1
        else t = 0;  // 无需借位
    }
    
    // 去除结果前导 0（如 1000-999=0001，应输出 1）
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    
    return c;
}

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');
    
    // 根据大小关系处理减法
    if(cmp(A, B))
    {
        auto c = sub(A, B);
        
        for(int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    }
    else
    {
        auto c = sub(B, A);
        
        printf("-");  // 输出负号
        
        for(int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    }
    
    return 0;
}

高精度乘法

#include<iostream>
#include<vector>

using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> c;  // 存储结果的向量（逆序存储）
    
    int t = 0;  // 进位标志
    
    // 遍历A的每一位，并处理进位，直到没有进位为止
    for(int i = 0; i < A.size() || t; i++)
    {
        if(i < A.size()) t += A[i] * b;  // 当前位与乘数相乘，加上进位
        
        c.push_back(t % 10);  // 当前位的结果（取模10）
        
        t /= 10;  // 计算进位（整除10）
    }
    
    // 去除结果中的前导0（例如 1234 * 0 = 0000，应输出0）
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    
    return c;
}

int main()
{
    string a;  // 输入的高精度整数
    int b;     // 输入的低精度整数
    vector<int> A;
    
    cin >> a >> b;
    
    // 将字符串转换为逆序的数字向量
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    auto c = mul(A, b);

    for(int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    
    return 0;
}

高精度除法

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> c;  // 逆序存储商的向量
    
    r = 0;  // 初始化余数为0
    
    for(int i = A.size() - 1; i >= 0; i--)
    {
        r = r * 10 + A[i];  // 将余数扩大10倍并加上当前位的值
        c.push_back(r / b);  // 计算当前位的商
        r %= b;  // 更新余数为当前除法的余数
    }
    
    reverse(c.begin(), c.end());
    
    // 去除结果中的前导0
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    
    return c;
}

int main()
{
    string a;  // 输入的高精度整数
    int b;     // 输入的低精度整数（除数，b≠0）
    vector<int> A;
    
    int r; // 存储余数
    
    cin >> a >> b;
    
    // 将字符串转换为逆序的数字向量
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    auto c = div(A, b, r);
    
    for(int i = c.size() - 1; i >= 0; i--) 
        printf("%d", c[i]);
    
    printf("\n%d", r);
    
    return 0;
}

---

前缀和

#include<iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int arr[N][N];
int res[N][N]; // res[i, j] 为第i行j列格子左上部分所有元素的和

int main()
{
    scanf("%d %d %d", &n, &m, &q);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &arr[i][j]);
            // 计算前缀和
            res[i][j] = res[i-1][j] + res[i][j-1] - res[i-1][j-1] + arr[i][j];
        }
    }
    
    while(q--)
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        // 计算矩阵区间和
        cout<<res[x2][y2] - res[x1-1][y2] - res[x2][y1-1] + res[x1-1][y1-1]<<endl; 
    }
    return 0;
}

---

差分

#include <iostream>

using namespace std;

int n, m, q;
const  int N = 1010;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;     //原前缀和矩阵（x1,y1）后面的元素都会 + c
    b[x2+1][y1] -= c;   //进行抵消，只在给定区间 + c
    b[x1][y2+1] -= c;
    b[x2+1][y2+1] +=c;  //进行补偿
}

int main()
{
    scanf("%d %d %d", &n, &m, &q);
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <=m; j++)
            scanf("%d", &a[i][j]);
    //b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1] 
    //a矩阵是b矩阵的前缀和，b矩阵是a矩阵的差分        
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            insert(i, j, i, j, a[i][j]);

    while(q--)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    
    //还原成前缀和矩阵
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + b[i][j];
            
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++) printf("%d ", b[i][j]);
        puts("");
    }
    return 0;
}

---

第二讲_数据结构

单链表

#include <iostream>

using namespace std;

const int N = 100010;

// head 表示头结点，值表示头节点的next指针是多少
// e[i] 存储节点i的值
// ne[i] 存储节点i的next指针（idx）
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;  //-1表示空集
    idx = 0;    //下标从0开始，表示当前操作第 idx + 1 个元素
}

// 将x插到头结点
void add_to_head(int x)
{   
    e[idx] = x, ne[idx] = head, head = idx, idx++;
}

// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx, idx++;
}

// 将下标是k的点后面的一个点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin >> m;

    init();

    while (m--)
    {
        int k, x;
        char op;

        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

---

双链表

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

const int N = 100010;

int m;
int e[N], l[N], r[N], idx;

void init()
{
    // 0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    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;
    idx++;
}

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

int main()
{
    cin >> m;

    init();

    while (m--)
    {
        string op;
        cin >> op;
        int k, x;
        if (op == "L")
        {
            cin >> x;
            insert(0, x);
        }
        else if (op == "R")
        {
            cin >> x;
            insert(l[1], x);
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else
        {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

---

单调栈

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;//初始栈顶指针指向 0 位置

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        scanf("%d", &x);
        //栈不为空且栈顶元素大于等于 x 时，弹出栈顶元素（使栈具有单调性）
        while (tt && stk[tt] >= x) tt--;
        //如果栈空
        if (!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        // x 入栈
        stk[++tt] = x;
    }

    return 0;
}

---

单调队列-滑动窗口

//输入样例：
//8 3
//1 3 -1 -3 5 3 6 7
//输出样例：
//-1 -3 -3 -3 3 3
//3 3 5 5 6 7

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

const int N = 1000010;

int a[N], q[N]; //数组  单调队列：存储元素下标

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        //判断队头元素是否还在队列里面，不应该在，则弹出队头元素（保持 k 个元素）
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        //队列不为空且队尾元素大于等于 x 时，弹出队尾元素（使队列具有单调性）
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        //当前元素下标 i 入队
        q[++tt] = i;
		//判断是否满足 k 个元素
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        //队列不为空且队尾元素小于等于 x 时，弹出队尾元素（使队列具有单调性）
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        //当前元素下标 i 入队
        q[++tt] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    return 0;
}

---

堆

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;
// h[]：堆的元素存储（小根堆）
// ph[k]：**第k次插入的元素**在堆中的位置（pos）
// hp[pos]：**堆中pos位置的元素**是第几次插入的（k）
// cnt：当前堆的大小

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]); // 根据堆位置获取插入序号，然后在交换ph[]中的元素
    swap(hp[a], hp[b]);         // 交换堆位置对应的插入序号
    swap(h[a], h[b]);           // 交换堆中的元素值
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n--)
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))   // 1. 插入操作 I x
        {
            scanf("%d", &x);
            cnt++;  // 堆大小+1
            m++;    // 插入次数+1（m记录当前是第几次插入）
            ph[m] = cnt;    // 第m次插入的元素在堆中的位置是cnt
            hp[cnt] = m;    // 堆中cnt位置的元素是第m次插入的
            h[cnt] = x;     // 元素值存入堆
            up(cnt);    // 向上调整，维持小根堆
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);   // 2. 输出最小值 PM
        else if (!strcmp(op, "DM")) // 3. 删除最小值 DM
        {
            heap_swap(1, cnt);  // 交换堆顶和最后一个元素
            cnt--;      // 堆大小 - 1（删除原堆顶）
            down(1);    // 向下调整新堆顶
        }
        else if (!strcmp(op, "D"))  // 4. 删除第k次插入的元素 D k
        {
            scanf("%d", &k);
            k = ph[k];          // 找到第k次插入的元素在堆中的位置
            heap_swap(k, cnt);  // 交换该位置和最后一个元素
            cnt--;              // 堆大小-1
            up(k);              // 向上/向下调整（不确定方向，两者都调用）    
            down(k);
        }
        else // 5. 修改第k次插入的元素为x --- C k x
        {
            scanf("%d %d", &k, &x);
            k = ph[k];  // 找到第k次插入的元素在堆中的位置
            h[k] = x;   // 更新元素值
            up(k);      // 向上/向下调整（不确定方向，两者都调用）
            down(k);
        }
    }

    return 0;
}

散列表（哈希表）

开放地址法

#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    int t = (x % N + N) % N;    // 计算哈希下标
    while (h[t] != null && h[t] != x)    // 当位置被占用且不是目标值时
    {
        t++;
        if (t == N) t = 0;  // 到达数组末尾则回到开头（循环数组）
    }
    return t;   // 返回找到的空位或目标值的位置
}

int main()
{
    memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &n);

    while (n--)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

拉链法

#include <cstring>
#include <iostream>

using namespace std;

const int N = 100003;

int h[N];   //哈希表的表头数组
int e[N];   //存储链表中节点的值
int ne[N];  //存储链表中节点的下一个节点索引
int idx;    //链表节点的索引

void insert(int x)
{
    // c++中负数取模运算规则：
    // 满足数学关系：a = q * b + r
    // 其中 q 是商（向零取整），r 是余数 且 0 ≤ |r| < |b|
    
    // 计算哈希下标，确保非负
    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;
    //没找到返回 false
    return false;
}

int main()
{
    int n;
    scanf("%d", &n);

    // 初始化哈希表头为 -1，表示链表为空
    memset(h, -1, sizeof h);

    while (n--)
    {
        char op[2];
        int x;
        scanf("%s %d", op, &x);

        if (*op == 'I') insert(x);
        else
        {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

字符串哈希

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL; // 用无符号长整型存储哈希值，利用自然溢出处理模运算

const int N = 100010, P = 131;  // N 是字符串最大长度，P 是进制基数（经验值选131）

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r)
{
    // 利用前缀哈希差值计算子串哈希，h[r] - h[l-1] * p[r-l+1] 等价于子串的哈希值
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);   // 字符串从下标1开始存储

    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * P + str[i];   // 计算前缀哈希，类似 P 进制数累加
        p[i] = p[i - 1] * P;            // 预处理 P 的幂次，用于后续计算子串哈希
    }

    while (m--)
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        // 比较两个子串的哈希值
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}

---

KMP字符串匹配

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];    //匹配串  模式串

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;    //下标从 1 开始
		
    //求 next[] 数组
    //例如模式串："abababab" ne[] = [0, 0, 1, 2, 3, 4, 5, 6]
    for (int i = 2, j = 0; i <= n; i++)
    {
        // j 没有退回起点 且 不匹配时
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;  //j + 1 预处理进行匹配
        ne[i] = j;
    }

    // KMP匹配过程
    for (int i = 1, j = 0; i <= m; i++)
    {
        // j 没有退回起点 且 发生不匹配时
        while (j && s[i] != p[j + 1]) j = ne[j];
        //如果匹配，则 j 后移
        if (s[i] == p[j + 1]) j++;
        if (j == n)
        {
            printf("%d ", i - n);
            //往后退一步继续匹配
            j = ne[j];
        }
    }
	
    return 0;
}

---

Trie字典树

应用1：插入并统计字符串出现的次数

#define  _CRT_SECURE_NO_WARNINGS
// Trie 字典树:单模式串匹配（判断单个字符串是否在字典中）
// AC 自动机:多模式串匹配（在文本中同时查找多个字典词）
#include <iostream>

using namespace std;
// Trie（字典树）: 高效存储和查找字符串集合的数据结构
const int N = 100010;

int son[N][26]; //存储从节点 P 沿着 i 这条边走到的子节点
int cnt[N]; //存储以节点 p 结尾的单词插入次数
int idx;    //给每个节点编号（节点数）
char str[N];    //处理的字符串

void insert(char* str)
{
    int p = 0; // 从根节点（编号0）开始
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';  // 将字符映射为0-25的索引
        if (!son[p][u]) son[p][u] = ++idx; // 如果路径不存在，创建新节点
        p = son[p][u]; // 移动到下一个节点
    }
    cnt[p]++; // 标记字符串结尾，计数器加1
}

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; // 路径不存在，返回0
        p = son[p][u]; // 移动到下一个节点
    }
    return cnt[p]; // 返回该节点的计数器值
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        char op[2];
        scanf("%s %s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

应用2：最大异或对

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i--) // 处理31位（最高位到最低位）
    {
        //从最高位开始，右移获取当前位的值（0或1）
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++idx;  // 如果路径不存在，创建新节点
        p = son[p][u];  // 移动到下一个节点
    }
}

int query(int x)
{
    int p = 0, res = 0; // res 记录最大异或值
    for (int i = 30; i >= 0; i--)
    {
        int s = x >> i & 1; // 当前位的值
        if (son[p][!s]) // 若存在与当前位相反的路径
        {
            p = son[p][!s]; // 选择相反路径
            res += (1 << i);  //表示将数字 1 向左移动 i 位，相当于计算 2^i
        }
        else p = son[p][s]; // 否则选择相同路径
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, query(a[i]));

    printf("%d\n", res);

    return 0;
}

---

并查集

常规并查集

#include <iostream>

using namespace std;

const int N = 100010;

int p[N]; // p[x] 表示 x 的父节点

//查
int find(int x) //返回 x 的祖宗节点 + 路径压缩
{
    if (p[x] == x)	//如果递归到根节点则返回
        return x;
    else
        return p[x] = find(p[x]);   //递归回溯时将路径上的每个节点都指向跟节点（路径压缩）
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i;  // 初始化每个节点的父节点为自身（编号从 1 开始）

    while (m--)
    {
        char op[2];
        int a, b;
        scanf("%s %d %d", op, &a, &b);
        //并
        if (*op == 'M') p[find(a)] = find(b);   //合并 a，b 两个元素所属集合
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

应用1：统计连通块中点的数量

#include <iostream>

using namespace std;

const int N = 100010;

int p[N], cnt[N]; // p[x] 表示 x 的父节点，cnt[N]表示当前集合点的数量

//查
int find(int x) //返回 x 的祖宗节点 + 路径压缩
{
    if (p[x] == x)	//如果递归到根节点则返回
        return x;
    else
        return p[x] = find(p[x]);   //递归回溯时将路径上的每个节点都指向跟节点（路径压缩）
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;  // 初始化每个节点的父节点为自身（编号从 1 开始）
        cnt[i] = 1;
    }


    while (m--)
    {
        string op;
        int a, b;
        cin >> op;
        //并
        if (op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b); // 先找到两个元素的根节点
            if (a != b) // 如果不在同一个集合才需要合并
            {
                p[a] = b; // 将a的根节点合并到b的根节点下
                cnt[b] += cnt[a];  // 更新b集合的大小（加上a集合的大小）
            }
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }

    return 0;
}

应用2：食物链

#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
int p[N];   //存储每个节点的父节点
int d[N];   //存储当前节点到父节点的 “距离”
//模 3 余 1：吃根节点对应的动物；
//模 3 余 2：被根节点对应的动物吃；
//模 3 余 0：与根节点同类。


int find(int x)
{
    if (p[x] == x)  //如果递归到根节点则返回
        return x;
    else
    {
        int t = find(p[x]); // 递归找根节点
        d[x] += d[p[x]];    // 更新当前节点到父节点的距离
        p[x] = t;           // 路径压缩，当前节点直接指向根
        return t;
    }
}

int main()
{
    scanf("%d %d", &n, &m);

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

    int res = 0;
    while (m--)
    {
        int t, x, y;
        scanf("%d %d %d", &t, &x, &y);

        //若动物编号超出范围，直接判定为假话
        if (x > n || y > n) res++;
        else
        {
            int px = find(x), py = find(y);// 递归找根节点
            
            //同类语句
            if (t == 1)
            {
                //根节点相同时，若 (d[x] - d[y]) % 3 != 0，说明 x 和 y 不是同类，语句冲突
                if (px == py && (d[x] - d[y]) % 3) res++;
                else if (px != py)  //根节点不同时，设置 d[px] 使合并后 x 和 y 同类关系成立。
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else //捕食语句
            {
                //根节点相同时，若 (d[x] - d[y] - 1) % 3 != 0，说明 x 不吃 y，语句冲突
                if (px == py && (d[x] - d[y] - 1) % 3) res++;
                else if (px != py)  //根节点不同时，设置 d[px] 使合并后 x 吃 y 的关系成立。
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}

---

第三讲_搜索与图论

DFS

排列数字组合

// 所有可能、回溯、连通性、博弈
#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;
const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u)
{
	// 递归终止条件：已填满 n 个位置
	if (u == n)
	{
		// 输出当前排列
		for (int i = 0; i < n; i++) printf("%d ", path[i]);
		puts("");
		return;
	}

	// 尝试为第 u 个位置填入 1~n 中未使用的数字
	for (int i = 1; i <= n; i++)
	{
		if (!st[i])	// 若数字 i 未被使用
		{
			path[u] = i;	// 第 u 个位置填入 i
			st[i] = true;	// 标记 i 为已使用
			dfs(u + 1);		// 递归处理下一个位置（u+1）
			st[i] = false;	// 回溯：撤销标记，尝试其他数字
		}
	}
}

int main()
{
	cin >> n;

	dfs(0);

	return 0;
}

n皇后问题

#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N];		// 记录每一列是否已经被占用
bool dg[N * 2];		// 正对角线的特点是行和列的和固定，以 u+i 作为 dg 的索引
bool udg[N * 2];	// 反对角线的特点是行和列的差固定，以 n-u+i 作为 udg 的索引（确保为正）

void dfs(int u)
{
    // 终止条件：遍历完所有行
    if (u == n)
    {
        for (int i = 0; i < n; i++) puts(g[i]);
        puts("");
        return;
    }

    // 遍历当前行 u 的每一列 i，尝试放置皇后
    for (int i = 0; i < n; i++)
        // 检查列、正对角线、反对角线是否冲突
        if (!col[i] && !dg[u + i] && !udg[n - u + i])
        {
            // 放置皇后
            g[u][i] = 'Q';
            // 标记冲突（列、对角线被占用）
            col[i] = dg[u + i] = udg[n - u + i] = true;
            // 递归处理下一行
            dfs(u + 1);
            // 回溯：撤销标记和皇后
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g[i][j] = '.';

    dfs(0);

    return 0;
}

---

BFS

// BFS天生适合**无权图的最短路径问题**
// 最短、最少、层级、扩散
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N];    // 存储网格
int d[N][N];    // 存储到各点的最短距离
// 四个方向：上、右、下、左
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

int bfs()
{
    queue<PII> q;

    memset(d, -1, sizeof d);    // 初始化距离为-1（未访问）
    d[0][0] = 0;        // 起点距离为0
    q.push({ 0, 0 });   // 起点入队

    while (q.size())
    {
        auto t = q.front(); // 取队头元素
        q.pop();            // 队头出队

        for (int i = 0; i < 4; i++) // 遍历四个方向
        {
            int x = t.first + dx[i];    // 新x坐标
            int y = t.second + dy[i];   // 新y坐标
            //检查：
            //1. 坐标是否在网格范围内
            //2. 该位置可通行
            //3. 该位置未访问过
            if (x >= 0&&x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1; // 更新距离
                q.push({ x, y });                   // 新坐标入队
            }
        }
    }

    return d[n - 1][m - 1]; // 返回终点距离
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}

---

拓扑排序

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
// 邻接表存储树
int h[N];   //存储表头
int e[N];   //存储节点编号
int ne[N];  //存储下一条边的索引
int idx;    //分配边的索引

int d[N];   // 存储每个节点的入度
int q[N];   // 队列，用于BFS实现拓扑排序

void add(int a, int b)
{
    e[idx] = b;     // 记录节点编号
    ne[idx] = h[a]; // 指向前一条边的索引
    h[a] = idx++;   // 更新表头为当前边索引，idx自增
}

bool topsort()
{
    int hh = 0, tt = -1;
    // 初始化队列，将所有入度为0的节点入队
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q[++tt] = i;

    // BFS处理队列中的节点
    while (hh <= tt)
    {
        // 取出队头节点
        int t = q[hh++];
        // 遍历t的所有邻居节点
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            // 减少邻居节点的入度，若变为0则入队
            if (--d[j] == 0)
                q[++tt] = j;
        }
    }
    // 若队列中的节点数等于n，说明存在拓扑排序
    return tt == n - 1;
}

int main()
{
    scanf("%d %d", &n, &m);

    memset(h, -1, sizeof h);

    // 读入边，构建图并统计入度
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);

        d[b]++;
    }

    if (!topsort()) puts("-1");
    else
    {
        for (int i = 0; i < n; i++) printf("%d ", q[i]);
        puts("");
    }

    return 0;
}

---

Dijkstra

#include <cstring>
#include <iostream>
#include <algorithm>
// Dijkstra: 非负权图(城市道路导航)，单源最短路径, 时间复杂度 O(n²) （n 为顶点）
// Bellman-Ford:正负权图（金融利率模型），单源最短路径，时间复杂度 O(n * m) （n 为顶点，m 为边）
// SPFA：负权图（无负环），单源最短路径, 时间复杂度平均情况：O(m)，但最坏情况仍为 O(n * m) （n 为顶点，m 为边）
// Floyd：任意两点最短路径，时间复杂度 O(n³) （n 为顶点）
using namespace std;

const int N = 510;

int n, m;
int g[N][N];    // 邻接矩阵存储图
int dist[N];    // 存储各节点到起点的最短距离
bool st[N];     // 标记节点是否已确定最短路径

int dijkstra()
{
    // 初始化距离数组为无穷大，起点距离为0
    memset(dist, 0x3f, sizeof dist);
    //起点为 1 号点，故先给起点距离设为 0
    dist[1] = 0;

    // 迭代n-1次，每次确定一个节点的最短路径
    for (int i = 0; i < n - 1; i++)
    {
        // 找到未确定最短路径的节点中距离最小的节点t
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用节点t更新其所有邻居的距离
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        // 标记节点t为已确定
        st[t] = true;
    }
    // 若终点的距离仍为无穷大，说明无法到达
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d %d", &n, &m);

    //初始化各边权为无穷大
    memset(g, 0x3f, sizeof g);

    while (m--)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        //对于可能出现重边和自环，取最小的边权
        g[a][b] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

---

Floyd

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;    // n为节点数，m为边数，Q为查询次数
int d[N][N];    // 邻接矩阵
int p[N][N];    // 存储路径的中间节点，
                // p[i][j] 表示i到j的最短路径中j的前驱节点

void floyd()
{
    //外层循环枚举中间点 k，内层两层循环枚举所有点对 (i, j)
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (d[i][j] > d[i][k] + d[k][j])
                {
                    //注意可能存在被负权边 “松弛” 后的 INF - k
                    d[i][j] = d[i][k] + d[k][j];
                    //记录插点（前驱节点编号）
                    p[i][j] = k; 
                }
}

void path(int i, int j)
{
    if (p[i][j] == 0) return;   // 没有前驱节点，递归结束（节点编号默认从 1 开始）
    int k = p[i][j];
    path(i, k);                 // 输出 i 到 k 的路径
    printf("%d ", k);           // 输出前驱节点 k
    path(k, j);                 // 输出 k 到 j 的路径
}

int main()
{
    scanf("%d%d%d", &n, &m, &Q);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) d[i][j] = 0;    // 自己到自己的距离为0 
            else d[i][j] = INF;         // 初始化为无穷大

    // 读入边，处理重边（保留最小边权）
    while (m--)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while (Q--)
    {
        int a, b;
        scanf("%d %d", &a, &b);

        int t = d[a][b];
        //将 INF / 2 视作阈值防止负权边 “松弛”
        if (t > INF / 2) puts("impossible");
        else
        {
            // 输出最短距离
            printf("%d\n", t);
            // 输出路径
            printf("Path: %d ", a);
            path(a, b);
            printf("%d\n", b);
        }
    }

    return 0;
}

---

Prim（选点）

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];    // 邻接矩阵存储图
int dist[N];    // 记录各顶点到当前生成树（集合）的最短距离
bool st[N];     // 标记顶点是否已加入生成树

int prim()
{
    // 初始化距离数组为无穷大
    memset(dist, 0x3f, sizeof dist);

    // 存储最小生成树的总权值
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        // 步骤 1：筛选距离当前生成树最近的未加入顶点 t
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 步骤 2：判断图是否连通，若中间过程无法找到 t 且非初始轮次，说明无法构成最小生成树
        if (i && dist[t] == INF) return INF;

        // 步骤 3：更新最小生成树总权值，标记 t 为已加入
        if (i) res += dist[t];
        st[t] = true;

        // 步骤 4：用新加入的顶点 t 更新其他顶点到生成树的距离
        for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    // 初始化邻接矩阵为无穷大
    memset(g, 0x3f, sizeof g);

    while (m--)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
} 

---

Kruskal（选边）

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge
{
    int a, b, w;
}edges[M];

//查
int find(int x) //返回 x 的祖宗节点 + 路径压缩
{
    if (p[x] == x)	//如果递归到根节点则返回
        return x;
    else
        return p[x] = find(p[x]);   //递归回溯时将路径上的每个节点都指向跟节点（路径压缩）
}

bool cmp(struct Edge A, struct Edge B)
{
    return A.w < B.w;
}

int kruskal()
{
    sort(edges, edges + m, cmp);

    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;
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = { a, b, w };
    }

    int t = kruskal();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

---

二分图

染色法判定二分图

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
// 邻接表存储树
int h[N];   //存储表头
int e[M];   //存储节点编号
int ne[M];  //存储下一条边的索引
int idx;    //分配边的索引

int color[N];	// 存储每个顶点的颜色，0表示未着色，1和2表示两种不同颜色

void add(int a, int b)
{
    e[idx] = b;     // 记录节点编号
    ne[idx] = h[a]; // 指向前一条边的索引
    h[a] = idx++;   // 更新表头为当前边索引，idx自增
}

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])
        {
            // 递归着色为相反颜色
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;   // 如果邻接顶点已着色且颜色相同，返回冲突
    }

    return true;
}

int main()
{
    scanf("%d %d", &n, &m);

    // 初始化邻接表头为-1，表示空链表
    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b), add(b, a);
    }

    // 标记是否为二分图
    bool flag = true;
    // 遍历所有顶点，处理未着色的连通分量
    for (int i = 1; i <= n; i++)
        if (!color[i])
        {
            // 从顶点i开始DFS，初始颜色为1
            if (!dfs(i, 1))
            {
                // 发现冲突，不是二分图
                flag = false;
                break;
            }
        }

    if (flag) puts("Yes");
    else puts("No");

    return 0;
}

二分图最大匹配

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
// 邻接表存储树
int h[N];   //存储表头
int e[M];   //存储节点编号
int ne[M];  //存储下一条边的索引
int idx;    //分配边的索引

int match[N];   //记录右部节点的匹配对象（值为左部节点编号，0 表示未匹配）
bool st[N];     //标记右部节点是否被访问  

void add(int a, int b)
{
    e[idx] = b;     // 记录节点编号
    ne[idx] = h[a]; // 指向前一条边的索引
    h[a] = idx++;   // 更新表头为当前边索引，idx自增
}

bool find(int x)
{
    // 遍历左部节点 x 的所有邻接右部节点
    for (int i = h[x]; i != -1; i = ne[i])
    {
        // 右部节点 j
        int j = e[i];
        // 右部节点 j 未被访问
        if (!st[j])
        {
            // 标记为已访问
            st[j] = true;
            // 若 j 未匹配，或 j 的原匹配节点可找到新匹配
            if (match[j] == 0 || find(match[j]))
            {
                // 更新匹配关系
                match[j] = x;
                // 找到增广路径
                return true;
            }
        }
    }
    // 未找到增广路径
    return false;
}

int main()
{
    scanf("%d %d %d", &n1, &n2, &m);

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
    }
    // 最大匹配数
    int res = 0;
    for (int i = 1; i <= n1; i++)
    {
        // 重置访问标记
        memset(st, false, sizeof st);
        // 找到增广路径则匹配数加 1
        if (find(i)) res++;
    }

    printf("%d\n", res);

    return 0;
}

---

Math

质数

试除法

#include <iostream>
#include <algorithm>

using namespace std;

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0)
            return false;
    return true;
}

int main()
{
    int n;
    cin >> n;

    while (n--)
    {
        int x;
        cin >> x;
        if (is_prime(x)) puts("Yes");
        else puts("No");
    }

    return 0;
}

分解质因数

#include <iostream>
#include <algorithm>
// 质因数：一个数分解成质数相乘的形式时，这些质数就是该数的质因数
using namespace std;

void divide(int x)
{
    for (int i = 2; i <= x / i; i++)
        // 检查i是否是x的质因数
        if (x % i == 0)
        {
            // 统计该质因数的指数
            int s = 0;
            while (x % i == 0) x /= i, s++;
            // 输出质因数及其指数
            cout << i << ' ' << s << endl;
        }
    // 如果x仍大于1，说明x本身是一个质数
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

筛质数_埃及筛

#include <iostream>
#include <algorithm>
// 核心逻辑：如果 i 是质数，将其所有倍数标记为合数。
// 缺点：可能重复标记同一个合数（如 12 会被 2 和 3 分别标记）。
using namespace std;

const int N = 1000010;

int primes[N], cnt; // 存储所有质数
bool st[N];         // 标记数组，true表示合数

// 求出1~n中质数的个数
void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        // 如果是合数直接跳过
        if (st[i]) continue;
        primes[cnt++] = i;
        // 标记i的所有倍数为合数
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

筛质数_线性筛（最优）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int primes[N], cnt; // 存储所有质数及其数量
bool st[N];         // 标记数组，st[i] 为 true 表示 i 是合数

// 求出1~n中质数的个数
void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        // 若 i 未被标记，i 是质数
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            // 标记 primes[j] * i 为合数
            st[primes[j] * i] = true;
            // 关键优化：确保每个合数只被最小质因数筛除
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

---

约数

试除法

#include <iostream>
#include <algorithm>
#include <vector>
// 约数 = 因数 跟倍数配对，质数 = 素数 跟合数配对
using namespace std;

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i++)
        if (x % i == 0)
        {
            res.push_back(i);
            // 避免重复添加相同的约数
            if (i != x / i) res.push_back(x / i);
        }
    // 将约数按升序排列
    sort(res.begin(), res.end());
    return res;
}

int main()
{
    int n;
    cin >> n;

    while (n--)
    {
        int x;
        cin >> x;
        auto res = get_divisors(x);

        for (auto x : res) cout << x << ' ';
        cout << endl;
    }

    return 0;
}

统计约数个数

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
// 约数个数定理： 360 = 2^3 * 3^2 * 5^1
// cnt = (a1 + 1)*(a2 + 1)*...*(ak + 1) 其中(a是各约数的指数)

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;

    while (n--)
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i++)
            while (x % i == 0)
            {
                x /= i;
                // 记录约数 i 的个数
                primes[i]++;
            }
        // 最后可能还剩个比较大的因数 如 14 = 2 * 7
        if (x > 1) primes[x]++;
    }

    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;

    cout << res << endl;

    return 0;
}

统计约数之和

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
// 约数和定理： 360 = 2^3 * 3^2 * 5^1
// sum = (p1^0 + p1^1 + ... + p1^a1)*...*(pk^0 + pk^1 + ... + pk^ak) 
// 其中(p是各质因数，a是各约数的指数)
using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;

    while (n--)
    {
        int x;
        cin >> x;
        // 分解x的质因数，累加到primes中
        for (int i = 2; i <= x / i; i++)
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;
            }
        // 剩余的x是质因数
        if (x > 1) primes[x]++;
    }

    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first;     // 质因数p
        LL b = p.second;    // 总次数b
        
        LL t = 1;
        // 求等比数列和
        while (b--) t = (t * a + 1) % mod;

        // 累乘所有等比数列和
        res = res * t % mod;
    }

    cout << res << endl;

    return 0;
}

GCD和LCM

#include <iostream>
#include <algorithm>

using namespace std;

// 计算GCD（Greatest Common Divisor）
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

// 计算LCM（Lowest Common Multiple）
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", gcd(a, b));
    }

    return 0;
}

---

快速幂

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
// 应用:求逆元
// 费马小定理： 假如 a 是一个整数，p 是一个质数那么
// 1. 如果 a 是 p 的倍数， a^p = a (mod p)  (其中 = 表示同余符号)
// 2. 如果 a 不是 p 的倍数，a^（p - 1） = 1 (mod p)  
//                          =>   a * a^(p - 2) = 1 (mod p)  
//                          =>   (a % p) * (a^(p - 2) % p) = 1 % p  
//                          其中 a^(p - 2) 是 a 的逆元
// 乘法逆元：如果 a * x = 1 ( mod p ),则称 x 和 a 互为乘法逆元

// 快速计算 a^b mod p （二进制转十进制）
LL qmi(int a, int b, int p)
{
    // 初始化结果，处理 p=1 的情况
    LL res = 1 % p;
    while (b)
    {
        if (b & 1) res = res * a % p;   // 当前位为 1 时，累乘 a 的当前幂次
        a = a * (LL)a % p;              // a 自乘，更新为 a^{2^k}
        b >>= 1;                        // 右移一位
    }
    return res;
}


int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int a, b, p;
        scanf("%d %d %d", &a, &b, &p);
        printf("%lld\n", qmi(a, b, p));
    }

    return 0;
}

---

STL学习

vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 1. 定义与初始化
    vector<int> v1;                    // 空vector
    vector<int> v2(5, 10);             // 包含5个10的vector
    vector<int> v3 = { 1, 2, 3, 4 };     // 初始化列表
    vector<int> v4(v3.begin(), v3.end());  // 用迭代器范围初始化
    vector<int> v5(v3);                // 拷贝构造

    // 2. 元素操作
    v1.push_back(100);                 // 尾部插入元素
    v1.emplace_back(200);              // C++11: 直接构造元素（效率更高）
    v1.pop_back();                     // 尾部删除元素

    // 3. 访问元素
    cout << "第一个元素: " << v3[0] << endl;    // 无边界检查
    cout << "第二个元素: " << v3.at(1) << endl;  // 有边界检查（越界抛异常）
    cout << "最后一个元素: " << v3.back() << endl;

    // 4. 修改元素
    v3[2] = 300;                       // 修改指定位置元素

    // 5. 插入与删除
    v3.insert(v3.begin() + 1, 200);    // 在位置1插入200
    v3.erase(v3.begin() + 2);          // 删除位置2的元素

    // 6. 遍历元素
    cout << "遍历v3: ";
    for (int i = 0; i < v3.size(); ++i) {
    	cout << v3.at(i) << " ";  // 输出 1 2 3 
    }
    cout << endl;

    // 7. 容量与大小
    cout << "v3大小: " << v3.size() << endl;        // 实际元素数量
    cout << "v3容量: " << v3.capacity() << endl;    // 已分配内存大小
    v3.resize(10);                     // 调整大小（不足则补默认值）
    v3.reserve(20);                    // 预分配容量，避免频繁扩容

    // 8. 二维数组（动态矩阵）
    vector<vector<int>> matrix(3, vector<int>(4, 0));  // 3行4列（可只定义行数）

    // 访问二维数组
    matrix[1][2] = 100;                // 修改第2行第3列元素

    // 遍历二维数组
    cout << "遍历二维数组:" << endl;
    for (const auto& row : matrix) {
        for (int x : row) {
            cout << x << "\t";
        }
        cout << endl;
    }

    // 9. 二维数组的动态调整
    matrix.push_back({ 1, 2, 3, 4 });    // 添加一行
    matrix[0].resize(5, 0);            // 第一行扩展为5列

    // 10. 清空与释放内存
    v3.clear();                        // 清空元素，但保留容量

    return 0;
}

string

#include <iostream>
#include <string>
using namespace std;

int main() {
    // 1. 定义与初始化
    string s1;                  // 空字符串
    string s2 = "hello";        // 直接初始化
    string s3("world");         // 构造函数初始化
    string s4 = s2 + " " + s3;  // 拼接字符串: "hello world"
    string s5(5, 'a');          // 重复字符: "aaaaa"

    // 2. 访问与修改
    cout << "s2的第1个字符: " << s2[0] << endl;      // 输出: h
    cout << "s2的第2个字符: " << s2.at(1) << endl;    // 输出: e
    s2[0] = 'H';    	 	// 修改字符: "Hello"
    s2.append(" world");    // 追加: "Hello world"
    s2 += "!";              // 追加: "Hello world!"

    // 3. 长度与容量
    cout << "s2长度: " << s2.length() << endl;      // 输出: 12
    cout << "s2容量: " << s2.capacity() << endl;    // 输出: 至少12（可能更大）
    cout << "s2是否为空: " << (s2.empty() ? "是" : "否") << endl;  // 输出: 否

    // 4. 查找与替换
    size_t pos = s2.find("world");      // 查找子串，返回位置: 6
    if (pos != string::npos) {          // 判断是否找到
        s2.replace(pos, 5, "universe"); // 替换: "Hello universe!"
    }

    // 5. 子串与截取
    string sub = s2.substr(6, 8);        // 从位置6开始截取8个字符: "universe"
    cout << "截取子串: " << sub << endl;

    // 6. 比较
    string s6 = "Hello";
    if (s6 == s2.substr(0, 5)) {         // 比较子串
        cout << "前缀相同" << endl;
    }
    // 使用compare函数（0表示相等，负数表示小于，正数表示大于）
    cout << s6.compare(s2) << endl;  // -1

    // 7. 插入与删除
    s2.insert(5, ",");    // 在位置5插入逗号: "Hello, universe!"
    s2.erase(5, 1);       // 删除位置5的字符: "Hello universe!"

    // 8. C风格字符串转换
    const char* c_str = s2.c_str();                 // 转换为const char*
    cout << "C风格字符串: " << c_str << endl;

    // 9. 遍历字符串
    cout << "遍历s2: ";
    for (char c : s2) {      // C++11范围for循环
        cout << c;
    }
    cout << endl;

    // 10. 数值转换（C++11）
    string num_str = "12345";
    int num = stoi(num_str);                       // 字符串转整数
    string back_to_str = to_string(num + 5);       // 整数转字符串
    cout << "数值转换: " << back_to_str << endl;    // 输出: 12350

    return 0;
}

unordered_map

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    // 1. 定义与初始化
    unordered_map<string, int> map;  // 键为string，值为int

    // 2. 插入元素
    map["apple"] = 10;              // 下标操作插入
    map.insert({ "banana", 20 });     // insert()插入
    map.emplace("cherry", 30);      // emplace()直接构造

    // 3. 访问元素
    cout << "apple的数量: " << map["apple"] << endl;  // 下标访问（键不存在会插入默认值）
    cout << "banana的数量: " << map.at("banana") << endl;  // at()访问（键不存在抛异常）

    // 4. 判断键是否存在
    if (map.count("cherry") > 0) {  // count()返回0或1
        cout << "找到cherry!" << endl;
    }
    auto it = map.find("cherry");
    if (it != map.end()) {
        cout << "Cherry: " << it->second << endl;
    }

    // 5. 修改元素
    map["apple"] += 5;             // 修改已存在的键值
    map["durian"] = 5;             // 插入新键值对

    // 6. 删除元素
    map.erase("banana");           // 按键删除
    map.erase(map.find("cherry")); // 按迭代器删除

    // 7. 遍历元素
    cout << "遍历map:" << endl;
	for (auto it = map.begin(); it != map.end(); ++it) {
		cout << it->first << ": " << it->second << endl;
	}

    // 8. 统计与容量
    cout << "map大小: " << map.size() << endl;

    //map.clear();
    //map.empty()
    return 0;
}

set

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;

    // 插入元素
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(2);  // 重复元素，自动忽略

    // 遍历（有序输出）
    cout << "Elements in set: ";
    for (int x : s) {
        cout << x << " ";  // 输出：1 2 3
    }
    cout << endl;

    // 查找元素
    if (s.find(2) != s.end()) {
        cout << "2 found!" << endl;
    }

    // 删除元素
    s.erase(2);
    cout << "After erase 2: ";
    for (int x : s) {
        cout << x << " ";  // 输出：1 3
    }
    cout << endl;

    // 统计元素个数
    int size = s.size();  // 返回元素数量

    // 清空set
    s.clear();  // s变为空集

    // 查找第一个大于等于x的元素（lower_bound）
    auto it = s.lower_bound(2);  // 若存在>=2的元素，返回迭代器；否则返回s.end()

    // 查找第一个大于x的元素（upper_bound）
    auto it = s.upper_bound(2);

    return 0;
}

stack

#include <iostream>
#include <stack>
using namespace std;

int main() {
    // 1. 定义栈（默认基于deque）
    stack<int> s;

    // 2. 入栈操作
    s.push(10);     // 栈顶: 10，栈内容: [10]
    s.push(20);     // 栈顶: 20，栈内容: [10, 20]
    s.emplace(30);  // C++11: 直接构造元素，栈内容: [10, 20, 30]

    // 3. 访问栈顶元素
    cout << "栈顶元素: " << s.top() << endl;  // 输出: 30

    // 4. 修改栈顶元素
    s.top() = 300;  // 栈内容: [10, 20, 300]

    // 5. 出栈操作
    s.pop();        // 移除栈顶元素(300)，栈内容: [10, 20]
    cout << "出栈后栈顶元素: " << s.top() << endl;  // 输出: 20

    // 6. 判断栈状态
    cout << "栈是否为空: " << (s.empty() ? "是" : "否") << endl;  // 输出: 否
    cout << "栈大小: " << s.size() << endl;                        // 输出: 2

    // 7. 遍历栈（只能逐个出栈）
    cout << "遍历栈: ";
    while (!s.empty()) {
        cout << s.top() << " ";  // 访问栈顶元素
        s.pop();                 // 移除栈顶元素
    }
    cout << endl;  // 输出: 20 10（注意顺序：后进先出）

    return 0;
}

queue

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 1. 定义队列（默认基于deque）
    queue<int> q;

    // 2. 入队操作
    q.push(10);      // 队尾插入元素10
    q.push(20);      // 队尾插入元素20
    q.emplace(30);   // C++11: 直接构造元素30

    // 3. 访问队首和队尾元素
    cout << "队首元素: " << q.front() << endl;  // 输出: 10
    cout << "队尾元素: " << q.back() << endl;   // 输出: 30

    // 4. 修改队首和队尾元素
    q.front() = 100;  // 队首元素变为100
    q.back() = 300;   // 队尾元素变为300

    // 5. 出队操作
    q.pop();          // 移除队首元素(100)
    cout << "出队后队首元素: " << q.front() << endl;  // 输出: 20

    // 6. 判断队列状态
    cout << "队列是否为空: " << (q.empty() ? "是" : "否") << endl;  // 输出: 否
    cout << "队列大小: " << q.size() << endl;                        // 输出: 2

    // 7. 遍历队列（只能通过出队方式）
    cout << "遍历队列: ";
    while (!q.empty()) {
        cout << q.front() << " ";  // 访问队首元素
        q.pop();                   // 移除队首元素
    }
    cout << endl;  // 输出: 20 300

    return 0;
}