历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

算法基础课笔记

作者：

月明星稀 , 2022-02-23 21:05:13 , 所有人可见 , 阅读 276

算法基础课（待完善，一边二刷一边完善）

基础算法

快速排序

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return; // 区间长度为0时就返回

    int i = l - 1, j = r + 1, x = q[l + r >> 1];

    while(i < j)
    {
        // 寻找到不满足x的左边右边的条件的数
        do i ++; while(q[i] < x); 
        do j --; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);      
    }
    //向左向右递归
    quick_sort(q, l, j); 
    quick_sort(q, j + 1, r);
}

归并排序

int tmp[N];
void merge_sort(int q[], int l, int r)
{
    if(l >= r) return; // 区间长度为0时就返回

    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r); // 向左向右递归拆分区间

    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(a[i] <= b[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    //左边或者右边的数组当中没结束的继续赋值到tmp数组
    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]; // 从[l,r] 区间，将tmp数组赋值给原数组
}

二分

整数二分

/*
个人理解，本题求解区间，也就是大于等于下限，小于等于上限
所以第一个check函数写(q[mid] >= x)，第二个写(q[mid] <= x)
*/
while(l < r) // [l, mid],[mid + 1, r]
{
    int mid = l + r >> 1;
    if(q[mid] >= x) r = mid; // 满足 (q[mid] >= x) 时，说明答案在小于等于mid的范围里，因此r = mid
    else l = mid + 1; // 而不满足时，是(q[mid] < x), 所以不能包含mid，所以将左边界更新为mid + 1
}

while(l < r) //[l, mid - 1], [mid, r]
{
    int mid = l + r + 1>> 1;
    if(q[mid] <= x) l = mid; 
    else r = mid - 1; // 如果这里减1了，就在上面求mid处加1（我是这么记的QAQ）
}

浮点数二分

const double eps = 1e-8;// 浮点数判断等于0要小于某个很小的数
//二分的区间l和r要包答案即可
while(r - l > eps)
{
    double mid = (l + r) / 2;
    if(mid * mid * mid >= x) r = mid; // mid >= x的三次根等价于mid的三次方>=x
    else l =mid;
}

高精度

加

/*
原数：123456，数组里的数：654321  
(倒叙的存储的目的是从低位开始算，方便最高位进位，否则要移动整个数组)
*/
vector<int> add(vector<int> &a, vector<int> &b)
{
    if(a.size() < b.size()) return add(b, a); //用大的加小的；在这里判断就不用在main函数中判断特殊情况了

    vector<int> res;
    int t = 0;
    for(int i = 0; i < a.size(); i ++)
    {
        t += a[i]; // 进位（如果有的话）的t + a[i] + b[i]
        if(i < b.size()) t += b[i]; //需要判断b[]是否结束
        res.push_back(t % 10);// 存储答案的时候是从个位开始存到res[0], 输出结果的时候要倒序（从最高位）输出
        t /= 10; // t如果大于等于10就进位
    }

    if(t) res.push_back(t);
    return res;
}

减

//需要判断a是否大于b。如果a > b 则a - b, 否则-(b - a)
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;
}

vector<int> sub(vector<int> &a, vector<int> &b)
{
    vector<int> res;

    int t = 0;
    for(int i = 0; i < a.size(); i ++)
    {
        t = a[i] - t; 
        if(i < b.size()) t -= b[i];
        res.push_back((t + 10) % 10); //存a[i] - b[i] 的绝对值
        if(t < 0) t = 1; //如果t小于0就要借位
        else t = 0;
    }
    //例如 123-123等于000，需要去除前导0 
    while(res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

乘

vector<int> mul(vector<int> &a, int b)
{
    vector<int> res;

    int  t = 0;
    for(int i = 0; i < a.size(); i ++)
    {
        t += a[i] * b;
        res.push_back(t % 10); // 存储答案的时候是从个位开始存到res[0], 输出结果的时候要倒序（从最高位）输出
        t /= 10;
    }
    while(t) // 处理还没算完的t
    {
        res.push_back(t % 10);
        t /= 10;
    }

    //例如12345*0的时候 等于 00000， 需要去除前导0
    while(res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

除

vector<int> div(vector<int> &a, int b, int &r)
{
    vector<int> res;
    r = 0;
    for(int i = a.size () - 1; i >= 0; i --)
    {
        r = r * 10 + a[i]; //余数*10 + 当前位
        res.push_back(r / b);
        r = r % b;
    }
    // 如果这里正序输出就是答案，但是例如123 / 10得到012，不易去除前导0
    reverse(res.begin(), res.end()); //因此要反转
    while(res.size() > 1 && res.back() == 0) res.pop_back(); //去除前导0
    return res;
}

前缀和

一维

//前缀和 S[i] = a[1] + a[2] + a[3] + ...+ a[n]
//S[l, r] =(a[1] + a[2]+ ...+ a[l - 1] + a[l] +...+ a[n]) - (a[1] + a[2]+ ...+ a[l - 1]) = S[r] - S[l - 1]

二维

s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

s[x2 , (x1 - 1)][y2 , (y1 - 1)] = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];

差分

一维

/*
思路：
1. 假设数组b满足 a[l,r]的和 = b[l] + b[l + 1] + ... + b[r - 1] + b[r];
则b是a的差分数组，a是b的前缀和

2. 如果在b[l] + c 则根据公式，a[l]之后的每一项都加上了c，因此如果只想在a[l,r]区间中的每项加上c，则需要从b[r + 1] 之后的项加上-c 
*/
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

二维

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

双指针

位运算

int lowbit(int x) // 返回x的二进制中，最后一个1
{
    return x & -x;
}
//求n的二进制表示中，第k位是几
cout << (n >> k & 1);

离散化

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

using namespace std;

typedef pair<int, int> PII;

vector<PII> add, query;
vector<int> alls;

const int N = 300010; // 这里因为需要存插入点的位置（映射后）， 还要存询问区间（左右边界）（映射后）的位置，因此要开300000的大小
int n, m;
int s[N], a[N];

int find(int 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;
}

int main()
{
    cin >> n >> m;
    while (n -- )
    {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});

        alls.push_back(x);
    }

    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);

        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }

    sort(alls.begin(), alls.end()); //排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重

    for(auto t : add)
    {
        int x = find(t.first);
        a[x] += t.second;
    }

    for(int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];

    for(auto t : query)
    {
        int l = find(t.first), r = find(t.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

区间合并

数据结构

单链表

// e[N] 存储节点 idx 的值
// ne[N] 存储节点 idx 的下一个节点的编号
//head 表示头节点
//idx 表示第几个插入的点
int e[N], ne[N], head, idx;

//初始化
void init()
{
    head = -1;
    idx = 0;
}

// 向链表头插入一个数 x
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++;
}

//在第 k 个插入的数后面插入一个数 x
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = 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]; // 要删除头节点，和remove操作一样，直接让head指向head的下一个即可
            else remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x); // 因为idx是从0 开始，所以要k - 1
        }
    }

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

双链表

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

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x; //idx节点的值等于x
    l[idx] = a, r[idx] = r[a]; //idx节点的右边是a的右边，idx节点的左边是a
    l[r[a]] = idx, r[a] = idx ++ ; // a的右边是idx节点，a之前的右边节点的左边是idx
}

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

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

    // 0是左端点，1是右端点 (左右节点相当于两个标记，没有存值，所以(op == "R")时，要在最右端的左边一位存(也就是l[1]))
    // 遍历整个链表的时候，要从最左端的右边一个单位开始(这时候才是第一个节点(即r[0]))
    r[0] = 1, l[1] = 0;
    idx = 2;
    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;
}

栈

int stk[N], tt; // tt 表示栈顶指针

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

    while (m -- )
    {
        string op;
        int x;
        cin >> op;
        if(op == "push")
        {
            cin >> x;
            stk[++ tt] = x;
        }
        else if(op == "pop") tt --;
        else if(op == "empty") cout << ( (tt == 0) ? "YES" : "NO" ) << endl; // 用tt是否等于0判断栈是否空
        else cout << stk[tt] << endl;
    }
    return 0;
}

队列

int tt, hh, q[N]; // hh 表示队头, tt表示队尾

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

    hh = 1; 
    while (m -- )
    {
        string op;
        cin >> op;
        int x;

        if(op == "push")
        {
            cin >> x;
            q[++ tt] = x;
        }
        else if(op == "pop") ++ hh;
        else if(op == "empty") 
        {
            if(tt < hh) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        else cout << q[hh] << endl;;
    }

单调栈

for(int i = 0; i < n; i ++)
{
    int x;
    scanf("%d", &x);
    while(tt && stk[tt] >= x) tt--;  // 每次读入x后，判断栈顶元素是否大于当前的x，如果大于就把栈顶元素更新为更小的x，最终这个栈就是个从下往上递减的栈
    if(tt) printf("%d ", stk[tt]);
    else printf("-1 ");
    stk[++ tt] = x;
}

单调队列

//数组q存的是下标，数组a存的是下标对应的值
int q[N], a[N], hh, tt;

for (int i = 0; i < n; i ++ )
{
    if(tt >= hh && i - k + 1 > q[hh]) hh ++; // 如果队列里有元素，且当前窗口的长度超出给定长度, 就将队头元素移出窗口
    while(tt >= hh && a[q[tt]] >= a[i]) -- tt; //如果之前插入的元素大于等于当前元素，就把它删去（为了保证当前维护的窗口从队尾到队头是单调递减的） 
    q[++ tt] = i; // (数组q中存储的是下标) 经过上一步的处理，保证队列中a[i] 之前的数都是小于a[i] 的


    if(i >= k - 1) printf("%d ", a[q[hh]]); // 按照上述规则维护的队列能保证队头就是整个窗口中最小的元素
}

KMP

char s[M], p[N];

int main()
{

    for(int i = 2, j = 0; i <= n;i ++)
    {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }


    for(int i = 1, j = 0; i <= m; i ++)
    {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        if(j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
}

Tire

/*
字典树，用树的结构存储字符串，方便查询字符串是否出现和判断字符串出现的次数
*/
//son[N][26] 第一维对应节点的下标，第二维对应'a~z'26个字母
//cnt[N] 标记以某个字母结尾的字符串的个数
//idx 类似于链表的idx 表示第几个节点
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
    int p = 0; // 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] ++; //标记以某个字母结尾的字符串的数量加一
}

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]; // 返回以某个字母结尾的字符串出现的次数（可能为0）
}

并查集

将两个集合合并
询问两个元素是否在一个集合当中
（近乎O（1）的复杂度），用树来维护

每个集合用一棵树来表示，树根的编号就是整个集合的编号

每个节点存储它的父节点 p[x] 表示x的父节点

问题一：如何判断树根if（p[x] == x）

问题二：如何求x集合编号 while （p[x] != x） x = p[x];

问题三：如何合并两个集合： px 是x的集合编号，py是y的集合编号， p[x] = y（将一个集合直接差到另一个集合中去）

优化：路径压缩，搜索一遍后，让所有元素都指向根节点

int p[N];
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]); // 如果x的父节点不是根节点，就递归寻找根节点，并将x的父节点指向根节点
    return p[x];
}
p[find(a)] = find(b); // 合并集合就是将一个集合的根节点指向另一个集合的根节点

堆（完全二叉树）（除了最后一层，上面的节点都是非空的，最后一层从左到右）

每个父节点都满足小于等于的左右两个子节点

插入一个数
求集合当中的最小值
删除最小值
删除任意一个元素
修改任意一个元素

用一维数组存储用1 表示根节点，2x表示x的左子节点，2x+1表示x的右子节点

int h[N], cnt;
void down(int u)
{
    int t = u;
    // 判断是否大于左右子节点
    if(u * 2 <= cnt && h[t] > h[u * 2]) t = u * 2; 
    if(u * 2 + 1 <= cnt && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
    if(u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

while (m -- )
{
    cout << h[1] << ' ';
    h[1] = h[cnt --]; // 删除堆顶元素，将最后一个和第一个交换，然后让堆顶元素下沉
    down(1);
}

int n, m;
//ph[k]表示第k个插入的节点在堆中的下标，hp[k]表示堆中第k个节点是第几个插入的数。
int h[N], cnt, ph[N], hp[N]; 

void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]); // 但是交换的时候无法找到堆中节点为a，b对应是第几个插入的数，因此需要h[k]，记录堆中下标为k的元素是第几个插入的元素
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

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

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

int main()
{
    cin >> n;
    m = 0;
    while (n -- )
    {
        string op;
        cin >> op;
        int k, x;
        if(op == "I")
        {
            scanf("%d", &x);
            cnt ++;
            m ++;
            ph[m] = cnt, hp[cnt] = m; // cnt是元素在堆中的下标 k是第几个插入的元素
            h[cnt] = x;
            up(cnt);
        }
        else if(op == "PM") printf("%d\n", h[1]);
        else if(op == "DM") 
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if(op == "D")
        {
            scanf("%d", &k); // 由于需要删除第k个插入的元素，因此需要ph[k]记录第k个插入的元素在堆中的下标
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }
    return 0;
}

哈希表

模拟哈希

拉链法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100003;

int n;
int h[N], e[N], ne[N], idx;

//插入的思想：假设有一个长度为N的数组，找到k映射后的哈希值，在这个哈希值后连接出链表
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;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;

    while (n -- )
    {
        string op;
        int x;
        cin >> op;
        scanf("%d", &x);
        if(op == "I") insert(x);
        else
        {
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

开放寻址法

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

using namespace std;

//开放寻址法一般开数据范围2~3倍的大小（一般足够避免冲突）
const int N = 200003, null = 0x3f3f3f3f;

int h[N];
int n;

//find(x) 返回的是x应该在数组中的位置
int find(int x)
{
    int k = (x % N + N) % N;
    while(h[k] != null && h[k] != x) // 如果当前位置上有元素，且该元素不是x，就继续查看下一个元素，直到能放进去x或找到x为止
    {
        k ++;
        if(k == N) k = 0; // 如果k已经到达数组的最大值，就从头开始找
    }
    return k;
}

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

    cin >> 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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, P = 131;

typedef unsigned long long ULL;

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

ULL get(int l, int r)
{
    // 例如 "AABBAABB" 要求AA[5,6]的哈希值，
    //就用AABBAA(h[6]) - AABB00(h[4] * p[2]) = AA  (AABB是h[l - 1]，乘上p[r - l + 1]后就是AABB00)
    return h[r] - h[l - 1] * p[r - l + 1];
}

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

    scanf("%s", str + 1);
    p[0] = 1; // P的0次幂为1
    for(int i = 1; i <= n ; i ++)
    {
        p[i] = p[i - 1] * P; // 计算P的n次幂
        h[i] = h[i - 1] * P + str[i]; 计算str前n位的哈希值，将前n位当作一个P进制的数
    }

    int l1, r1, l2, r2;
    while (m -- )
    {
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}

STL

搜索与图论

DFS

排列数字问题

const int N = 10;

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

void dfs(int u)
{
    if(u == n) // 判断递归的边界，如果是已经填满n位数，就输出答案，并回溯
    {
        for(int i = 0; i < n; i++) printf("%d ", path[i]);
        puts("");
        return ;
    }
    for(int i = 1; i <= n; i ++)
        if(!st[i]) // 如果当前数字没有被标记过，才进行处理
        {
            path[u] = i;
            st[i] = true; // 将该数字标记
            dfs(u + 1); // 向下一层递归
            st[i] = false; //恢复现场
        }
}

int main()
{
    cin >> n;
    dfs(0);
    return 0;
}

八皇后问题

第一种搜索顺序

// 按列枚举，如果该点所在列，所在正对角线，反对角线都有皇后，就跳过
const int N = 10;
bool col[N], dg[N], udg[N];
char g[N][N];
int n;

void dfs(int u)
{
    if(u == n) // 表明已经放置所有皇后
    {
        for(int i = 0; i < n; i ++) puts(g[i]);
        puts("");
        return ;
    }

    for(int i = 0; i < n; i ++)
        if(!col[i] && !dg[u + i] && !udg[n - i + u])
        {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - i + u] = true; //放皇后标记
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - i + u] = 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;
}

第二种搜索顺序

#include<iostream>

using namespace std;

const int N = 30;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s)
{
    // 递归要先处理边界
    if(y == n) y = 0 , x ++;
    if(x == n)
    {
        if(s == n)
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    //放皇后
    //多一个判断，行不能有皇后，列不能有，正反对角线上不能有
    if(!col[y] && !row[x] && !dg[x + y] && !udg[n + y - x])
    {
        g[x][y] = 'Q';
        col[y] = row[x] = dg[x + y] = udg[n + y - x] = true;
        dfs(x, y + 1, s + 1);
        col[y] = row[x] = dg[x + y] = udg[n + y - x] = false;
        g[x][y] = '.';
    }    
    //不放皇后
    dfs(x, y + 1, s);

}

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

    dfs(0, 0, 0);

    return 0;
}

BFS

走迷宫

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

using namespace std;

const int N = 110;

typedef pair<int, int> PII;

int g[N][N];
int d[N][N];
PII q[N * N];
int n, m;

int bfs()
{
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q[0] = {0, 0};


    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //上下左右四个方向

    int hh = 0, tt = 0;
    while(hh <= tt)
    {
        auto t = q[hh ++];
        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i]; // 探测下一个点
            // d[x][y] == -1 表示还没有被搜过，没有更新过距离(因为值记录第一次搜到)
            if(x >= 0 && x < n && y >= 0 && y < m && d[x][y] == -1 && g[x][y] == 0)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[++ tt] = {x, y};  //将t点上下左右满足条件的点加入队列
            }
        }
    }
    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;
}

八数码

树与图的深度优先遍历

树的重心

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


using namespace std;

const int N = 100010 , M = N * 2;
int h[N], e[M], ne[M], idx;
bool st[N];
int n;
int ans = N;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u)
{
    st[u] = true;

    // sum存储这个点加上它的所有节点的数量
    int sum = 1, size = 0; //size 存储当前这个点删掉后，每一个连通块中点的数量的最大值 
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j =e[i];
        if(!st[j])
        {
            int s = dfs(j); // s 表示当前这个点的每一个子树的大小
            size = max(size, s);
            sum += s; //sum是当前点的所有子节点的总数
        }
    }

    size = max(size, n - sum); //除了当前这个点和它的子树，另一个连通块的大小
    ans = min(ans, size);

    return sum ;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs(n);

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

    return 0;
}

树与图的广度优先遍历

树的层次

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

using namespace std;

const int N = 100010, M = N * 2;

int h[N], e[M], ne[M], idx;
int n, m;
int d[N]; // bfs 可以将距离初始化为-1，如果等于-1表示没搜过（就不需要st[]标记）
int q[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs()
{
    memset(d, -1, sizeof d);

    q[0] = 1;
    d[1] = 0;

    int hh = 0, tt = 0;

    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++ tt] = j;
            }
        }
    }
    return d[n];
}

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

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

    cout << bfs();
    return 0;
}

拓扑排序

// 如果图中有环，则存在某些点无法拓扑排序（因为在环中找不到入度为0的点）
// 反之，如果没有环，就可以找到入度为0的点，然后一个一个的突破
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx;
int n, m;
int d[N], q[N];

void add(int a, int b) 
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}


bool topsort()
{
    int tt = -1, hh = 0;

    for(int i = 1; i <= n; i ++)
        if(!d[i]) q[ ++ tt] = i;

    while(hh <= tt)
    {
        int t = q[hh ++]; // 取出队头元素（bfs）， 遍历当前这个点的所有出度

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j] -- ; // j这个点的入度为零时，表明它前面的点都已经排好序了，因此j也可以加入队列中，寻找它的出度
            if(d[j] == 0)
                q[++ tt] = j;
        }
    }

    return tt == n - 1; // 将所有点的入度减为0， 表明没有环，存在拓扑序
}

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

    memset(h, -1, sizeof h);

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

        d[b] ++ ;
    }

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

    return 0;
}

Dijkstra

朴素Dijkstra(稠密图)

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

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); // 所有距离初始化为正无穷
    dist[1] = 0; // 到第一个点的距离为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还没开始找，或者这个点到起点的距离比t到起点的距离小)
                t = j; // 用当前还未标记的点中，距离最小的点来操作

        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]); // 更新到j点的距离，取直接到j点和先到t再从t到j中最小的路径

        st[t] = true; // 使用过t点更新其他点，标记为true
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> 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);
    }
    cout << dijkstra() << endl;

    return 0;
}

堆优化Dijkstra(稀疏图)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;


typedef pair<int, int> PII;

const int N = 200010;

int h[N], e[N], w[N], ne[N], idx;
int n, m;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}


int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    dist[1] = 0;
    heap.push({0, 1});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if(st[ver]) continue;

        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];

}

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

    memset(h, -1, sizeof h);

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

    cout << dijkstra() << endl;

    return 0;
}

bellman-ford

// 求解有负权边的最短路问题
// 如果最多k次遍历，则循环k次，每次循环遍历每条边，对每条边进行松弛操作
// 最终， dist[b] <= dist[a] + w;

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

using namespace std;

const int N = 510, M = 10010;

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

int n, m, k;
int dist[N], backup[N];

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for(int i = 0; i < k; i ++)
    {
        memcpy(backup, dist, sizeof dist); // 因为在一次循环中，可能会用之前更新的结果来更新下一条边，为了避免这种情况，要用上一次的结果来更新
        for(int j = 0; j < m; j ++)
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], backup[e.a] + e.c);
        }
    }
}

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

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

    bellman_ford();

    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else cout << dist[n];

    return 0;
}

spfa

求最短路

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

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i]) // 只有当前边更新变小过，它才有可能去更新其他边
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true; // 标记j这个点有没有在队列中
                }
            }
        }
    }
    return dist[n];
}

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

    memset(h, -1, sizeof h);

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

    int t = spfa();

    if(t == 0x3f3f3f3f) puts("impossible");
    else cout << t;

    return 0;
}

求负环

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

using namespace std;

const int N = 2010, M = 10010;

int h[N], e[M], idx, ne[M], w[M];
int n, m;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool spfa()
{
    queue<int> q;
    for(int i = 1; i <= n; i ++) // 每个点出发都要判断有无负环
    {
        q.push(i);
        st[i] = true;
    }

    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1; // 每次能更新的时候说明距离变小，经过的边数多了一条

                if(cnt[j] >= n) return true; //当有经过n条边的时候说明经过n + 1个点，说明一定存在负环
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }


    return false;
}

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

    memset(h, -1, sizeof h);

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

        add(a, b, c);
    }

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

    return 0;
}

Floyd

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

using namespace std;

const int N = 210;
int n, m, k;
int g[N][N];

// floyd 用dp的思想
void floyd()
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

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

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j++)
            if(i == j) g[i][i] = 0;
            else g[i][j] = 0x3f3f3f3f;

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

    floyd();

    while(k -- )
    {
        int x, y;
        scanf("%d%d", &x, &y);

        int t = g[x][y];
        if(t > 0x3f3f3f3f / 2) puts("impossible");
        else cout << t << endl;
    }

    return 0;
}

Prim

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

using namespace std;

const int N = 510;

int g[N][N];
int dist[N];
int n, m;
bool st[N];

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] == 0x3f3f3f3f) return 0x3f3f3f3f; //

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

int main()
{
    cin >> 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 == 0x3f3f3f3f) puts("impossible");
    else cout << t << endl;

    return 0;
}

Kruskal

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

using namespace std;

const int N = 200010;

int n, m;
int cnt;
int p[N];
struct Edge
{
    int a, b, w;

    bool operator < (const Edge &W) const
    {
        return w < W.w;
    }
}edge[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

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

    int a, b, c;
    for(int i = 0; i < m; i ++)
    {

        scanf("%d%d%d", &a, &b, &c);
        edge[i] = {a, b, c};
    }

    sort(edge, edge + m);

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

    int res = 0;
    for(int i = 0; i < m; i ++)
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;

        a = find(a), b = find(b);

        if(a != b)
        {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }

    if(cnt < n - 1) cout << "impossible";
    else cout << res;

    return 0;
}

染色法判定二分图

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

using namespace std;

const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = 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, c % 2 + 1)) return false; // 1，2交替，如果搜的结果不对就返回false
        }
        else if(color[j] == c) return false; // 如果当前点和它相邻的点颜色相同，则不是二分图
    }
    return true;
}

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

    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]) // 如果还没染色，就进入搜索
        {
            if(!dfs(i, 1)) // 如果搜索不对，即不是二分图
            {
                flag = false;
                break;
            }
        }
    }

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

    return 0;
}

匈牙利算法

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

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

void add(int a, int b) 
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

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 main()
{
    cin >> 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); // 这里每次都要设置为false，下一个男生才能去尝试所有和自己相连的女生
        // 有没有匹配是从两个角度判断的： 
        //1.st[j] 表明男生已经和某个女生匹配过了，下一个男生想来挖这个墙角的时候就不能和这个女生匹配了
        //2.match[j] 记录和j女生匹配的男生是x这一信息， 如果下一个女生想和j匹配，就看看之前匹配的x男生还有没有下家
        if(find(i)) res ++;
    }

    cout << res;

    return 0;
}

数学知识

质数

试除法求质数

bool is_prime(int x)
{
    if(x < 2) return false;
    // 用x / i的写法避免x超出int范围
    for(int i = 2; i <= x / i; i ++) // 如果b是n的约数，那么n/b也是n的约数，因此判断sqrt(n)的范围即可
        if(x % i == 0) return false;
    return true;
}

分解质因数

void divide(int x)
{
    for(int i = 2; i <= x / i; i ++)
        if(x % i == 0)
        {
            int s = 0;
            while(x % i == 0) s ++, x /= i; // 如果i是x的质因数，会在这一步将x中的i质因数除干净，因此枚举到的i一定是x的质因数
            printf("%d %d\n", i, s);
        }

    if(x > 1) cout << x << ' ' << 1 << endl; // 循环结束后，因为只会枚举小于等于sqrt(x)的因数，因此话要输出剩余的质因数，且该质因数只会存在一个，如果存在2个，就会大于x
    cout << endl;
}

埃氏筛法

void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(st[i]) continue; // 如果i是质数才继续到下一步，i不是质数就跳过
        primes[cnt++] = i;
        for(int j = i + i; j <= n; j += i) // 枚举质数的倍数
            st[j] = true;
    }
}

线性筛

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; primesp[j] <= n / i; j ++)
        {
            st[primes[j] * i] = false;
            if(i % primes[j] == 0) break;
        }
    }
}

约数

试除法求约数

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); // 例如 25 / 5 = 5 就不能加入答案
        }
    }
    sort(res.begin(), res.end());
    return res;
}

约数个数

// x = a1^p1*a2^p2*...*an^pn 任何一个数都可以表示乘若干个质数的乘积
//且它的所有约数也可以用这些质数表示
unordered_map<int, int> primes;

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

    for(int i = 2; i <= x / i; i ++)
    {
        while(x % i == 0) primes[i] ++, x /= i; 求每个质因数的指数
    }
    if(x > 1) primes[x] ++ ;
}

LL res = 1;
for(auto p : primes) res = res * (p.second + 1) % mod; 利用公式：约数个数 = (a1 + 1)*(a2 + 1)*...*(an + 1)

约数之和

//x = a1^p1*a2^p2*...*an^pn
while (n -- )
{
    int x;
    cin >> x;
    for (int i = 2; i <= x / i; i ++ )
        while(x % i ==0) primes[i] ++, x /= i;
    if(x > 1) primes[x] ++;
}

LL res = 1;
for(auto p : primes)
{
    int a = p.first, b = p.second;
    LL t = 1;
    while(b --) t = (t * a + 1) % mod;  //约数和 = (a1^0 + a1^1 + ... + a1^p1)*(a2^0 + a2^1 + ... + a2^p2)*...*(an^0 + an^1 + ... + an^pn)
    res = res * t % mod;
}

最大公约数

// 辗转相除法， a和b的最大公约数与b和a%b的最大公约数相同
int gcd(int a, int b)
{
    return b? gcd(b, a % b): a;
}

欧拉函数

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

using namespace std;

int phi(int x)
{
    int res = x;
    for(int i = 2; i <= x / i; i ++)
    {
        if(x % i == 0)
        {
            res = res / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) res = res / x * (x - 1);
    return res;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a;
        scanf("%d", &a);
        cout << phi(a) << endl;
    }
    return 0;
}

筛法求欧拉函数

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

using namespace std;

const int N = 1000010;

typedef long long LL;

int phi[N];
int primes[N], cnt;
bool st[N];

void get_eulers(int n)
{
    phi[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) 
        {
            primes[cnt ++] = i;
            phi[i] = i - 1; // 如果i是质数，则1 ~ i - 1都和它互质
        }
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j]; // 如果 i 有pj这个质因数，那么i分解质因数后，因为能整除，所以只是pj这个质数的系数多了1，由于欧拉函数与指数无关，因此只需将系数N 变为primes[j] * i
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] -1); // 因为不能整除，所以多了pj这个质数项，(primes[j] -1)是化简后的表达式
        }
    }
}

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

    get_eulers(n);

    LL res = 0;
    for(int i = 1; i <= n; i ++) res += phi[i];
    cout << res;

    return 0;
}

快速幂

// 思路：预处理出a的2次方的0次方到a的2次方的logk次方的值
// 将k转化为二进制，则k可以表示为一系列2的n次方的和
// 则a的k次方就等于 a的(k表示为一系列2的n次方的和)次方
// 则a的k次方就等于 一系列a的2次方的n次方 的乘积
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

LL qmi(int a, int k, int p)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = res * a % p; // 从低位开始处理， 如果k的转化为二进制的最低位为1，结果乘a的2次方的n次方
        k >>= 1;
        a = (LL)a * a % p; // 递推公式
    }

    return res;
}

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

    return 0;
}

快速幂

#include <iostream>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
    LL res = 1;

    while(k)
    {
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = (LL) a * a % p;
    }

    return res;
}

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


    while (n -- )
    {
        int a, p;

        scanf("%d%d", &a, &p);
        if(a % p == 0) puts("impossible");
        else printf("%d\n", qmi(a, p - 2, p)); // 由费马定理得出的共公式
    }
    return 0;
}

扩展欧几里得算法

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

using namespace std;

int exgcd(int a, int b, int & x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y -= a / b * x; // a 的系数 还是x， b 的系数变为(y - a / b * x);
    return d;
}

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

    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int x, y;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
    return 0;
}

扩展欧几里得算法求线性同余方程

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

using namespace std;

typedef long long LL;

int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

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

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

        int x, y;
        int d = exgcd(a, m, x, y);

        if(b % d) puts("impossible");
        else cout << ((LL)b / d * x % m) << endl;
    }

    return 0;
}

中国剩余定理

高斯消元

求组合数

容斥原理

博弈论

动态规划

背包问题

01背包

/*
状态表示：f[i,j] 表示所有从0 ~ i件物品中选，总体积不超过j的选法
状态计算：考虑第i件物品，根据第i个物品选或不选，分为2类
1. 第i个物品不选，也就是从i - 1 中选
2. 第i个物品选，也就是所有情况都选了第i个物品，则只需让从i - 1中选的最大值再加上第i个物品的价值即可（当然，总体积因为选了i，所有要j - vi（因此要记得判断））
*/

// 二维写法
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
int v[N], w[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];


    for(int i = 1; i <= n; i ++)    
        for(int j = 0; j <= m; j ++)
        {
            f[i][j] = f[i - 1][j]; // i 不选
            if(j >= v[i])f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); // i 选
        }

    cout << f[n][m];

    return 0;
}


//一维写法
// f[i][j] = f[i - 1][j]; 这句话可以看到，第一维的更新之和上一次更新有关，因此可以删去
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];
int v[N], w[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];


    for(int i = 1; i <= n; i ++)    
        for(int j = m; j >= v[i]; j --) // 但是删去第一维，j需要从最大体积开始枚举
        // 因为，如果正着枚举 f[j] 可能会被 f[j - vi]更新(此时表示i已经选进去了)，当 j = j + vi 时 f[j] 又有可能会被f[j - vi] = f[j](将j = j + vi 带入) 更新 ，此时相当于选了两次i，不满足01背包问题
            f[j] = max(f[j], f[j - v[i]] + w[i]);


    cout << f[m];

    return 0;
}

完全背包

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

using namespace std;

const int N = 1010;

int n, m;
int f[N];
int v[N], w[N];

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

    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];


    for(int i = 1; i <= n; i ++)
        for(int j = v[i]; j <= m; j ++) 
            f[j] = max(f[j], f[j - v[i]] + w[i]);


    cout<< f[m] << endl;        

    return 0;
}

多重背包

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

using namespace std;

const int N = 110;

int n, m;
int f[N][N];
int v[N], w[N], s[N];

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

    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i] >> s[i];


    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++) // 枚举每个物品选多少个
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k); 

    cout << f[n][m] << endl;
    return 0;
}

多重背包之二进制优化

/*
思路 ： 将数量s 拆分成若干个2的n次方的表达, 那么v和w也可以拆分
此时就可以在拆分后的v和w中选（转化为01背包问题）
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;
int cnt;
int n, m;
int v[N], w[N];
int f[M];

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

    cnt = 0;
    for(int i = 1; i <= n; i ++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k = k * 2;
        }
        if(s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }


    }
    n = cnt;

    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

分组背包

// 类似于01背包，但是要枚举选哪个物品
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

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

    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        for(int j = 0; j < s[i]; j ++)
            cin >> v[i][j] >> w[i][j];
    }

    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= 0; j --)
            for(int k = 0; k < s[i]; k ++)
                if(v[i][k] <= j)
                f[j]= max(f[j], f[j - v[i][k]] + w[i][k]);


    cout << f[m] << endl;


    return 0;
}

线性DP

数字三角形

/*
状态表示： f[i][j], 所有从起点走到(i,j)这个点的路径
状态计算： 从左上(i - 1, j - 1)到(i,j) 这个点的路径和从右上(i - 1, j)到(i,j) 这个点的路径
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N =  510;
int n;
int a[N][N];
int f[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];

    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= i + 1; j ++)
            f[i][j] = -1e9; // 在原三角形周围再扩大一圈来处理边界问题

    f[1][1] = a[1][1]; // 表示第一个点从(1, 1) 这个点来，且距离时a[1][1]

    for(int i = 2; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    int res = -1e9;
    for(int i = 1; i <= n; i ++)
        res = max(res, f[n][i]); 

    cout << res << endl;

    return 0;
}

最长上升子序列

/*

f[i] 表示所有以i结尾的子序列
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int n;
int a[N];
int f[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    for(int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for(int j = 1; j < i ;j ++)
            if(a[j] < a[i])
            {   
                f[i] = max(f[i], f[j] + 1);

            }
    }

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

    cout << res << endl;

    return 0;
}

// 求方案版本

最长上升子序列 II

最长公共子序列


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    cin >> a + 1 >> b + 1;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m] << endl;

    return 0;
}

// 求方案的版本
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N], res[N];
int f[N][N];
int p[N][N]; // 用p数组来记录状态转移的路径，1表示从对角线转移过来，2表示从左边，3表示从上边

int main()
{
    cin >> n >> m;
    cin >> a + 1 >> b + 1;

    for(int i =1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            if(a[i] == b[j]) 
            {
                f[i][j] = f[i - 1][j - 1] + 1;
                p[i][j] = 1;
            }
            else if(f[i - 1][j] > f[i][j - 1])
            {
                f[i][j] = f[i - 1][j];
                p[i][j] = 2;
            }
            else 
            {
                f[i][j] = f[i][j - 1];
                p[i][j] = 3;
            }
        }

    int i = n, j = m;
    int k = f[n][m];
    while(i > 0 && j > 0)
    {
        if(p[i][j] == 1)
        {

            res[k] = a[i];
            i --, j --;
            k --;
        }
        else if(p[i][j] == 2) i --; //从左边转移过来的
        else j --; //从上边转移过来的
    }

    for (int i = 1; i <= f[n][m]; i ++ ) printf("%c " ,res[i]);
    return 0;
}

最短编辑距离

/*
f[i][j]表示将a[1 ~ i] 变为b[1 ~ j] 所需的步数
1.删除a的最后一个， a的前i-1和b的前j相同，即f[i - 1][j] + 1 
2.增加a的最后一个,  b的前j-1和a的前i相同，即f[i][j - 1] + 1 
3.替换(如果a[i] == b[j] 就不用操作) a的前i-1和b的前j-1相同 即f[i - 1][j - 1] + 1
上述三种情况的最小值
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

int main()
{
    cin >> n >> a + 1 >> m >> b + 1;

    for(int i = 0; i <= n; i ++) f[i][0] = i;
    for(int i = 0; i <= m; i ++) f[0][i] = i;

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if(a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }

    cout << f[n][m];

    return 0;
}

区间DP

石子合并

// f[i][j] 表示所有将第i到j堆石子合并的方式
// 根据最后一次划分的不同，分为左1堆右k-1堆，左2右k-2...左k-1右1 即：a[i][k] 到 a[k + 1][j]
// 则状态计算就是左边部分合并的代价加上右边合并的代价再加最后一步合并的代价 
// 即 对所有k取最小值 min(f[i][k] + f[k + 1][j] + s[j] - s[i - 1])
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int n;
int s[N];
int f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> s[i];

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

    for(int len = 2; len <= n; len ++)
        for(int i = 1; i + len - 1 <= n; i ++)
        {

            int l = i, r = i + len - 1;
            f[l][r] = 1e8;
            for(int k = l; k < r; k ++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }    

    cout << f[1][n] << endl;

    return 0;
}

计数类DP

整数划分


/*
    完全背包版本：f[i,j]表示从前i个物品中选，总体积恰好为j的方案数
    依据 i选或不选，状态转移方程就是 f[i][j] = f[i - 1][j] + f[i][j - i] （不选i的方案数加上选若干个i的方案数）
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];

int main()
{
    cin >> n;
    f[0] = 1;

    for(int i = 1; i <= n; i ++)
        for(int j = i; j <= n; j ++)
            f[j] = (f[j] + f[j - i]) % mod;


    cout << f[n] << endl;

    return 0;
}

/*
f[i][j] 表示总和为i，且总个数为j的选法
依据所选的方案中有没有1，分为：
1. 有1，减去一个1，f[i - 1][j - 1]
2. 没有1，每个选择的数都减去1，f[i - j][j]
f[i][j] = f[i - 1][j - 1] + f[i - j][j]


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

using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];

int main()
{
    cin >> n;

    f[1][1] = 1;
    for(int i = 2; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;
    cout << res << endl;

    return 0;
}
*/

数位统计DP

状态压缩DP

树形DP

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

using namespace std;

const int N = 6010;
int n;
int happy[N];
int h[N], ne[N], e[N], idx;
bool has_father[N];
int f[N][2];

void add(int a, int b) 
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    f[u][1] = happy[u]; // 选u这个点，就把高兴度赋值给它

    for(int i = h[u]; i != - 1; i = ne[i])
    {
        int j = e[i];

        dfs(j); // 求以j为根节点的情况

        f[u][1] += f[j][0]; // 如果选了根节点，那么它的子节点就不能选，也就是加上不选子节点的高兴度
        f[u][0] += max(f[j][0],f[j][1]); // 不选根节点，就是计算子节点选还是不选哪个高兴度更大
    }

}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1 ; i <= n ; i ++) cin >> happy[i];

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        has_father[a] = true;
    }

    int root = 1; // 寻找根节点，也就是没有父节点的点
    while(has_father[root]) root ++;

    dfs(root);

    printf("%d\n", max(f[root][0], f[root][1])); // 答案就是判断选根节点和不选根节点哪个更大

    return 0;
}

记忆化搜索

滑雪

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

using namespace std;

const int N = 310;

int n, m;
int g[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
    int &v = f[x][y];
    if(v != -1) return v;

    v = 1;
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1 && a <= n && b >= 1 && b <= m && g[a][b] < g[x][y])
            v = max(v, dp(a, b) + 1);
    }
    return v;
}

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

    memset(f, -1, sizeof f);

    int res = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            res = max(res, dp(i, j));

    cout << res << endl;

    return 0;
}

算法基础课笔记

算法基础课 （待完善， 一边二刷一边完善）

基础算法

快速排序

归并排序

二分

整数二分

浮点数二分

高精度

加

减

乘

除

前缀和

一维

二维

差分

一维

二维

双指针

位运算

离散化

区间合并

数据结构

单链表

双链表

栈

队列

单调栈

单调队列

KMP

Tire

并查集

每个集合用一棵树来表示，树根的编号就是整个集合的编号

每个节点存储它的父节点 p[x] 表示x的父节点

问题一 ： 如何判断树根if（p[x] == x）

问题二： 如何求x集合编号 while （p[x] != x） x = p[x];

问题三： 如何合并两个集合 ： px 是x的集合编号，py是y的集合编号， p[x] = y（将一个集合直接差到另一个集合中去）

优化： 路径压缩，搜索一遍后，让所有元素都指向根节点

堆（完全二叉树）（除了最后一层，上面的节点都是非空的，最后一层从左到右）

每个父节点都满足小于等于的左右两个子节点

用一维数组存储 用1 表示根节点，2x表示x的左子节点，2x+1表示x的右子节点

哈希表

模拟哈希

拉链法

开放寻址法

字符串哈希

STL

搜索与图论

DFS

排列数字问题

八皇后问题

第一种搜索顺序

第二种搜索顺序

BFS

走迷宫

八数码

树与图的深度优先遍历

树的重心

树与图的广度优先遍历

树的层次

拓扑排序

Dijkstra

朴素Dijkstra(稠密图)

堆优化Dijkstra(稀疏图)

bellman-ford

spfa

求最短路

求负环

Floyd

Prim

Kruskal

染色法判定二分图

匈牙利算法

数学知识

质数

试除法求质数

分解质因数

埃氏筛法

线性筛

算法基础课（待完善，一边二刷一边完善）

问题一：如何判断树根if（p[x] == x）

问题二：如何求x集合编号 while （p[x] != x） x = p[x];

问题三：如何合并两个集合： px 是x的集合编号，py是y的集合编号， p[x] = y（将一个集合直接差到另一个集合中去）

优化：路径压缩，搜索一遍后，让所有元素都指向根节点

用一维数组存储用1 表示根节点，2x表示x的左子节点，2x+1表示x的右子节点