算法基础模板

时空复杂度分析

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，C++代码中的操作次数控制在10⁷～10⁸为最佳。下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择:

1. n ≤ 30，指数级别，dfs+剪枝，状态压缩dp
2. n ≤ 100 => O(n³)，floyd，dp，高斯消元
3. n ≤ 1000 =>O(n²)，O(n²logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
4. n ≤ 10000 => o(n * \(\sqrt{n}\))，块状链表、分块、莫队
5. n ≤ 100000 => O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
6. n ≤ 1000000 =>O(n)，以及常数较小的O(nlogn)算法 => 单调队列、hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的O(nlogn)的做法: sort、树状数组、heap、dijkstra、spfa
7. n ≤ 10000000 => o(n)，双指针扫描、kmp、AC自动机、线性筛素数
8. n ≤ 109=> o(\(\sqrt{n}\))，判断质数
9. n ≤ 1018 => o(logn)，最大公约数，快速幂，数位DP
10. n ≤ 101000 => o((logn)²)，高精度加减乘除
11. n ≤ 10100000 => o(logk x loglogk)，k表示位数，高精度加减、FFT/NTT

基础算法-模板

排序

//快排
void quick_sort(int q[], int l, int r){
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j){
        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);
}
//归排
void merge_sort(int q[], int l, int r){
    if (l >= r) return;
    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 (q[i] <= q[j]) tmp[k ++] = q[i ++];
    	else tmp[k ++] = q[j ++];
    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] = q[j ++];
    
    for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}

二分

// 整数二分
bool check(int x){} // 查找x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:符合条件的第一个位置
int bsearch_1(int l, int r){
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;  // check(mid) 判断 [l,mid] 这个区间是否满足条件
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:符合条件的最后一个位置
int bsearch_2(int l, int r){
    while (l < r){
        int mid = l + r + 1 >> 1; // + 1 的原因是 l + r >> 1 有可能 == l , l = mid 这条就会导致死循环
        if (check(mid)) l = mid;  // check(mid) 判断 [mid,r] 这个区间是否满足条件
        else r = mid - 1;
    }
    return l;
}

// 浮点数二分
double bsearch_3(double l, double r){
    const double eps = 1e-6;	// 查找的精度
    while (r - l > eps){
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度

// 加法
vector<int> add_plus(vector<int> &a, vector<int> &b){		//数组元素都是倒置
    if (a.size() < b.size()) return add_plus(b,a);
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++){
        t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}
//减法   C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &a, vector<int> &b){
    vector<int> c;
    for (int i = 0, t = 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;
        else t = 0;
    }

    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
//高精×低精 C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &a, int b){
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || t; i ++ ){
        if (i < a.size()) t += A[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
//高精÷低精 A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &a, int b, int &r){
    vector<int> c;
    r = 0;
    for (int i = a.size() - 1; i >= 0; i -- ){
        r = r * 10 + A[i];
        c.push_back(r / b);
        r %= b;
    }
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

前缀和

//一维
s[i] = s[i - 1] + a[i];
[x1,x2]的和 sum = s[x2] - s[x1 - 1];
//二维
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
[(x1,y1),(x2,y2)]的和 sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];

差分

//一维差分			思路: 存数按询问方式操作
给区间[l, r]中的每个数加上c: B[l] += c, B[r + 1] -= c
//二维差分
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

位运算

① &: 与 ② |: 或 ③ ^: 异或同0异1 ④ ~: 取反 ⑤ <<: 左移 ⑥ >>: 右移

//求n的二进制的第k位数字:n >> k & 1; 19 10011
cout << (19 >> 4 & 1) << endl; //1
cout << (19 >> 3 & 1) << endl; //0
cout << (19 >> 2 & 1) << endl; //0
cout << (19 >> 1 & 1) << endl; //1
cout << (19 >> 0 & 1) << endl; //1
//求n的二进制的最后一位1的位置lowbit(n) = n&-n; 20 10100
cout << (20&-20) << endl;//4

双指针

for (int i = 0, j = 0; i < n; i ++ ){
    while (j < i && check(i, j)) j ++ ;
    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

离散化

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n
}

区间合并

void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for (auto seg : segs){
        if (ed < seg.first){
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
}

数据结构-模板

单链表

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init(){
    head = -1;
    idx = 0;
}
// 在链表头插入一个数a
void insert(int a){
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 在结点k后插入一个数x
void add(int k, int x){
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
// 将头结点删除，需要保证头结点存在
void remove(){
    head = ne[head];
}

双链表

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
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 ++; // 旧节点连新	
}

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

// 遍历单链表
for (int i = h[k]; i != -1; i = ne[i])
        x = e[i];

单调栈

//常见模型：找出每个数左边离它最近的比它大/小的数
int stk[N],tt = 0;	// 栈中存数据或下标
for (int i = 1; i <= n; i ++){
    int x; cin >> x;
    while (tt && stk[tt] >= x) tt -- ;	// 左边比它小的数
    stk[ ++ tt] = i;	// 把当前值放在合适地方
}

单调队列

//常见模型：找出滑动窗口中的最大值/最小值
int a[N],q[N]; // q[N] 存的是a数组的下标
int hh = 0, tt = -1;   // hh 队头(左) tt 队尾(右) 
for (int i = 0; i < n; i ++){
    while (hh <= tt && check_out(q[hh])) hh ++ ;  	// 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ; 	// 舍去不合理数据
    q[ ++ tt] = i;					// 把当前数据的坐标插入适合的地方
}

KMP

// s[1-m]是长文本，p[1-n]是模式串，m是s的长度，n是p的长度
// 求next
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 && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++;
    if (j == n) {
        printf("%d ",i - n);
        j = ne[j];
    }
}

Tree树

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点	【实质是多开*26空间记录每个节点的信息】【这个26是根据提目要求具体有所变化】
// cnt[]存储以每个节点结尾的单词数量
// idx 节点编号

// 插入一个字符串
void insert(char *str){
    int p = 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;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

(1)朴素并查集：
    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x){
        if (p[x] != x) p[x] = find(p[x]);	// 路径压缩
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);

(2)维护size的并查集:
    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x){
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

(3)维护到祖宗节点距离的并查集:
    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x){
        if (p[x] != x){
            int u = p[x];  // u记录旧的父节点
			p[x] = find(p[x]); // 路径压缩，新父节点变成根节点了
			d[x] += d[u];  // x到新父节点的距离等于x到旧父节点的距离加上旧父节点到根节点的距离
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

// 240. 食物链 ------ (3)维护到祖宗节点距离的并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N];
int find(int x) {
    if (p[x] != x) {
        int u = p[x];  // u记录旧的父节点
		p[x] = find(p[x]); // 路径压缩，新父节点变成根节点了
		d[x] += d[u];  // x到新父节点的距离等于x到旧父节点的距离加上旧父节点到根节点的距离
    }
    return p[x];
}
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) {                                       //x和y是同类
                if (px == py && (d[x] - d[y]) % 3) res ++ ;     //如果d[x]=d[y]说明距离相等
                else if (px != py) {                            //更新
                    p[px] = py;
                    d[px] = d[y] - d[x];                        //(d[x]+?-d[y])%3==0
                }
            }else {                                             //x和y不是同类
                if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];                    //(d[x]+?-d[y]-1)%3==0
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

堆

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第 k 个插入的点在堆中的位置
// hp[J]存储堆中下标为 J 的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int i, int j){	        // 交换i节点和j节点(附带更新是第几个插入的节点)
    swap(ph[hp[i]],ph[hp[j]]);    	//更新 i 和 j ph 信息 
    swap(hp[i], hp[j]);			//更新 i 和 j hp 信息
    swap(h[i], h[j]);			//交换 i 和 j 数值
}

void down(int u){	// 向下更新
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;	// 左孩子
    if (u * 2 + 1 <= size && 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;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

哈希表

(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    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;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x){
        int t = (x % N + N) % N;	// N 一般取 大于数据范围的素数
        while (h[t] != null && h[t] != x){
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

字符串哈希

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ ){
    h[i] = h[i - 1] * P + str[i];// 这个str[i]只要不是0就行任意值都行，因此不需要转成1-26
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
// 由于h数组的特殊定义,h数组前面都是哈希值的高位,所以l-r的哈希值可以通过
// 类似, l=123,r=123456,r-l哈希值等于123456-123000
ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}

STL

vector:变长数组,倍增的思想
     vector<int> a(10),a(10,1); // 长度10，且初始化为1
     vector<int> a[10];	// 10个vector
    【size()返回元素个数】   【empty()返回是否为空】   【clear()清空】   【front()/back()】
    【push_back()/pop_back()】   【begin()/end()】   【[数组]】   【支持比较运算，按字典序】

pair<int, int>
    【first, 第一个元素】   【second, 第二个元素】
    【支持比较运算,以first为第一关键字,以second为第二关键字(字典序)】
    【p = make_pair(10,20); p = {10,20};】

string，字符串
    【size()/length()返回字符串长度】  【empty()】  【clear()】
    【substr(起始下标,(子串长度))返回子串】  【c_str()返回字符串所在字符数组的起始地址】

queue, 队列
    【size()】      【empty()】     【push()向队尾插入一个元素】     【front()返回队头元素】
    【back()  返回队尾元素】      【pop()  弹出队头元素】

priority_queue, 优先队列，默认是大根堆		【黑科技:插入负数就是小根堆】
    【size()】      【empty()】      【push()插入一个元素】       【top()返回堆顶元素】
    【pop()弹出堆顶元素】    【定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;】

stack, 栈
    【size()】 【empty()】  【push()向栈顶插入一个元素】  【top()返回栈顶元素】  【pop()弹出栈顶元素】

deque, 双端队列
    【size()】   【empty()】   【clear()】   【front()/back()】    【push_back()/pop_back()】
    【push_front()/pop_front()】    【begin()/end()】    【[数组/随机访问]】

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    【size()】  【empty()】  【clear()】  【begin()/end()】  【++,-- 返回前驱和后继,时间复杂度 O(logn)】

set(无重复)/multiset(可重复)
    【insert()  插入一个数】  【find()  查找一个数】  【count()  返回某一个数的个数】
    【erase()】
         (1) 输入是一个数x，删除所有x   O(k + logn)
         (2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
    【lower_bound(x)  返回大于等于x的最小的数的迭代器】
    【upper_bound(x)  返回大于x的最小的数的迭代器】
map/multimap
    【insert()  插入的数是一个pair】   【erase()  输入的参数是pair或者迭代器】    【find()】
    【[下标索引]  注意multimap不支持此操作。 时间复杂度是 O(logn)】  【lower_bound()/upper_bound()】

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []
    count()  返回有多少个1
    any()  判断是否至少有一个1
    none()  判断是否全为0
    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

搜索与图论-模板

树与图的存储

树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。

1. 邻接矩阵: g[a][b]存储边a->b

2. 邻接表:

   // 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
   int h[N], e[N], ne[N], idx;
   
   // 添加一条边a->b
   void add(int a, int b){
       e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
   }
   
   // 初始化
   idx = 0;
   memset(h, -1, sizeof h);
   

树与图的遍历

时间复杂度O(n ＋ m), n表示点数，m表示边数

1. 深度优先搜索

   int dfs(int u){
       st[u] = true; // st[u] 表示点u已经被遍历过
   
       for (int i = h[u]; i != -1; i = ne[i]){
           int j = e[i];
           if (!st[j]) dfs(j);
       }
   }
   

2. 宽度优先搜索

   queue<int> q;
   st[1] = true; // 表示1号点已经被遍历过
   q.push(1);
   
   while (q.size()){
       int t = q.front();
       q.pop();
   
       for (int i = h[t]; i != -1; i = ne[i]){
           int j = e[i];
           if (!st[j]){
               st[j] = true; // 表示点j已经被遍历过
               q.push(j);
           }
       }
   }
   

拓扑排序

时间复杂度 O(n+m)，n表示点数，m表示边数

int q[N],d[N]; // q模拟队列，d记录入度
bool topsort(){
    int hh = 0, tt = -1;
    
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;	// 度为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] == 0)	// 度为0的点入队
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列;否则不存在拓扑序列。
    return tt == n - 1; // 1 说明有n个节点入过队列
}

朴素dijkstra算法

时间复杂是O(n²+m), n表示点数, m表示边数

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ ){
        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]);
        
        st[t] = true;
    }

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

堆优化版dijkstra

时间复杂度O(mlogn), n表示点数, m表示边数

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    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] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

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

Bellman-ford算法

时间复杂度O(nm), n表示点数, m表示边数

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge{     // 边，a表示出点，b表示入点，w表示边的权重
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < m; j ++ ){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

求边数限制的最短路算法 通过k次松弛，所求得的最短路，就是边数限制的最短路

const int N = 510, M = 10010;
struct Edge{
    int a, b, c;
}edges[M];
int n, m, k;
int dist[N];
int last[N];

void bellman_ford(){
    memset(dist, 0x3f, sizeof dist);	// 初始化
    dist[1] = 0;
    
    for (int i = 0; i < k; i ++ ){
        // 为了防止发生串联 如: 1→2→3,在一次循环里1更新2,2有就可能更新3,这是不允许的，所以保存初始dist数组
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j ++ ){
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[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();
    
	//不可dist[n]==0x3f3f3f3f 因为有可能出现1到不了2,2到3为负数,所以大于无穷的一半就可以判定无法到达
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);
    return 0;
}

spfa 算法

队列优化的Bellman-Ford算法: 时间复杂度平均情况下O(m)，最坏情况下O(nm), n表示点数, m表示边数

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;	// st 数组记录哪些点在队列里

    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]){                    // 如果队列中已存在j，则不需要将j重复插入
                    q.push(j);    	        // 只要是符合条件就进队列
                    st[j] = true;
                }
            }
        }
    }

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

spfa 求负环

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa(){
    // 不需要初始化dist数组,因为不用求具体数值,只需要矢量的比较就行
    // 原理:如果某条最短路径上有n个点(除了自己),那么加上自己之后一共有n+1个点,由抽屉原理一定有两个点相同,所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ ){	// 求整个图中的负环
        q.push(i);
        st[i] = 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];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点(不包括自己),则说明存在环
                if (!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

Floyd算法

// 初始化:
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd(){
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

// 输出结果
	if(g[a][b] > INF/2)puts("impossible");
	else printf("%d\n",g[a][b]);

朴素版Prim算法

时间复杂度是O(n²+m), n表示点数，m表示边数

用堆优化版prim，和用堆优化版Dijkstra差不多

int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
    memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
    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 (dist[t] == INF) return INF;

        res += dist[t];
        st[t] = true;
		// 放在下面，是因为数据中有自环，容易造成误算
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);	// 把t所连且距离更短的放入集合
    }
    return res;
}

堆优化版Prim

不用刻意优化

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
bool st[N];
int prim(){
    int res = 0, cnt = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0,1});
    while (heap.size()){
        auto t = heap.top();
        heap.pop();
        if(st[t.second]) continue;
        st[t.second] = true;
        res += t.first;
        cnt ++;
        for (int i = 1; i <= n; i ++){
            if (!st[i] && g[t.second][i] != INF){
                heap.push({g[t.second][i], i});
            }
        }
        
    }
    if(cnt != n)return INF;
    return res;
}

Kruskal算法

int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge{     // 存储边
    int a, b, w;
    bool operator< (const Edge &W)const{
        return w < W.w;
    }
}edges[M];

int find(int x){     // 并查集核心操作
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal(){
    sort(edges, edges + m);
    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;
}

二分图-染色判定法

• 二分图定义: 图中不存在奇数环；或图可被分为两部分，两部分内部不存在边，只在中间存在边。
• 时间复杂度是O(n ＋ m), n表示点数，m表示边数

int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，0表示未染色，1表示白色，2表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
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] && !dfs(j, 3 - c)) return false;
		else if (color[u] == color[j]) return false;
	}
	return true;
}

bool check(){
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i] && !dfs(i, 0)){
                flag = false;
                break;
        }
    return flag;
}

二分图-匈牙利算法

• 匈牙利算法为了解决二分图两部分的节点的最大匹配数。
• 匈牙利算法: 二分图的两部分，一方男同志，一方女同志，两方匹配，一方按顺序匹配，有心仪的女生(即有边)，即匹配成功，到某个男生匹配时，发现心仪的女生已经匹配了，那么这个男生就要女生问问她的配偶是否有备胎，递归去问备胎是否单身....。若备胎也没匹配，那么她男朋友和他备胎在一起，直到所有有联系的人都问完。---给人找到下家，才去挖墙脚。(做错不重要，重要的是错过)
• 时间复杂度是O(nm), n表示点数，m表示边数

int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
bool st[N];			// 男生匹配每个女生只尝试一次
int match[N];		// 该女生匹配了哪个男生

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 res = 0;
for (int i = 1; i <= n1; i ++ ){
    memset(st, false, sizeof st);	// 每个都尝试
    if (find(i)) res ++ ;
}

数学知识-模板

试除法判定质数

时间复杂度大O(sqrt(n))

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

试除法分解质因数

时间复杂度O(log(n) - sqrt(n))

void divide(int x){
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0){	// i 一定是质数,因为合数在前面已经除完了
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;// 一个数最多有一个大于sqrt(n)的质因子,因为若是有两个那么乘积就大于n了
    cout << endl;
}

朴素筛法求素数

时间复杂度O(nlog(log(n)))近似O(n)

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)	// 只需要以素数筛就可以，因为前面的素数会将后面的合数筛掉
            st[j] = true;
    }
}

线性筛法求素数

原理: n只会被它的最小质因子筛掉 时间复杂度 O(n)

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]) primes[cnt ++ ] = i;
        // 用已经筛出的素数去筛,保证了每次都是最小质因子筛掉合数
        /* 
        	primes[j]<=n/i是合理的, 因为j永远小于i, 即primes已存的素数都是小于i的
            1、当 i 是合数, 那么一定在下面的break出去, 因为一定有最小质因子。
            2、当 i 是质数, 如果不从primes[j] <= n / i退出，那一定在下面break退出(因为总会j++到primes[j] == i时)
        */
        for (int j = 0; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = true;	//在下面注释
            if (i % primes[j] == 0) break;	// 只能被自己最小质因子筛掉
        }
    }
}

注释:

1. 若i % primes[j] == 0 那么primes[j] 一定是 i 的最小质因子,此时i可以直接被筛掉,且primes[j] * i 的最小质因子也是primes[j]。
2. 若i % primes[j] != 0 说明前面筛出的素数都不是i最小质因子，但primes[j] * i 的最小质因子也是 primes[j]。
3. 总之，primes[j] * i 的最小质因子始终是 primes[j] 对应代码 st[primes[j] * i] = true;

试除法求所有约数

时间复杂度为O(logn)

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

约数个数和约数之和

如果 N = p1^c1 * p2^c2 * ... *pk^ck		// p为质因子
约数个数:(c1 + 1) * (c2 + 1) * ... * (ck + 1)	// 组合数
// 按照组合数选数, 展开的每一项就是约数, 总和就是约数之和
约数之和:(p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

const int N = 110;
const int 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){
                primes[i] ++;
                x /= i;
            }
        }
        if (x > 1) primes[x] ++;
    }
    LL res = 1;
    // 约数个数
    for (auto prime:primes)res = res * (prime.second + 1) % mod;
    
    cout << res << endl;
    res = 1;
    // 约数之和
    for (auto prime:primes){
        int p = prime.first,k = prime.second;
        LL t = 1;
        while (k --) t = (t * p + 1) % mod;  // 这里要取模所以用等比数列前n项和不合适
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

欧几里得算法

假设d为任意两个数的最大公约数

1. 定理: 若d|a 和 d|b, 即d|ax + by |: 整除的意思 ↔ d|a a整除b 裴蜀定理: 对于任意正整数a, b, 一定存在非零整数x, y, 使得ax + by = (a, b) 即a, b组合的最小的正整数为a和b的最大公约数。
2. 推理: a mod b = a - a / b * b = a - c * b 令c = a / b
3. 论证: (b, a % b) == (b, a - c * b) 由(1)得 d|(a - c * b) 和 d|b 得d|(a- c * b + c * b)，即d|a，
   所以(b, a % b) == (a, b) (a,b)即a和b最大公约数
4. 结论: (a, b) == (a, a % b)

int gcd(int a, int b){	// (a,b) == (a, a % b) 递归下去, 即求最大公约数 递归结束条件 b == 0
    return b ? gcd(b, a % b) : a;// b不等于0, 返回gcd(b, a % b), 否者返回a, 因为a和0的最大公约数为a
}

欧拉函数

1. 极性函数证明
   

2. 容斥原理证明

代码如下

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

    return res;
}

筛法求欧拉筛

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n){
    euler[1] = 1;	// 定义的
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]){
            primes[cnt ++ ] = i;
            euler[i] = i - 1;	// 质数的欧拉值为 i - 1
        }
        for (int j = 0; primes[j] <= n / i; j ++ ){
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0){	// primes[j] 是 i的最小质因子
                /*
                	phi[i] = i*(1-1/p1)*(1-1/p2)*...*(1-1/pk),且primes[j]是i的质因子,
                	所以phi[t] = primes[j]*i*(1-1/p1)*(1-1/p2)*...*(1-1/pk) = primes[j]*phi[i]
                */
                euler[t] = euler[i] * primes[j];
                break;
            }
            /*
            	解释一:
            		i 不能整除 primes[j], 那么 i 就和 primes[j] 互质, 根据积性函数得 φ(t) = φ(i) * φ(primes[j])
            	解释二:
            		i 不能整除 primes[j], 但是primes[j]仍是t的最小质因子, 因此不仅需要将基数N修正为primes[j]倍, 还需要				补上1 - 1 / primes[j]这一项, 因此最终结果phi[i] * (primes[j] - 1)
            */
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

快速幂

求 m^k mod p，时间复杂度 O(log(k))

原理: 预处理m的1,2,4,8,16....次方，进行k的二进制规律进行组合相乘

int qmi(int m, int k, int p){
    int res = 1 % p, t = m;
    while (k){ // k次, k转成二进制
        if (k&1) res = res * t % p;	// 每次看末位是否为1,为1则进行累乘
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

快速幂求逆元(p质数)

≡ : 同余

a / b ≡ a * x (mod p)
两边同乘b可得 a ≡ a * b * x (mod p)
即 1 ≡ b * x (mod p)
同 b * x ≡ 1 (mod p)
由费马小定理可知，当p为质数时
b^(p-1) ≡ 1 (mod p)
拆一个b出来可得 b * b^(p-2) ≡ 1 (mod p)
故当n为质数时，b的乘法逆元 x = b^(p-2)

LL qmi(int m, int k, int p){
    LL res = 1 % p, t = m;
    while (k){
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");	// 质数只和自己的倍数不互质
        else printf("%lld\n", qmi(a, p - 2, p));
    }
    return 0;
}

扩展欧几里得算法

证明1:

写法一

int exgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回)
    if(b==0){
        x = 1, y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = exgcd(b, a%b, x1, y1);
    x = y1, y = x1 - a/b*y1;	// 递归回溯回时记录答案
    return gcd; 
}

写法二

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y){
    if (!b){
        x = 1; y = 0;	// 当 b = 0时, a和b的最大公约数为 a, 系数为 x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;	// y = y' - a/b * x'  y'和x'都是回溯上层的结果
    return d;
}

线性同余方程

求同余方程ax ≡ b(mod m)的系数 x

推理: ax ≡ b(mod m)↔(ax % m = b % m)，知存在y_k使得 ax = my_k + b，得ax - my_k = b，令 y = -y_k，即 ax + my = b。ax + my = b有解的必要条件是gcd(a, m)|b。设求出ax₀ + my₀ = gcd(a,m) ，即得 x = b / gcd(a,m) * x₀ = b * x₀ / gcd(a, m)

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");	        // 说明b不能整除gcd(a, m)
    else printf("%d\n", (LL)b * x / d % m);	// 题目要求在int范围内,且(a*x)%m = (a*(x%m))%m, 所以最后需要%m
}

扩展欧几里得求逆元(p非质数)

求ax ≡ 1 (mod p)的x,根据线性同余方程等价求ax + py = 1的x

while (n--) {
    cin >> a >> p;
    if (exgcd(a, p, x, y) == 1) cout << (x + p) % p << endl;
    else  cout << "impossible" << endl;//如果 exgcd(a,p,x,y) != 1, 说明ax+py=1无解, 因为1只能整除1
}

高斯消元

// a[N][N]是增广矩阵
int gauss(){
    int c, r;
    for (c = 0, r = 0; c < n; c ++ ){
        int t = r;
        for (int i = r; i < n; i ++ )//找到绝对值最大的行,寻找最大的数值是因为可以避免系数变得太大,精度较高.
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端 r
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];     // 将当前行的首位变成 1
        for (int i = r + 1; i < n; i ++ )                      // 用当前行将下面所有的列消成 0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n){
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)  // 最后一列有非零则无解
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] & a[j][n];	// 回解每个未知数

    return 0; // 有唯一解
}

递推法求组合数

\(C_{m}^{n}\) = \(C_{m-1}^{n}\) + \(C_{m-1}^{n-1}\) : m个数选n个，可分为两种情况，某数x，① 确定选 x 再在m-1个中选n-1个，即\(C_{m-1}^{n-1}\)② 确定不选 x 再在m-1个中选n个\(C_{m-1}^{n}\)

数据范围: 10000次询问，1 <= b <= a <= 2000

// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;	// c[i][0] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

预处理逆元的方式求组合数

首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元

数据范围: 10000次询问，1 <= b <= a <= 10⁵

int qmi(int a, int k, int p){    // 快速幂模板
    int res = 1;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ ){
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

Lucas定理求组合数

若p是质数，则对于任意整数 1 <= m <= n，有: \(C_{m}^{n}\) = \(C_{m\%p}^{n\%p}\) * \(C_{m/p}^{n/p}\) (mod p)

数据范围: 20次询问，1 <= b <= a <= 10¹⁸，1 <= p <= 10⁵

int qmi(int a, int k, int p){  // 快速幂模板
    int res = 1 % p;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int C(int a, int b, int p){  // 通过定理求组合数C(a, b)
    if (a < b) return 0;

    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ ){
        x = (LL)x * i % p;
        y = (LL) y * j % p;
    }
    
    return x * (LL)qmi(y, p - 2, p) % p;
}
int lucas(LL a, LL b, int p){
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

分解质因数法求组合数

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：

1. 筛法求出范围内的所有质数

2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 \(\lfloor {n \over p} \rfloor\) + \(\lfloor {n \over p^{2}} \rfloor\) + \(\lfloor {n \over p^{3}} \rfloor\) + ... \(\lfloor {n \over p^{k}(p^{k}\leqslant n)} \rfloor\)

   n*(n-1)*(n-2)*...2*1 中 p 的次数: p为质因子

   • \({n \over p}\) 代表 1 - n 中 p倍数的数字个数 1p,2p,3p,...xp \({\leqslant}\) n 这个x=\({n \over p}\)
   • \({n \over p^{2}}\) 代表1 - n/p 中 p倍数的数字个数1p,2p,...mp\({\leqslant}\) n/p 其中m=\({n \over p^{2}}\)
   • .....
   • \({n \over p^{k}}\) 代表1 - n/p^k-1 中 p倍数的数字个数1p,2p,3p,....,kp\({\leqslant}\) n/p^k-1 其中k=\({n \over p^{k}}\) (循环结束条件: p^k+1 > n)
   • 所以 n! 中p的次数是 \(\lfloor {n \over p} \rfloor\) + \(\lfloor {n \over p^{2}} \rfloor\) + \(\lfloor {n \over p^{3}} \rfloor\) + ... \(\lfloor {n \over p^{k}(p^{k}\leqslant n)} \rfloor\)

3. 用高精度乘法将所有质因子相乘

// 线性筛求素数
int primes[N], cnt;
int sum[N];
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; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

// 求n!中的次数(核心代码)
int get(int n, int p){
    int res = 0;
    while (n){
        res += n / p;	        // 累计一次p的数量
        n /= p;			// 增加一次方
    }
    return res;
}

// 高精度乘低精度模板
vector<int> mul(vector<int> a, int b){
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ ){
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t){
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

/*************************************************************************/
get_primes(a);  // 预处理范围内的所有质数
for (int i = 0; i < cnt; i ++ ){// 求每个质因数的次数
    int p = primes[i];
    sum[i] = get(a, p) - get(b, p) - get(a - b, p);	// 分子的p次数 减去 分母p的次数
}

// 剩余的质因子相乘(高精度乘低精度)
vector<int> res;
res.push_back(1);
for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

卡特兰数(组合数)

给定n个0和n个1,它们按照某种顺序排成长度为2n的序列,满足任意前缀中0的个数都不少于1的个数的序列的数量为:Cat(n) = \(C_{2n}^{n} \over n + 1\)

将01序列置于坐标系中，起点定于原点。若0表示向右走，1表示向上走，那么任何前缀中0的个数不少于1的个数就转化为，路径上的任意一点，横坐标大于等于纵坐标。题目所求即为这样的合法路径数量。
下图中，表示从(0,0)走到(n, n)的路径，在绿线及以下表示合法，若触碰红线即不合法。

由图可知，任何一条不合法的路径(如黑色路径)，都对应一条从(0,0)走到(n - 1,n ＋ 1)的一条路径(如灰色路径)。而任何一条(0,0)走到(n - 1,n＋1)的路径，也对应了一条从(0,0)走到(n,n)的不合法路径。

结论: 所有(0,0)到(n,n)且不经过红线的路线即为答案，所有经历红线并到达(n,n)的路线数 等价于 所有从(0,0)到(n-1,n+1)路线数，因为(0,0)到(n-1,n+1)一定经历红线。

证明: \(C_{2n}^{n}\) - \(C_{2n}^{n-1}\) = \(C_{2n}^{n} \over n + 1\)
\(C_{2n}^{n}\) - \(C_{2n}^{n-1}\) = \((2n)! \over n! n!\) - \((2n)! \over (n-1)!(n+1)!\) = \((2n)!(n+1) - (2n)!n\over (n+1)!n!\) = \((2n)! \over (n+1)!n!\) = \(1 \over n+1\)\((2n)!\over n!n!\) = \(C_{2n}^{n} \over n + 1\)

int a = n * 2, b = n;
int res = 1;
// 2n!/(n+1)!n! = 2n*(2n-1)*...*(2n-n+1)/(n+1)!
for (int i = a; i > a - b; i -- ) res = (LL)res * i % mod;	// 2n*(2n-1)*...*(2n-n+1)

for (int i = 1; i <= b + 1; i ++ ) res = (LL)res * qmi(i, mod - 2, mod) % mod;	// res*((n+1)!的逆元)

cout << res << endl;

容斥原理

应用: 能被整除的数

给定一个整数n和m个不同的质数p₁,p₂,... ,p_m，请你求出1～n中能被p₁,p₂,...,p_m中的至少一个数整除的整数有多少个。

解题思路:

实现思路:

// 二进制枚举
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 20;
int p[N], n, m;

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

    int res = 0;
    //枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
    for(int i = 1; i < 1 << m; i ++) {
        int t = 1;             //选中集合对应质数的乘积
        int s = 0;             //选中的集合数量

        //枚举当前状态的每一位
        for(int j = 0; j < m; j ++){
            //选中一个集合
            if(i >> j & 1){
                if((LL)t * p[j] > n){    
                    t = -1;
                    break;//乘积大于n, 则n / t = 0, 跳出这轮循环
                }
                s++;            //有一个1, 集合数量+1
                t *= p[j];
            }
        }

        if(t == -1) continue;  

        if(s & 1) res += n / t; //选中奇数个集合, 则系数应该是1, n/t为当前这种状态的集合数量
        else res -= n / t;      //反之则为 -1
    }

    cout << res << endl;
    return 0;
}

博弈论-NIM游戏

经典NIM游戏

for(int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    res ^= x;
}
if(res) puts("Yes");
else puts("No");

NIM游戏拓展

题目描述: 现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 a 个石子(i ≥ 1)。两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中(不能不拿)。已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。

最优策略:

1. 把所有奇数台阶看做经典NIM游戏，若是所有奇数台阶异或和为0，则必败，否者先手将奇数台阶拿走若干石子到下一台阶(偶数台阶)，把所有奇数台阶的异或和恢复为 0 。
2. 将经典NIM游戏中的拿走某堆中若干，看做两种情况，① 拿奇数台阶到下一台阶(偶数台阶)，就相当于NIM游戏中拿走某堆中若干 ② 拿偶数台阶到下一台阶(奇数台阶)，那后手就将拿过去的都拿到下一台阶(偶数)，那么奇数台阶又恢复异或为0的状态。
3. 为什么不用偶数台阶计算？因为最后都落到0号台阶且不能再移动，0号台阶是偶数台阶。

int f = 0;
for (int i = 1,x; i <= n; i++){
    cin >> x;
    if(i%2)f^=x;
}
if (f)puts("Yes");
else puts("No");

博弈论-SG函数

例子: 若干堆石子，每一次只能拿2, 5个，其他规则和NIM游戏相同

SG函数过程:

结合代码重点理解Mex运算，以及SG函数如何利用Mex运算

应用一: 集合-Nim游戏

给定n堆石子以及一个由k个不同正整数构成的数字集合S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

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

using namespace std;

const int N=110,M=10010;
int n,m;
int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值

int sg(int x){
    if(f[x] != -1) return f[x];// 如果此sg值出现过就不再重复计算
    unordered_set<int> S; // set代表的是有序集合,记录所有子节点的sg值
    for(int i = 0;i < m;i ++){
        int sum = s[i];
        if(x >= sum) S.insert(sg(x - sum));// 当x大于sum是才可以"拿"递归下去
    }

    /*************************************重点Mex运算***************************************
    	循环完之后可以进行选出最小的没有出现的自然数的操作,这里就保证了sg值可以像Nim游戏一样,
    	Nim游戏中可以拿任意数量,sg(x)节点可以走到小于它的任何节点,这是一个有向图
    ***************************************************************************************/
    for(int i=0;;i++)
        if(!S.count(i)) return f[x] = i;
}

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

    cin >> n;
    memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过

    int res = 0;
    for (int i = 0;i < n; i++){
        int x;
        cin >> x;
        res ^= sg(x);//观察异或值的变化,基本原理与Nim游戏相同
    }

    if(res) printf("Yes");
    else printf("No");

    return 0;
}

应用二: 拆分-Nim游戏

题目描述:

给定n堆石子，两位玩家轮流操作，每次操作可以拿走其中的一堆石子，然后重新放置两堆规模更小的石子(新堆规模可以为0，且两个新堆的石子总数可以大于取走的那堆石子数)，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

加黑解释: 新的两堆，不是以原来的石子分的，是重新放的两堆石子，只是要求这两堆每一堆都小于原来那堆的数量。

题目分析:

相比于集合-Nim，这里的每一堆可以变成小于原来那堆的任意大小的两堆，即a_i可以拆分成(b_i, b_j)，为了避免重复规定b_i >= b_j，
相当于一个局面拆分成了两个局面，由SG函数理论，多个独立局面的SG值，等于这些局面SG值的异或和。因此需要存储的状态就是sg(b_i)^sg(b_j) (与集合-Nim的唯一区别)

int f[N];
unordered_set<int> S;
/*****************************为什么可以把 S 定义成全局变量********************************
	因为这个sg函数的特殊性, 求sg(100)时, 它会将1-100的所有sg(1)-sg(100)都计算出来,
	当 x <= 100 的都会直接return f[x]; 当x > 100 的会因为sg是递归性质, 因此会按顺序求出sg(101),
	sg(102),...,sg(x), 所以把S设置成全局变量更好.
**************************************************************************************/

int sg(int x){
    if(f[x] != -1) return f[x];

    for(int i = 0 ; i < x ; i++)
        for(int j = 0 ; j <= i ; j++)//规定j不大于i，避免重复
            //相当于一个局面拆分成了两个局面,由SG函数理论,多个独立局面的SG值,等于这些局面SG值的异或和
            S.insert(sg(i) ^ sg(j));
    for(int i = 0 ; ; i++)
        if(!S.count(i))
            return f[x] = i;
}

动态规划-模型

背包问题

01背包

每件物品只能选一次，在不超过体积 j 的前提下可以选择的最大价值

朴素版

int v[N],w[M];
int f[N][N];	// 在1-i中选出体积不超过j的最大价值
    
for (int i = 1; i <= n; i ++){
    for (int j = 0; j <= m; j ++){
        f[i][j] = f[i - 1][j];		// 不选第i个物品: 只从1-i-1中选, 且体积不超过j
        if (j > v[i]) f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]); // 选第i个物品: f[i - 1][j - v[i]] + w[i]
    }
}
cout << f[n][m] << endl;

优化版

int v[N],w[M];
int f[N];
for (int i = 1; i <= n; i ++){
    for (int j = m; j >= v[i]; j --)	// 倒着循环保证f[j-v[i]]是上一轮的数据没有被覆盖
        /*
        	1. 本轮没选第i个物品 f[i - 1][j] == f[j]
        	2. 本轮选第i个物品 f[i - 1][j - v[i]] + w[i] == f[j - v[i]] + w[i]
        	3. 两者取max
        */
        f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m] << endl;

完全背包

每件物品可以被选无数个，在不超过体积 j 的前提下可以选择的最大价值

朴素版

int v[N],w[M];
int f[N][N];	// 在1-i中选出体积不超过j的最大价值
for (int i = 1; i <= n; i ++)
    for (int j = 0; j <= m; j ++)
        for (int k = 0; k * v[i] <= j; k ++)
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
cout << f[n][m] << endl;

优化版1

int v[N],w[M];
int f[N][N];	// 在1-i中选出体积不超过j的最大价值
for (int i = 1; i <= n; i ++)
    for (int j = 0; j <= m; j ++){
        /*
        	f[i][j] = max{f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,f[i-1][j-3*v]+3*w,...}
        	f[i][j-v] = max{        f[i-1][j-v]  ,f[i-1][j-2*v]+  w,f[i-1][j-3*v]+2*w,...}
        	所以 f[i][j] = max{f[i-1][j],f[i][j-v]+w}
        */
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    }
cout << f[n][m] << endl;

优化版2

int v[N],w[M];
int [N];	// 在1-i中选出体积不超过j的最大价值
for (int i = 1; i <= n; i ++)
    for (int j = v[i]; j <= m; j ++){	// 和01背包唯一的区别就是循环的顺序
        /*
        	1. f[i][j] = f[i - 1][j]; == f[j] = f[j]
        	2. f[i][j] = max(f[j], f[i][j - v[i]] + w[i]); == f[j] = max(f[j], f[j - v[i]] + w[i])
        	3. 循环不用倒着是因为f[i][j - v[i]]就是需要本层已经更新过的, 因此不用担心覆盖问题
        */
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
cout << f[m] << endl;

多重背包

每件物品可以被选x_i个，在不超过体积 j 的前提下可以选择的最大价值

朴素版 时间复杂度O(n*m*s)

int v[N], w[N], s[N];
int f[N][N];
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]] + k * w[i]);
cout << f[m] << endl;

为什么不用完全背包优化的方法优化多重背包?

优化版 时间复杂度O(n*m*log(s)) 利用二进制将多重背包优化成01背包
例子: x = 200 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 73，且200以内所有的数都可以用这些数组和表示

// N = 1000*log(2,2000)
int n,m,cnt;
int v[N],w[N];
int f[N];
for (int i = 0; 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 *= 2;
    }
    if (s > 0){
        v[++ cnt] = a * s;
        v[cnt] = b * s;
    }
}
for (int i = 1; i <= cnt; i ++)
    for (int j = m; j >= v[i]; j --)
        f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;

分组背包

每组有多种物品，每种物品只有一个，每组只能选一个，，在不超过体积 j 的前提下可以选择的最大价值

多重背包是每组选几个，而分组背包是每组选哪个。

f[i][j] = max{f[i - 1][j], f[i - 1][j - k_i] + w[i][k_i]} 类似01背包

int n,m;
int v[N][N],w[N][N];
int f[N],s[N];
for (int i = 1; i <= n; i ++)
    for (int j = m; j > 0; j --)
        for (int k = 1; 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;

PS: 第三重循环和第二重循环是不可以换位子的，因为第二重循环是从m开始的，为了避免覆盖上层，而不能使用上层。如果换位置，f[j] 就会循环s[i]次导致上层数据被覆盖。但是如果是没有进行一维优化的话，用二维i，j，k就可以交换位置了，那样就不会覆盖上层数据。

线性DP

数字三角形

for (int i = n - 1; i >= 1; i --)
    for (int j = 1; j <= i; j ++)
        a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
cout << a[1][1] << endl;

最长上升子序列

数据范围 1 <= N <= 1000

int n,a[1010],f[1010],g[1010];	// g[i] 记录 f[i] 是从哪个状态转移过来的, 最后可以倒着推出序列是什么
for(int i = 1; i <= n; i ++){
    f[i] = 1; 
    g[i] = 0;	// 以i为起点的最长子序列
    for(int j = 1; j < i; j ++)
        if(a[j] < a[i] && f[i] < f[j] + 1){
            f[i] = f[j] + 1;		// 若是a[j] < a[i] 那么以i结尾的最长子序列长度 = f[j] + 1
            g[i] = j;
        }
}
int ans = 0;
for(int i = 1; i <= n; i ++) ans = max(ans, f[i]);
cout << ans << endl;

数据范围 1 <= N <= 100000

/************************** DP ----> 贪心 **************************
	q数组下标: 代表最长子序列长度
	q数组的值: 记录下标len的子序列最后一个数的最小值
	因为q数组的定义可知,所以q[len]一定小于q[len+1]，因此数组q具有单调递增性质,
	可以利用二分找到第一个大于a[i]的值, q[i + 1] = a[i]
*******************************************************************/
int n,a[N],q[N];
int len = 0;
for (int i = 0; i < n; i ++ ){
    int l = 0, r = len;
    while (l < r){
        int mid = l + r + 1 >> 1;
        if (q[mid] < a[i]) l = mid;
        else r = mid - 1;
    }
    len = max(len, r + 1);
    q[r + 1] = a[i];
}
printf("%d\n", len);

最长公共子序列

闫式DP分析

• 状态表示f[i, j]
  ① 集合: 所有在第一个序列的前i个字母出现，且在第二个序列的前j个字母出现的子序列
  ② 属性: Max
• 状态计算: f[i, j] 分为4种状态 00(i不选, j不选)，01(i不选, j选)，10(i选, j不选)，11(i选, j选)
  00: 这个状态好表示 f[i, j] = f[i - 1, j - 1]
  01: 这个状态表示为 f[i, j] = f[i - 1, j]
  10: 这个状态通过为 f[i, j] = f[i, j - 1]
  11: 这个状态好表示 f[i, j] = f[i - 1, j - 1] + 1
• 通过对f[i, j]的定义，可以发现f[i - 1, j - 1] 这种状态属于 f[i - 1, j] 和 f[i, j - 1] 这两种状态中。

int n, m;
char a[N], b[N];
int f[N][N];
scanf("%s%s", a + 1, b + 1);
for (int i = 1; i <= n; i ++)	// 双重循环--二维dp
    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;
/*
acbd
abedc
*/

最短编辑距离

题意: 两个字符串a, b，有三种操作: 增，删，改。问最少的操作次数使得字符串a变成b

• 状态表示 f[i, j]
  1. 集合: 所有将a[1~i]变成b[1~j]的操作方式
  2. 属性: Min
• 状态计算
  1. 删除: f[i - 1, j] + 1 要保证a[0，i - 1] 和 b[0，j] 相等的条件下
  2. 增加: f[i, j - 1] + 1 要保证a[0，i] 和 b[0，j - 1] 相等的条件下
  3. 修改: f[i - 1, j - 1] + 1_不同or 0_相同 要保证 a[0，i - 1] 和 b[0，j - 1] 相等的条件下

int f[N][N];
char a[N],b[N];
scanf("%s%s", a + 1, b + 1);
// 初始化
for(int i = 0; i <= m; i ++)f[0][i] = i;	// a[0,0] 到 b[0,i] 需要添加操作i次
for(int i = 0; i <= n; i ++)f[i][0] = i;	// a[0,i] 到 b[0,0] 需要删除操作i次

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; // a[i] == b[i] 修改 +1
        else f[i][j] = f[i - 1][j - 1];	// 修改
        f[i][j] = min(f[i][j], min(f[i - 1][j] + 1,f[i][j - 1] + 1));	// 比较三种情况选出最小值
    }
}
cout << f[n][m] << endl;

区间DP-石子合并

• 题意: 合并 N 堆石子，每次只能合并相邻的两堆石子，求最小代价

• 解题思路:

  关键点: 最后一次合并一定是左边连续区间和右边连续区间进行合并

  1. 状态表示: f[i][j] 表示将 i 到 j 这一区间的石子合并成一个区间的集合，属性时Min

  2. 状态计算:

     f[i][j] = min{f[i][k_i] + f[k_i + 1][j] + s[j] - s[i - 1]} (i ≤ k_i ≤ j - 1) 至少 k_i 把[i, j]分成两个区间

int s[N];
int f[N][N];
for (int i = 1; i <= n; 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 ++ )	//k ∈ [l, r - 1]
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
    }
printf("%d\n", f[1][n]);

记忆化搜索做法

int dp(int i, int j) {
    if (i == j) return 0; // 判断边界
    int &v = f[i][j];

    if (v != -1) return v;// 减枝避免重复计算,因为下面循环会出现区间重叠

    v = 1e8;
    for (int k = i; k < j; k ++)
        v = min(v, dp(i, k) + dp(k + 1, j) + s[j] - s[i - 1]);

    return v;
}
memset(f, -1, sizeof f);
cout << dp(1, n) << endl;

区间DP常用模板

for (int len = 1; len <= n; len ++) {         // 区间长度
    for (int i = 1; i + len - 1 <= n; i ++) { // 枚举起点
        int j = i + len - 1;                 // 区间终点
        if (len == 1) {
            dp[i][j] = 初始值
            continue;
        }

        for (int k = i; k < j; k ++) {        // 枚举分割点，构造状态转移方程
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }
}

计数类DP-整数划分

问题描述: 一个正整数n可以表示成若干个正整数之和，形如：n = n₁ + n₂ + … + n_k，其中 n₁ ≥ n₂ ≥ … ≥ n_k, k≥1，我们将这样的一种表示称为正整数 n 的一种划分，现在给定一个正整数n，请你求出n共有多少种不同的划分方法

方法一

/***************************利用完全背包的推理***********************
f[i][j]: 表示前i个整数(1,2…,i)恰好拼成j的方案数
f[i][j] = f[i-1][j]+f[i-1][j-i]+f[i-1][j-i*2]...f[i-1][j-i*s]	i*s <= j < i*(s+1)
f[i][j-i] = 		f[i-1][j-i]+f[i-1][j-i*2]...f[i-1][j-i*s]
得出转移方程 f[i][j] = f[i-1][j]+f[i][j-i]
优化维度	f[j] = f[j]+f[j-i]
******************************************************************/
int f[N];
f[0] = 1;  //总和为0的方案数,也就是f[i][0]前i个整数(1,2…,i)恰好拼成0的方案数,只有一种就是一个都不选
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;

方法二

/*********************计数DP****************************
f[i][j]表示和为i,恰好选j个数的方案数
划分为两种情况
1.最小值为1 那把为1的情况去掉 就是f[i-1][j-1]这种情况的方案数
2.最小值大于1 那把i个数都减去1 就是f[i-j][j] 这个情况的方案数
转移方程: f[i][j] = f[i-1][j-1] + f[i-j][j]
		ans = f[n][1] + f[n][2] + ... + f[n][n]
*******************************************************/
int f[N][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;

数位统计DP-计数问题

题目描述:

给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0～9的出现次数。
例如，a=1024，b = 1032，则a和b之间共有9个数如下:
1024 1025 1026 1027 1028 1029 1030 1031 1032
其中0出现10次，1出现10次，2出现7次，3出现3次等等...

算法思想: 前缀和，数位dp

例如 n = abcdefg 求 0 ~ n 中x出现的次数，记作count(n, x)，核心思想是计算x在abcdefg上每一位出现的次数之和

计算x在数字'd'这个位置出现的次数

1. ① 'abc'位置是[000, abc - 1] 此时ans += abc*10^3

   ② 当x = 0时要特判，因为多算了000x这种情况，所以ans -= 10^3

2. 'abc'位置是abc时

   • ③ d < x 时，那么abcxefg就大于abcdefg，此时不符合条件不计入ans
   • ④ d = x 时，那么efg就是所求x在数字d所在位置的次数 ans += efg+1 (000 ~ efg)
   • ⑤ d > x 时，那么efg所在的位置可以填任何数字, ans += 1000 (000 ~ 999)

最后将x在n的每一位上计算的次数相加，就是0~n中x出现的次数

所以求 a~b之间的x出现的次数,利用前缀和原理,即等于求0~b出现x的次数减去0~a-1出现x的次数: ans = count(b, x) - count(a - 1, x)

int get(vector<int> num, int l, int r){	// 计算num[l],num[l+1],...,num[r]十进制数
    int res = 0;
    for (int i = l; i >= r; i --) res = res * 10 + num[i];
    return res;
}
int power10(int x){						// 计算10^x
    int res = 1;
    while (x -- ) res *= 10;
    return res;
}
int count(int n, int x){				// 计算0~n中x出现的次数
    if (!n) return 0;
    vector<int> num;					// 把n的每一位拆分放进num数组中
    while (n){
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();
    int res = 0;	
    for (int i = n - 1 - !x; i >= 0; i --){
        if (i < n - 1){	// 计算i的前缀是0 ~ (abc-1)
            res += get(num, n - 1, i + 1) * power10(i);	//① 0~(abc-1)数量等于abc   res+="前缀数量"*power10(i)
            if (!x) res -= power10(i);			//② 如果x是0, 那么就会多数一种情况000xefg, 即多加一个 power10(i)
        }
        if (num[i] == x) res += get(num, i - 1, 0) + 1;	//④ 前缀是abc且d = x
        else if (num[i] > x) res += power10(i);			//⑤ 前缀是abc且d > x
    }
    return res;
}
int main(){
    int a, b;
    while (cin >> a >> b , a){
        if (a > b) swap(a, b);
        for (int i = 0; i <= 9; i ++)
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }
    return 0;
}

状态压缩DP

蒙德里安的猜想-DP

题意: n x m的棋盘可以摆放不同的1 × 2小方格的种类数。

题目分析:

• 摆放方块的时候，先放横着的，再放竖着的。总方案数等于只放横着的小方块的合法方案数。
• 如何判断，当前方案数是否合法? 所有剩余位置能否填充满竖着的小方块。可以按列来看，每一列内部所有连续的空着的小方块需要是偶数个。
• 这是一道动态规划的题目，并且是一道状态压缩的dp: 用一个N位的二进制数，每一位表示一个物品，0/1表示不同的状态。因此可以用0 →2^N -1中的所有数来枚举列全部的状态。

状态表示: f[i][j]表示已经将前i-1列摆好，且从第i-1列，伸出到第i列的状态是j的所有方案。其中j是一个二进制数，用来表示第i-1列转化成第i列的状态(j对应二进制中的1表示从i-1列横着放一个方块，0表示从i-1类到i列没变化)，其位数和棋盘的行数一致。

状态转移: f[i][j] += f[i - 1][k_i] (0 ≤ k_i ≤ 2ⁿ-1) 表示第i列的状态j的方案数等于所有符合条件的第i-1列的状态k_i之和。其中状态k_i 表示第i-2列转化到第i-1列的状态，状态j表示第i-1列转化到第i列的状态

typedef long long LL;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];// 第一维表示列, 第二维表示所有可能的状态
vector<int> state[M];
bool st[M];//存储每种状态是否有奇数个连续的0, 如果奇数个0是无效状态, 如果是偶数个零置为true

int main(){
    while (cin >> n >> m, n || m){
        // 预处理(一): 预处理出[0,1<<n]中每个数的n位中连续0的数量是否为偶数	1 表示伸出  0 表示不伸出
        for (int i = 0; i < 1 << n; i ++ ){
            int cnt = 0;
            bool is_valid = true;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1){
                    if (cnt & 1){
                        is_valid = false;
                        break;
                    }
                    cnt = 0; // 这一步可以不写, 因为上面if不满足的话, cnt一定是偶数
                }
                else cnt ++ ;
            if (cnt & 1) is_valid = false;
            st[i] = is_valid;
        }
		// 预处理(二): 预处理出f[k-1,i]到f[k,j]状态转移的所有合法方案, 此时属于减少不必要的枚举
        for (int i = 0; i < 1 << n; i ++ ){
            state[i].clear();
            for (int j = 0; j < 1 << n; j ++ )
                /*
                	i & j == 1 说明i和j的n位上有同时为1的情况, 这是不允许的, 若是i的某位为1,
                	说明在那个位置有从i的前一种状态伸出, 那么此时就不能在这个位置填一个块伸出到j对应位置
                	
                	st[i|j]==true 标明在i转换成j状态后,i中剩余连续的0是否符合偶数,因为剩下的0要填竖着的方块
                	例如i='10101' j='01000' i|j=='11101' 这个就是不符合条件的, 即i不能转化为j, 排除
                */
                if ((i & j) == 0 && st[i | j])
                    state[i].push_back(j);
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        /*******************************为什么f[0][0] = 1**********************************
			1. 题目中输入参数的列数是从1开始到m，即范围为1~m，但我们写的时候是将其先映射到数组0~m-1里
			2. 对于第一列，也就是数组中的第0列，是需要初始化的；也就是我们需要初始化f[0][x] = ?回到定义，
			f[0][x] 表示从-1列伸到0列(此处说的都是数组下标)状态为x的方案。
			3. 我们发现，合法的方案只能是不伸过来，因为根本没有-1列。即x只能取0的时候方案合法，f[0][0] = 1;
			接着dp过程就从第1列(数组下标)开始。
			4. 那么答案为什么是f[m][0] 呢，因为横放的时候方块最多够到第m-1列(数组下标)，不能从m-1再往外伸，
			所以是f[m][0];
        **********************************************************************************/
        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ )
                for (auto k : state[j])
                    f[i][j] += f[i - 1][k];	// 枚举所有符合从i-1的k状态且能成功转化i的j状态, 并累加

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

蒙德里安的猜想-记忆化搜索

定义状态: dp[i][j]表示前i - 1列的方格都已完全覆盖，第i列方格被第i - 1列伸出的方块覆盖后状态为j的所有方案数。

例如，上图表示的就是dp[3][010010]的状态(红色为2 * 1方块，绿色为1 * 2方块) 0 表示没有覆盖，1 表示覆盖。

状态转移:

我们采用由底至上的递推方式，即由当前状态推出下一列状态的方案数。

以某一列的状态而言

1. 【情况一】如果当前行的格子已被上一列伸出的方块覆盖，则跳过
2. 【情况二】如果当前行的格子未被覆盖，说明可以放一个1 * 2的方块
3. 【情况三】如果当前行的格子和下一行的格子都未被覆盖，说明可以放一个2 * 1的方块
4. 【总结】此列所有行的格子都覆盖完后，我们便可以得出下一列的合法状态

如上图，我们对第3列的状态进行搜索后可到达的其中一种状态

为什么要搜索?

根据dp数组的定义可知，第一列不可能被上一列伸出的方块覆盖，所以初始化为dp[1][000] = 1，搜索下一列可得：

可知第二列可到达的状态只有3种，于是进行第三列的搜索时只需从这3种状态开始dfs，当前阶段总是影响下一阶段，我们只对可到达的进行讨论，并不需要枚举每一种情况。

时间复杂度:

1. 外层循环时间: m * (1<<n) = 11*2^11
2. 递归时间: 最坏情况是一个不满的二叉树 2⁰+2¹+2²+...+2¹⁰ = (2¹¹ - 1)
3. 总时间 = 外层循环时间*递归时间 ≈ 10 * 2¹¹ * 2¹¹ = 46137344 ≈ 4e7

int n, m;
long long dp[12][2500];
void dfs(int row, int col, int state, int next) {
    //row为当前行, col为当前列, state为当前列的状态, next为可到达的下一列的状态
    //当前列全覆盖后可到达的下一个状态加上当前状态的方案数
    if (row == n) {
        //当前列所有行都已覆盖完毕
        dp[col + 1][next] += dp[col][state];
        return;
    }
    //情况一: 如果当前行(state二进制中第row位等于1)的格子已被覆盖,跳过
    if (state & (1 << row)) dfs(row + 1, col, state, next);
    else {
        //当前行未被覆盖，可放一个1*2的方块
        dfs(row + 1, col, state, next | (1 << row));// 情况二
        //当前行和下一行都未被覆盖，可放一个2*1的方块
        if (row + 1 < n && (state & (1 << (row + 1))) == 0) dfs(row + 2, col, state, next);// 情况三
    }
}
int main() {
    while (scanf("%d%d", &n, &m) && n && m) {
        if (n > m) swap(n, m);
        //因为n行m列和n列m行的方案数等价, 所以我们不妨将min(n, m)作为二进制枚举的指数, 减少方案数
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < (1 << n); j ++) {
                if (dp[i][j] > 0) {     //筛选出之前搜索过可到达的状态
                    dfs(0, i, j, 0);
                }
            }
        }
        //因为下标从0开始，所以dp[m][0]表示第m + 1列没有任何第m列的方块伸出的方案数
        cout << dp[m][0] << endl;
    }
    return 0;
}

最短Hamilton路径

题目描述: 给定一张n个点的带权无向图，点从0 ~ n-1标号，求起点0到终点n-1的最短Hamilton路径。Hamilton路径的定义是从0到n-1不重不漏地经过每个点恰好一次。

状态表示: f[i][j]

• 集合: 所有从0走到j，走过的所有点是i的所有路径
• 属性: Min

状态计算: 0→...→k→j f[ i ][ j ] = min(f[ i ][ j ], f[ i - (1 << j) ][ k_i ] + w[ k_i ][ j ])

int f[M][N],w[N][N];
int main(){
    cin >> n;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            cin >> w[i][j];
    memset(f, 0x3f, sizeof f);	// 初始化费用最大值
    f[1][0] = 0;				// 0 到 0 路径只有 0 的费用是 0
    //for (int i = 0; i < 1 << n; i ++)
    for (int i = 1; i < 1 << n; i += 2)	//优化: 0001 + 10 = 0011 因为第0位始终只有是1才是合法的, 所以+2是符合条件的
        for (int j = 0; j < n; j ++)
            if (i >> j & 1)		// i的第j位二进制是否为1
                for (int k = 0; k < n; k ++)  // 节点j的前一个路径节点k
                    if(i - (1 << j) >> k & 1)	// i - 1 << j 的第k位是否为1
                       f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
    cout << f[(1 << n) - 1][n - 1] << endl;	// f[11...11][n - 1]是答案
    return 0;
}

树形DP-没有上司的舞会

题目描述: Ural大学有N名职员，编号为1～N。他们的关系就像─棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数H_i给出，其中1≤i≤N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

状态表示: f[u][0]，f[u][1]

• 集合: f[u][0]表示以u为根节点且u不参加的快乐指数最大值，f[u][1]表示以u为根节点且u参加的快乐指数最大值
• 属性: Max

状态计算: f[u][0] += max(f[u_i][0], f[u_i][1])，f[u][1] += f[u_i][0]

最后的结果ans = max(f[u, 0], f[u, 1]])

void dfs(int u){
    f[u][0] = 0;       // 不加当前结点
    f[u][1] = a[u];    // 加上当前结点
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dfs(j);       // 一直递归到最深处
        f[u][0] += max(f[j][0], f[j][1]); // 不加当前结点,那么他的子结点就可以选或者不选
        f[u][1] += f[j][0];                     // 加上当前结点,那么他的子结点只能不选
    }
}
for(int i = 1; i <= n; i++) if(!ru[i]) root = i; // 找出根节点
dfs(root);
printf("%d\n", max(f[root][0], f[root][1]));

记忆化搜索

题目描述: 一张n*m的图，图上每一个点都有一个高度，a点走到b点的要求是a点高度要大于b点高度，求某个点可以走的最大步数。

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

如上图最大的步数是从25走，螺旋路线，最远走到1，一共25步

int n, m;
int g[N][N],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[x][y] > g[a][b])
            v = max(v, dp(a, b) + 1);
    }
    return v;
}
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));
printf("%d\n", res);

贪心-思想

区间问题

区间选点

题目描述: 给定N个闭区间[a_i,b_i]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。位于区间端点上的点也算作区间内。

struct Range{
    int l, r;
    bool operator< (const Range &W)const{
        return r < W.r;
    }
}range[N];
sort(range, range + n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
    if (range[i].l > ed){
        res ++ ;
        ed = range[i].r;
    }

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

最大不相交区间数量

题目描述: 给定N个闭区间[a_i,b_i]，请你在数轴上选择若干区间，使得选中的区间之间互不相交(包括端点)。输出可选取区间的最大数量。

计算方法和区间选点一模一样。

struct Range{
    int l, r;
    bool operator< (const Range &W)const{
        return r < W.r;
    }
}range[N];
sort(range, range + n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
    if (range[i].l > ed){
        res ++ ;
        ed = range[i].r;
    }

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

区间分组

题目描述: 给定N个闭区间[a_i,b_i]，请你将这些区间分成若干组，使得每组内部的区间两两之间(包括端点)没有交集，并使得组数尽可能小。输出最小组数。

思路:

1. 将所有区间按左端点从小到大排序
2. 从前往后处理每个区间，判断能否将其放到某个现有的组中L[i] > Max_r
   1. 如果不存在这样的组，则开新组，然后再将其放进去;
   2. 如果存在这样的组，将其放进去，并更新当前组的Max_r

sort(range, range + n);
priority_queue<int, vector<int>, greater<int>> heap;// 小根堆里存在每个组右端点
for (int i = 0; i < n; i ++ ){
    auto r = range[i];
    if (heap.empty() || heap.top() >= r.l) heap.push(r.r);// 最小的右端点都大于r.l那就需要新开一个组
    else{		// 否者就把这个组加入右端点最小的那个组, 并且更新
        heap.pop();
        heap.push(r.r);
    }
}
printf("%d\n", heap.size());

区间覆盖

题目描述: 给定N个闭区间[a_i, b_i]以及一个线段区间[s, t]，请你选择尽量少的区间，将指定线段区间完全覆盖。输出最少区间数，如果无法完全覆盖则输出 -1。

核心思想: 在左端点l都小于等于st的情况下, 取右端点最大的小区间

1. 将所有区间按照左端点从小到大进行排序
2. 从前往后枚举每个区间，在所有能覆盖start的区间中，选择右端点的最大区间，然后将start更新成右端点的最大值 这—步用到了贪心决策

int n;
int st, ed;
struct Range{
    int l, r;
    bool operator< (const Range &W)const{
        return l < W.l;
    }
}range[N];

sort(range, range + n);

int res = 0;
bool success = false;
int i = 0;
while (i < n){
    int r = -2e9;
    /*********************************************************************************
        int r = -2e9 不能放在外面
        例如: 
        4 10
        2
        4 5
        11 12  这个样例不会执行里面的while,i 不会 ++, 且if (r < st) 永远不会执行, 就会陷入死循环
    **********************************************************************************/
    while (i < n && range[i].l <= st){	//在左端点l都小于等于st的情况下, 取右端点最大的小区间
        r = max(r, range[i].r);
        i ++ ;
    }

    if (r < st){	// 若 r < st 即说明while循环结束条件是 i < n, 所以说明所有的区间都不在[st, ed]里面
        res = -1;
        break;
    }

    res ++ ;		// 成功找到合适的一个区间预设res ++
    if (r >= ed){	// 若 r >= ed 说明已经找到一个合适的区间, 此时退出, 贪心停止
        success = true;
        break;
    }

    st = r;			// st值设定成当前寻找的符合条件的右端点
}

if (!success) res = -1;
printf("%d\n", res);

Huffman树-合并果子

priority_queue<int, vector<int>, greater<int>> heap;
while (n --){
    int x;
    scanf("%d", &x);
    heap.push(x);
}

int res = 0;
while (heap.size() > 1){
    int a = heap.top(); heap.pop();
    int b = heap.top(); heap.pop();
    res += a + b;
    heap.push(a + b);
}

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

排序不等式-排队打水

题目描述: 有n 个人排队到1个水龙头处打水，第i个人装满水桶所需的时间是t，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小?

sort(t, t + n);
reverse(t, t + n);
LL res = 0;
for (int i = 0; i < n; i ++ ) res += t[i] * i;
printf("%lld\n", res);

绝对值不等式-货仓选址

题目描述: 在—条数轴上有N家商店，它们的坐标分别为A₁～ A_N。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

sort(a,a + t);
int ans = 0;
for(int i = 0; i < t; i ++) 
    /*
    	1. 当n为奇数时, 站点放在中位数a[t/2]时ans最小
    	2. 当n为偶数时, 站点放在范围为a[(t-1)/2]~a[t/2]中任意位置都行,设[a,b]中有一个x,即|a - x| + |b - x| = b - a
    	3. 所以无论n为奇数还是偶数, ans都是最小
    */
    ans += abs(a[i] - a[t/2]);
cout << ans << endl;
/*
1 2 3 4 5 6
4 - 1 + 4 - 2 + 4 - 3 = 6
*/

推公式-耍杂技的牛

题目描述: 农民约翰N头奶牛(编号为1..N)计划逃跑并加入马戏团，为此它们决定练习表演杂技。奶牛们不是非常有创意，只提出了一个杂技表演:
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这N头奶牛中的每一头都有着自己的重量W_i以及自己的强壮程度S_i。一头牛支撑不住的可能性取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

贪心思路: 按照w_i+s_i从小到大的顺序排，最大的危险系数一定是最小的。

typedef pair<int, int> PII;
const int N = 50010;
int n;
PII cow[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int s, w;
        scanf("%d%d", &w, &s);
        cow[i] = {w + s, w};
    }
    sort(cow, cow + n);
    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i ++ ){
        int s = cow[i].first - cow[i].second, w = cow[i].second;
        res = max(res, sum - s);
        sum += w;
    }
    printf("%d\n", res);
    return 0;
}