基础算法模板¶

基础算法¶

排序¶

快速排序

双指针, 两端靠中间遍历, 如果大小不对就调换, 直至相遇

C++
void quick_sort(int a[], int l, int r)
{
    // (1) 递归出口
    if (l >= r) return;

    int x = a[(l+r)>>1]; // 取中间数x
    int i = l-1, j = r+1; // 边界范围要小心

    // (2) 调节位置
    while(i < j)
    {
        do(i++); while(a[i] < x); // 严格小于
        do(j--); while(a[j] > x); // 严格大于
        if (i < j) swap(a[i], a[j]); // 必须要写限制条件
    }

    // (3) 递归处理
    quick_sort(a, l, j);
    quick_sort(a, j+1, r);

    // 另一种写法，注意对称
    // quick_sort(a, l, i-1);
    // quick_sort(a, i, r);
}

归并排序

先分成“各自单调递增”的两段, 再根据“大小比对”进行合并

C++
void merge_sort(int a[], int l, int r)
{
    // (1) 递归出口
    if (l >= r) return;

    // (2) 先归并，形成自递增的两段
    int mid = (l+r) >> 1;

    merge_sort(a, l, mid);
    merge_sort(a, mid+1, r);

    // (3) 合并处理
    int i = l, j = mid+1;
    int k = 0;

    while((i <= mid) && (j <= r)) // 一定是 <=
    {
        if(a[i] <= a[j]) tmp[k++] = a[i++]; // 这里=无所谓，但出于稳定性是让==取前者为好
        else tmp[k++] = a[j++];
    }

    // (4) 尾巴处理
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

    // (5) 将tmp暂存的结果塞回原数组对应位置
    for (int i=l, j=0; i<=r; i++, j++)
    {
        a[i] = tmp[j];
    }
}

二分¶

整数二分

尤其注意 mid 的取法(是否包含+1), 以及更新方式

C++
int ope_lfs(int l, int r, int ans)
{
    // 找到左边界
    // 第一个 >= ans的数的index
    // 课上的绿模型
    while(l < r)
    {
        int mid = (l+r) >> 1;

        if (a[mid] < ans){
            l = mid + 1;
        }
        else {
            r = mid;
        }   
    }

    if(a[l] != ans) {
        return -1;
    }
    else {
        return l;
    }
}

int ope_rfs(int l, int r, int ans)
{
    // 找到右边界
    // 最后一个 <= ans的数 的index
    // 课上的红模型
    while(l < r)
    {
        int mid = (l+r+1) >> 1;

        if (a[mid] > ans){
            r = mid - 1;
        }
        else {
            l = mid;
        }   
    }

    if(a[l] != ans) {
        return -1;
    }
    else {
        return l;
    }
}

浮点数二分

好写, 因为不存在边界问题

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

double minus_triple(double n)
{
    double l=-100, r=100; // 三次方根会存在负数
    while (r-l > 1e-8)
    {
        double mid = (l+r) / 2;
        if(check(mid)) r = mid;
        else l = mid;
    }

    return l;
}

int main()
{
    cin >> n;
    // 设置输出精度, 用 iomanip 的 fixed 和 setprecision
    cout << fixed << setprecision(6) << minus_triple(n) << endl;
    return 0;
}

前缀和¶

一维前缀和

C++
// 预处理
for (int i=1; i<=n; i++) s[i] = s[i-1] + a[i];
// 计算 a[l] + ... + a[r]
s[r] - s[l-1]

二维前缀和

C++
// 预处理
for (int i=1; i<=n; i++) {
    for (int j=1; j<=m; j++) {
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    }
}
// 计算 (x1, y1) 到 (x2, y2)
s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]

差分¶

b 是 a 的 “差分”, a 是 b 的 “前缀和”

思考方式: 考虑 差分数组 + c 对 原数组 的影响, 尤其是“后效性”

一维差分

操作重点 (insert函数):

C++
// a[l, r] 每个元素加上 c, 等价于:
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r+1] -= c;
}

全代码:

C++
// 使用 insert 的逻辑对 b 进行初始化
for (int i=1; i<=n; i++) insert(i, i, a[i]);
// 更新操作
while (m--)
{
    int l, r, c;
    cin >> l >> r >> c;
    insert(l, r, c); // 每一轮都对差分数组b进行对应操作
}
// 利用差分数组b的前缀和是 a，求 a
for(int i=1; i<=n; i++)
{
    a[i] = a[i-1] + b[i];
    cout << a[i] << " ";
}

二维差分

操作重点 (insert函数):

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

全代码:

C++
// 初始化 差分数组b
for (int i=1; i<=n; i++) {
    for (int j=1; j<=m; j++) {
        insert(i, j, i, j, a[i][j]);
    }
}

while(q--) 
{
    int x1, y1, x2, y2, c;
    cin >> x1 >> y1 >> x2 >> y2 >> c;
    insert(x1, y1, x2, y2, c); // 按需增量改变b数组
}

// 给b求前缀和，从而得到a
for (int i=1; i<=n; i++) {
    for (int j=1; j<=m; j++) {
        a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
        cout << a[i][j] << " ";
    }
    cout << endl;
}

数据结构¶

链表与双链表¶

单链表

具体操作:

C++
int head, e[maxn], ne[maxn], idx;
// head: 表头, 初始化指向空节点, head=-1
// e:    value数组
// ne:   next数组
// idx:  当前在node池里抽到几了

// 链表初始化: HEAD -> Tail(-1)
void init()
{
    // 我们命令所有空节点都是-1
    head = -1; // HEAD指向空节点 <=> 值为-1
    idx = 0; // 还没开始从node池里抽卡
}

// 在头节点后面直接插入一个值为x的node
void add_to_head(int x)
{
    // <=> HEAD 指向这个 X node
    e[idx] = x; // 当前节点赋值
    ne[idx] = head;
    head = idx ++;
}

// 在index=k的node后面，插入一个值为x的node
void insert(int k, int x)
{
    e[idx] = x; // 从池里抽一个实体，并赋值x
    ne[idx] = ne[k]; // 节点连接
    ne[k] = idx ++; // 节点连接
    // idx++ 更新池里抽卡
}

// 删除 k节点 后面的节点
void remove(int k)
{
    ne[k] = ne[ne[k]];
    // 只涉及现有链的连接更替，没有从池里抽卡
}

遍历输出:

C++
for (int i = head; i != -1; i = ne[i]) {
    // 链表的遍历方式: HEAD -> Tail, i = ne[i]
    cout << e[i] << ' ';
}

双链表

C++
int e[maxn], l[maxn], r[maxn], idx;
// 在双向链表的题型中，我们不设置HEAD && Tail，而是用0和1默认表示HEAD和Tail
// HEAD = 0
// Tail = 1
// e: 当前node的值
// l: 左连接
// r: 右连接
// idx: 从node池子里抽卡的index

// 初始化链表 0 (HEAD) <=> 1 (Tail)
void init()
{
    r[0] = 1; // ->
    l[1] = 0; // <-
    idx = 2; // 0和1专门给HEAD和Tail用的，因此抽卡下标从2开始
}

// 在节点k的右边插入一个值为x的node
void insert (int k, int x)
{
    e[idx] = x; // 给节点赋值

    l[idx] = k; // 节点连接
    r[idx] = r[k];
    l[ r[k] ] = idx;
    r[k] = idx++; // 记得给池子更新
}

// 删除k节点
void remove (int k)
{
    l[ r[k] ] = l[k]; // 连接更新
    r[ l[k] ] = r[k];
    // 鉴于没有从池里抽卡，idx不变
}

KMP¶

C++
int ne[maxn_N];
char s[maxn_M], p[maxn_N];

// 经典KMP问题: 字符串匹配
// 要点是: (1) next数组 (2) 下标从1开始写
// 详细解析看看笔记，很重要的思想

int main()
{
    int n, m;
    cin >> n >> p + 1;
    cin >> m >> s + 1;

    // j是代表已经匹配成功的元素个数

    for (int i = 2, j = 0; i <= n; i ++ ) // 求next数组
    {
        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)
        {
            cout << i-n << " ";
            j = ne[j];
        }
    }

    return 0;
}

Trie 树¶

I x: 向集合中插入一个字符串 x
Q x: 询问一个字符串在集合中出现了多少次

C++
const int maxn = 1e5+10;
// 仅包含小写英文字母: 每个节点向下最多有26个直接子节点
// 我们认为0表示空节点
int son[maxn][26]; // 每个节点向下的直接子节点
int cnt[maxn]; // cnt[x]: 以x结尾的单词数量
int idx; // 当前在node池里抽到谁了
string str; // 维护一整棵“全局trie树”

void insert (string str)
{
    int p = 0; // 记录插到哪里才到头
    for (int i=0; str[i]; i++) // 只要当前str没到头，就一直做
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx; // 如果当前点不存在，插入
        p = son[p][u]; // 向下走
    }

    cnt[p]++; // 以p结尾的单词数量
}

int query (string 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];
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        string op;
        cin >> op >> str;
        if (op == "I") {
            insert(str);
        }
        else {
            cout << query(str) << endl;
        }
    }

    return 0;
}

并查集¶

问题:

M a b，将编号为 a 和 b 的两个数所在的集合合并. 如果两个数已经在同一个集合中，则忽略这个操作
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中

原理:

每个集合用一棵树来表示, 树根编号即为此集合的编号
每个node存储它的父节点的编号

特点1 判断是不是树根:

C++
if (p[x] == x)

特点2 判定 x 的集合编号:

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

特点3 集合合并:

C++
p[ p_x ] = y // p_x 是 x 所在子树的祖宗节点

题目:

C++
// 并查集模板
// p[x]: x的父节点
// 树根 (属性来源): p[x] = x;
// 

int p[maxn];
int n, m;

void init()
{
    // 初始化方法 (最开始每个数各自在一个集合中)
    for (int i=1; i<=n; i++) p[i] = i;
}

int find (int x)
{
    // 找到x的祖先节点(路径压缩)
    if (p[x] != x) {
        // 只要还没到达祖先节点
        p[x] = find( p[x] ); // 递归向上找
    }

    return p[x];
}

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

    init();

    while (m--)
    {
        string op;
        int a, b;
        cin >> op >> a >> b;

        if (op == "M") { // merge set
            p[find(a)] = find(b); // 树的嫁接，表示集合合并
        }
        else { // query
            if (find(a) == find(b)) cout << "Yes" <<endl;
            else cout << "No" << endl;
        }
    }

    return 0;
}

堆¶

源码构造不讲了，讲一下如何调用STL:

C++
#include <queue>

大根堆:

C++
// 初始化
priority_queue<int> heap;
// 插入元素
heap.push(3);
// 访问堆顶元素
heap.top()
// 弹出堆顶元素
heap.pop()

小根堆:

C++
// 初始化
priority_queue<int, vector<int>, greater<int>> heap;

基于堆为结构体排序:

C++
struct Node {
    int val;
    bool operator>(const Node& other) const {
        // 如果当前节点的 val 值大于另一个节点的 val 值
        // 则当前节点"大于"另一个节点
        return val > other.val;
    }
};

priority_queue<Node, vector<Node>, greater<Node>> custom_heap;
// 创建了一个按 val 值升序排列的小根堆, 堆顶元素总是当前所有元素中 val 值最小的

哈希表¶

模拟散列表

维护一个集合，支持如下几种操作:

I x，插入一个整数 x
Q x，询问整数 x 是否在集合中出现过

(1) 拉链法: 本质是mod成剩余系 (找质数 + 列表插入法)

C++
// 观察 1e9 -> 1e5: 经典哈希表
// 哈希表: 拉链法
// 操作数量 N = 1e5 -> 找大于1e5的第一个质数

const int maxn = 1e5 + 3;
int h[maxn], e[maxn], ne[maxn], idx; // 链表那一套
int n;

/*
前置工作:

int find_prime()
{
    // return: 大于1e5的第一个质数
    for (int i=1e5;;i++)
    {
        int flag = true;
        for (int j=2;j*j<=i;j++)
        {
            if (i % j == 0)
            {
                flag = false;
            }
        }

        if (flag) return i;
    }
    // ans: 100003
}
*/

void insert(int x)
{
    int k = (x % maxn + maxn) % maxn; // k是应该指向哈希表的下标
    e[idx] = x; // node赋值
    ne[idx] = h[k];
    h[k] = idx++; // 节点连接更新，idx++更新在大池中的抽卡序号
}

int find(int x)
{
    int k = (x % maxn + maxn) % maxn;
    for (int i = h[k]; i != -1; i = ne[i])
    {
        if (e[i] == x) return true;
    }
    return false;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof(h)); // h数组全部初始化成-1

    while (n--)
    {
        string op;
        cin >> op;
        int x;
        if (op == "I")
        {
            cin >> x;
            insert(x);
        }
        else
        {
            cin >> x;
            if (find(x)) cout << "Yes" <<endl;
            else cout << "No" <<endl;
        }
    }

    return 0;
}

(2) 开放寻址法: 本质是mod成剩余系 (找质数 + 找"坑位")

C++
// 观察 1e9 -> 1e5: 经典哈希表
// 哈希表: 开放寻址法
// 操作数量 N = 1e5 -> 找大于 1e5 * 2 的第一个质数

const int maxn = 2e5 + 3, null = 0x3f3f3f3f;
// 0x3f3f3f3f > 1e9
// 初始化每个元素，肯定不能在任何题目可能触及到的数据范围内
int h[maxn];
int n;

/*
前置工作:

int find_prime()
{
    // return: 大于2e5的第一个质数
    for (int i=2e5;;i++)
    {
        int flag = true;
        for (int j=2;j*j<=i;j++)
        {
            if (i % j == 0)
            {
                flag = false;
            }
        }

        if (flag) return i;
    }
    // ans: 200003
}
*/

int find(int x)
{
    int k = (x % maxn + maxn) % maxn;

    while (h[k]!=null && h[k]!=x)
    {
        k++;
        if (k == maxn) k = 0; //遍历到上边界的话，归0，从头再开始遍历，保证完全性
    }

    return k;
}

int main()
{
    cin >> n;
    memset(h, 0x3f, sizeof(h)); // h数组全部初始化成 +inf

    while (n--)
    {
        string op;
        cin >> op;
        int x;
        if (op == "I")
        {
            cin >> x;
            h[find(x)] = x;
        }
        else
        {
            cin >> x;
            if (h[find(x)] != null) cout << "Yes" <<endl;
            else cout << "No" <<endl;
        }
    }

    return 0;
}

字符串哈希

求: str[l, r]

预处理:

C++
h[i] = h[i-1] * p + str[i];

子串表示:

C++
h[l, r] = h[r] - h[l] * p^( r - (l-1) )

全代码:

C++
typedef unsigned long long ULL; // 利用2^64自动溢出来实现取模

const int maxn = 1e5 + 10, P = 131;
// P: 经验值. 131 / 13331

int n, m;
char str[maxn];
ULL h[maxn], p[maxn];
// p[i] = P^i，表示方幂 (P经验值131/13331)

ULL get (int l, int r)
{
    return (h[r] - h[l-1] * p[r-l+1]);
}

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

    p[0] = 1;

    for (int i=1; i<=n; i++)
    {
        // 预处理h
        h[i] = h[i-1] * P + str[i];
        p[i] = p[i-1] * P; // 顺便把P^i也计算一下
    }

    while (m--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

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

    return 0;
}

搜索与图论¶

DFS and BFS¶

重点 1: DFS记得“恢复现场”
重点 2: BFS使用queue, 本身具备“最短路径”的属性

DFS

C++
// 全排列: 经典DFS思路
// 方法: 枚举第i位的可能性

int path[maxn], st[maxn];
// a:  记录路径的数组
// st: “每个数是否被用过”
int n;

void dfs(int u)
{
    // 考察第u位 (搜索树第u层)
    if (u==n) 
    {
        for (int i=0; i<n; i++) cout << path[i] << " ";
        cout << endl;

        return;
    }

    for (int i=1; i<=n; i++)
    {
        if (!st[i]) // 如果i没被使用过
        {
            path[u] = i; // 第u位放i
            st[i] = true; // i“被使用”
            dfs(u+1); // 考察下一位
            st[i] = false; // “恢复现场”
        }
    }
}

int main()
{
    cin >> n;

    // 搜索树根节点是0，第一位是第一层(1__ / 2__ / 3__)，因此起点是0
    dfs(0);

    return 0;
}

BFS

C++
const int maxn = 110;
typedef pair<int, int> PII;
// PII 等价于 struct node (x, y)

int n, m;
int g[maxn][maxn]; // 地形矩阵
int dis[maxn][maxn]; // 每个点到起点的距离

// 方向数组
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int bfs()
{
    queue<PII> q;

    // distance init
    memset(dis, -1, sizeof(dis)); // 每个点到起点的距离是-1
    dis[1][1] = 0; // 先处理起点

    q.push( {1,1} ); // 起点先入队

    while(!q.empty())
    {
        // 取出队首元素并弹出
        auto t = q.front();
        q.pop();

        for (int i=0; i<4; i++)
        {
            int xx = t.first + dx[i];
            int yy = t.second + dy[i];

            if (xx>=1 and xx<=n and yy>=1 and yy<=m)
            {
                // 地理边界不能出
                if (!g[xx][yy] and dis[xx][yy]==-1)
                {
                    // 不能是1(无法经过之地)
                    // 距离必须是“本轮才被更新”(确保最短路)
                    dis[xx][yy] = dis[t.first][t.second] + 1;
                    q.push( {xx, yy} );      
                }
            }
        }
    }

    return dis[n][m];
}

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

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

    // bfs 本身就具有最短路性质
    cout << bfs() << endl;

    return 0;
}

BFS实现拓扑排序

C++
const int node_maxn = 1e5+10;
const int edge_maxn = 1e5+10;

/*
典型的拓扑排序

1. 入度==0: 第一波入队
2. 扩展:
    - 砍相连的边
    - 砍后入度==0的点入队
*/

int n, m;
int h[node_maxn], e[edge_maxn], ne[edge_maxn], idx;
int d[node_maxn]; // 每个点的入度
queue<int> q; // BFS做拓扑排序
vector<int> ans_seq; // 装答案的

void add(int a, int b)
{
    // 建立有向边 a->b
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int topo_sort()
{
    for (int i=1; i<=n; i++)
    {
        if (!d[i]) q.push(i);
    }

    while (!q.empty())
    {
        // 取出队首并弹出
        int t = q.front();
        q.pop();
        ans_seq.push_back(t);

        for (int i=h[t]; i!=-1; i=ne[i])
        {
            int j = e[i]; // i->j
            d[j]--; // 被指向者砍边, 入度--
            if (!d[j]) q.push(j);
        }
    }

    return (int) ans_seq.size() == n;
}

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

    for (int i=1; i<=m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a,b);
        d[b]++; // 入度
    }

    if (!topo_sort()) cout << "-1" << endl;
    else {
        for (auto i = ans_seq.begin(); i!=ans_seq.end(); i++)
        {
            cout << *i << " ";
        }
        cout << endl;
    }

    return 0;
}

树和图的 DFS && BFS¶

树和图的存储: 邻接表, 类比"拉链法"中的操作
输入处理点和边:

C++
for (int i=1; i<=m; i++)
{
    // a ---_c_---> b
    int a, b, c;
    cin >> a >> b >> c;
    // 自环处理 (赋0)
    if (a==b) g[a][b] = 0; 
    // 重边处理 (取min)
    g[a][b] = min(g[a][b], c);
}

Tree DFS

C++
/*
经典图论题型: 树和图的存储 / 遍历

- 存储使用邻接表
普通的拉链法(h/e/ne/idx) => 建立有向边
需要无向边的话，就是add(a,b) | add (b,a)

- 本题采取遍历使用DFS: 
1. left_son_maxnum
2. right_son_maxnum
3. father_above: <=> n - cur_size
*/

int n, m;
int h[maxn], e[maxn*2], ne[maxn*2], idx; // 拉链法那一套
/*
每当插入一条边的时候 就需要申请一个节点 
树有n-1条边 每一条边看作是两条有向边 
故需插入2(n-1)条边 共需申请2(n-1)个节点
*/
int ans = maxn; // 答案
bool st[maxn]; // 该点是否被“考察过”

void add(int a, int b)
{
    // 建边 a->b
    // <=>在a处插入node_b并建立指针
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dfs(int u)
{
    // 走到u这个节点，现在形成“多个子树” + “顶上的父树”
    st[u] = true; // 这个点开始考察

    int size = 0, sum = 0; // size指u节点的单个子树的值

    for (int i=h[u]; i!=-1; i=ne[i])
    {
        // 遍历所有子节点 (get子树数)
        int j = e[i]; // 节点编号

        if (st[j]) continue; // 考察过的就跳过

        int s = dfs(j); // 子树的大小
        size = max(size, s); // 比较当前的子节点的最大值和之前的子节点的最大值
        sum += s; //计算u节点所统领的所有子节点
    }

    size = max(size, n - sum - 1);
    // size:    u的最大子树
    // n-sum-1: 图在去除以n为根的树后剩下的子节点值
    ans = min(ans, size); // 最大值的最小值

    return sum+1;
}

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

    int times = n-1;

    while ( times-- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b); // a -> b
        add(b, a); // b -> a
    }

    dfs(1);

    cout << ans << endl;

    return 0;
}

Tree BFS

C++
const int node_maxn = 1e5+10;
const int edge_maxn = 1e5+10;

int n, m;
int h[node_maxn], e[edge_maxn], ne[edge_maxn], idx;
int d[node_maxn]; // 1 号点到 n 号点的最短距离

void add(int a, int b)
{
    // 建立有向边 a->b [拉链法]
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int bfs()
{
    queue<int> q;
    memset(d, -1, sizeof(d)); // 距离初始化

    // 起点先考虑并初始化
    d[1] = 0;
    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]; // 考察node_j

            // 已经考察过的就不考察 (保证最短路)
            if (d[j] != -1) continue;

            d[j] = d[t] + 1; // t->j
            q.push(j);
        }
    }

    return d[n];
}

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

    for (int i=1; i<=m; i++)
    {
        // 注意这里不可以直接用while(m--)
        // 因为改变了m的值，会改变后面图中的定义
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    cout << bfs() << endl;

    return 0;
}

最短路算法¶

朴素 Dijkstra: 适合稠密图
堆优化版本的 Dijkstra: 适合稀疏图
Bellman-Ford: 有负环也可以做
SPFA: 有负环就不能做了, 可用来判断负环
Floyd

(1) 朴素 Dijkstra: 适合稠密图

C++
/*
看一下n和m的数据范围 -> 稠密图 -> 朴素 dijkstra

"可能存在重边和自环":
1. 自环: 令g[i][i] = 0;
2. 重边: 取a->b所有重边的min => d[a][b] = min(g[a][b], w_i)
*/

int n, m;
int g[node_maxn][node_maxn];
// g[i][j]: i->j 的边权
int dist[node_maxn]; // 每个点到1号起点的距离
bool st[node_maxn];  // st表示当前“已确定min_distance”的点的集合

int dijkstra()
{
    // 距离初始化 (“每个点离起点的距离”)
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    // 遍历全部点，取“不在S中的 离起点距离最近的”点

    for (int i=1; i<=n; i++) // 简单的“做n次”罢了, 不能用while(n--)
    {
        int t = -1; // 记录谁是“不在S中的离起点距离最近”的点

        for (int j=1; j<=n; j++)
        {
            if (!st[j] && (t==-1 || dist[t] > dist[j])) {
                // 这句话比较难理解，它做的是:
                // 不在S中的 离起点距离最近的点
                // !st[j]: 最近距离还没有确定的点
                // dist[t] > dist[j]: 符合!st[j]条件的"距离最小"的点
                // t==-1: 当第一次遇到未确定的点时能够被初始化
                t = j;
            }
        }

        // t是: 不在S中的离起点距离最近的点
        // 现在要用t去更新其他点的距离

        for (int j=1; j<=n; j++) {
            dist[j] = min (dist[j], dist[t] + g[t][j]);
        }

        st[t] = true; // t加入st大家庭(“已被使用”)
    }

    if (dist[n] == 0x3f3f3f3f) {
        // 无法从 1 号点走到 n 号点
        return -1;
    }
    else {
        return dist[n];
    }
}

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

    memset(g, 0x3f, sizeof(g)); // 边权初始化+INF
    /*
    memset的值是按byte覆盖上去，由于g[i][j]是int, 4字节
    因此每个边权初始化成0x3f3f3f3f (> 1e9)
    */

    for (int i=1; i<=m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;

        // if (a==b) g[a][b] = 0; // 自环处理 (赋0)

        g[a][b] = min(g[a][b], c); // 重边处理 (取min)
    }

    cout << dijkstra() << endl;

    return 0;
}

(2) 堆优化版本的 Dijkstra: 适合稀疏图

C++
const int node_maxn = 1e6;
const int edge_maxn = 1e6;

typedef pair<int, int> PII;
// PII.first = distance, PII.second = node_index

/*
看一下n和m的数据范围 -> 稀疏图 -> 堆优化 dijkstra

"稀疏图": 邻接表 -> 拉链法
"堆": 最短路 -> 小根堆 -> priority_queue

"可能存在重边和自环":
1. 自环: 令g[i][i] = 0;
2. 重边: 取a->b所有重边的min => d[a][b] = min(g[a][b], w_i)
*/

int n, m;
int h[node_maxn], w[edge_maxn], e[edge_maxn], ne[edge_maxn], idx;
// w[i]: idx对应的那条边的权重
int dist[node_maxn];
bool st[node_maxn];

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));
    dist[1] = 0;

    // 建小根堆: 返回“不在S中的离起点距离最近”的点
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0,1}); // 起点入堆

    while (heap.size())
    {
        // 返回“离起点最近”的点
        auto t = heap.top();
        heap.pop();

        int distance = t.first;
        int node_idx = t.second;

        // 如果已经在S中，就直接跳过!
        if (st[node_idx]) continue; // 只做S集合外的剩余节点

        // 现在node_idx就是“不在S中的离起点距离最近”的点
        st[node_idx] = true;

        // 用node_idx扩展剩余点的最短路径
        for (int i=h[node_idx]; i!=-1; i=ne[i])
        {
            int j = e[i]; // node_idx -> j

            if (dist[j] > dist[node_idx] + w[i]) {
                dist[j] = dist[node_idx] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

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

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

    memset(h, -1, sizeof(h)); // 邻接表初始化

    for (int i=1; i<=m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c); // 建边a->b, 边权为c
    }

    cout << dijkstra() << endl;

    return 0;
}

(3) Bellman-Ford: 有负环也可以做

C++
const int node_maxn = 500+10;
const int edge_maxn = 1e4+10;
const int INF = 0x3f3f3f3f;

struct Edge{
    int a;
    int b;
    int c; // a->b, weight=c
}edges[edge_maxn];

int n, m, k;
int dist[node_maxn];
// 在做某个操作之前，先“备份快照”
int backup[node_maxn];
/* 为什么要“backup”
在进行第k次遍历的时候，如果我们更新a->b的边，得到dist[b],
再更新b->c的边的时候，使用了已更新的dist[b]去更新dist[c]，
其实是遍历了两条边，
但bellman_ford算法在每一次遍历的时候，只允许更新一条边，
所以需要用一个backup数据，保证不会发生一次遍历中更新多条边
*/

void bellman_ford()
{
    // 距离初始化
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    // for k 次: "最多经过 k 条边"
    for (int i=1; i<=k; i++)
    {
        // 在做操作之前，先把当前状态保存备份一下
        memcpy(backup, dist, sizeof(dist)); // 复制dist内容到backup中

        // 操作
        for (int j=1; j<=m; j++) // 遍历所有边，做“松弛操作”
        {
            auto e = edges[j]; // 取出一条边
            dist[e.b] = min(dist[e.b], backup[e.a] + e.c);
            // “松弛操作”: i-j
            // 一定注意，是backup[i] + c !!!!!
        }
    }
}

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

    for (int i=1; i<=m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    bellman_ford();

    if (dist[n] > INF/2) cout << "impossible" << endl;
    else cout << dist[n] << endl;

    return 0;
}

(4) SPFA: 有负环就不能做了, 可用来判断负环

求最短路

C++
/*
含负权边，但不存在负权回路 => SPFA

原理跟Bellman-Ford一样，只是在更新时采用了优化
前躯优化 -> 后继优化 -> 采取BFS思想
*/

int n, m;
int h[node_maxn], w[edge_maxn], e[node_maxn], ne[node_maxn], idx;
int dist[node_maxn];
bool st[node_maxn]; 
// st维护的是: 每个点在queue当前轮次中只能出现一次

void add(int a, int b, int c)
{
    // a->b, weight=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 init
    queue<int> q;
    // 放入起点，起点加入S集
    q.push(1);
    st[1] = true;

    while (!q.empty())
    {
        // 取出队首并弹出
        int t = q.front();
        q.pop();

        st[t] = false; // 已经出队了

        // 更新t的所有出边, 如果没访问过，就入队
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i]; // t->j
            if (dist[j] > dist[t] + w[i])
            {
                // 更新t的所有出边
                dist[j] = dist[t] + w[i];

                if (!st[j]) // 如果没访问过
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

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

    memset(h, -1, sizeof(h)); // 初始化邻接表

    for (int i=1; i<=m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int dis = spfa();

    if (dis == INT_MAX) cout << "impossible" <<endl;
    else cout << dis << endl;

    return 0;
}

判断有无负环存在

C++
const int node_maxn = 2000+10;
const int edge_maxn = 10000+10;
const int INT_MAX = 0x3f3f3f3f;

int n, m;
int h[node_maxn], w[edge_maxn], e[edge_maxn], ne[edge_maxn], idx;
int dist[node_maxn], cnt[node_maxn];
// dist: 计算从起点走到这里的总路程
// cnt: 计算从起点走到这里一共“多少条边”
// cnt用于判断是否存在负环，抽屉原理
// 负环标志: cnt[n] >= n
bool st[node_maxn];
// st: 跟普通spfa一样，判断“当前queue中每个点只能存在一次”

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

int spfa()
{
    queue<int> q;

    // 之前普通的spfa是从1->n判断是否存在负环
    // 但是负环不一定只存在1->n的路径上
    // 因此需要所有起点都入队做一次

    for (int i=1; i<=n; i++)
    {
        st[i] = true;
        q.push(i);
    }

    while (!q.empty())
    {
        // 取出队头并弹出
        int t = q.front();
        q.pop();

        st[t] = false; // 弹出的“副作用”

        // 更新t的所有出边
        for (int i=h[t]; i!=-1; i=ne[i])
        {
            int j = e[i]; // t->j

            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

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

    for (int i=1; i<=m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

(5) Floyd:

C++
const int node_maxn = 210;
const int INT_MAX = 1e9;

int n, m, Q;
int d[node_maxn][node_maxn];

/*
多源汇最短路 => Floyd

可能存在重边和自环:

自环: d[i][i] = 0;
重边: 取min
*/

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

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

    // 边权初始化
    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] = INT_MAX;
        }
    }

    for (int i=1; i<=m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c); // 处理重边
    }

    floyd();

    while (Q--)
    {
        int a, b;
        cin >> a >> b;

        int ans = d[a][b];

        // INT_MAX/2: 原因和之前Bellman-Ford一样
        if (ans > INT_MAX/2) cout << "impossible" << endl;
        else cout << ans << endl;
    }

    return 0;
}

最小生成树¶

Prim:

C++
const int node_maxn = 500+10;
const int INF = 0x3f3f3f3f;

/*
最小生成树: 无自环 / 无向图
Prim 求最小生成树: 稠密图 -> 邻接矩阵
*/
int n, m;
int g[node_maxn][node_maxn]; // 邻接矩阵存边
int dist[node_maxn]; // 这个点到“连通块”的距离
bool st[node_maxn]; // 这个点“考察”过否

// Prim 处理
int prim()
{
    // 初始化: 所有点离“连通块集合”的Distance=INF
    memset(dist, 0x3f, sizeof(dist));

    int res = 0; // res: 最小生成树的边权之和
    for (int i=0; i<n; i++) // 迭代n次
    {
        int t = -1; // t: S集合以外距离S集合距离min的点

        for (int j=1; j<=n; j++)
        {
            if (!st[j] && (t==-1 || dist[t] > dist[j])) {
                // 1. 首先肯定是必须要“没访问”的
                // 2. 第一个点无脑加入(特殊处理): t==-1
                // 3. dist[j]只有比当前dist[t]还小时才更新
                t = j;
            }
        }

        // 这个点不是“第一个点”，它离当前集合的dist=INF
        // 说明肯定不连通，寻找失败
        if (i && (dist[t] == INF)) return INF;

        // 不是“第一个点”的点:
        // 1. 加上它到S连通块的“距离”
        // 2. 它加入S连通块
        if (i) res += dist[t];
        st[t] = true;

        // 用点t来更新其余点的距离
        for (int j=1; j<=n; j++) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
    /*
    Prim 和 Dijkstra 很像:

    - Dij中，迭代是n-1次，因为我们默认起点在最开始就已加入
    - Prim中，迭代是n次，因为不知道“谁是起点”

    - Dij中，dist表示的是每个点到起点的距离
    - Prim中，dist表示的是每个点到“当前连通块”的距离
    */
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g)); // 边权初始化成INF

    for (int i=1; i<=m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        // 自环处理: 变成0
        if (a==b) g[a][b] = g[b][a] = 0;
        // 重边处理: 取min
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int sum = prim();

    if (sum == INF) cout << "impossible" << endl;
    else cout << sum << endl;

    return 0;
}

Kruskal:

C++
const int node_maxn = 1e5+10;
const int edge_maxn = 2e5+10;
const int INF = 0x3f3f3f3f;

/*
Kruskal算法求最小生成树 -> 并查集

用结构体存边即可: 无向图 / 无自环
*/

int n, m;
int p[node_maxn]; // 并查集

struct Edge{
    int a, b, w;

    bool operator< (const Edge& W) const
    {
        return w < W.w;
    }
    // 重载<，这样sort的时候就会根据W.w来“从小到大”排序
}edges[edge_maxn];

int find(int x)
{
    // 找x的祖先节点(并查集)
    if (p[x]!=x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    // 按边权排序
    sort(edges+1, edges+1+m); // idx从1开始

    for (int i=1; i<=n; i++) p[i] = i; // 并查集初始化

    int res=0, cnt=0;
    // res: 边权和
    // cnt: 一共“归”了多少边 (最小生成树理论对应n-1条边)
    for (int i=1; i<=m; i++) // 按从小到大的边权枚举边
    {
        int a = edges[i].a; // 当前边的左端点
        int b = edges[i].b; // 当前边的右端点
        int w = edges[i].w;

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

        if (a != b) // 如果这两点不属于同一集合
        {
            p[a] = b; // 集合归并
            res += w;
            cnt++; // 归并边数+1
        }
    }

    if (cnt != n-1) return INF;
    return res;
}

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

    for (int i=1; i<=m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        // 自环处理
        if (a == b) edges[i] = {a, b, 0};
        else edges[i] = {a, b, w};
    }

    int ans = kruskal();

    if (ans == INF) puts("impossible");
    else cout << ans << endl;

    return 0;
}

基础数学¶

质数¶

试除法判定质数

C++
/*
试除法判定质数:

注意一处写法，在for-loop时:
1. i <= sqrt(x)
2. i * i <= x
3. i <= x/i    最推荐的写法!
*/

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

三种筛法筛出质数

C++
const int maxn = 1e6+10;

/*
质数筛:

1. 最简单的筛: 
    i从2开始枚举, 一直到n, 将i的倍数标记 (标记成合数)
2. 埃氏筛:
    使用质数来进行筛选: 从 2 开始，将每个质数的倍数都标记成合数
3. 线性筛:
    为确保每一个合数只被筛选一次，用每个合数的最小质因子来筛
*/

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

void get_primes(int n)
{
    // 最简单的筛法
    for (int i=2; i<=n; i++)
    {
        if (!st[i]) primes[cnt++] = i;

        for (int j = i+i; j<=n; j+=i)
            st[j] = true; // 将i的倍数标记
    }
}

void get_ai_primes(int n)
{
    for (int i=2; i<=n; i++)
    {
        if (st[i]) continue; // i是合数

        primes[cnt++] = i;

        for (int j=i+i; j<=n; j+=i) st[j] = true; // 质数的倍数
    }
}

void get_linear_primes(int n)
{
    for(int i=2; i<=n; i++)
    {
        if (!st[i]) primes[cnt++] = i; // i是质数

        for(int j=0; primes[j] <= n/i; j++)
        {
            // 枚举截至目前的质数, j是下标
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                // 保证所有数只被筛选一次, 避免重复晒选
                break;
            }
        }
    }
}

分解质因数 (算数基本定理)

C++
/*
算术基本定理:

(1) 定义:

每个大于1的自然数要么本身就是质数，
要么可以唯一表示为有限个质数的乘积

即: n = (P1^a1) * (P2^a2) * (P3^a3) ...

(2) 算法思路: 

最小质数2开始，依次用质数试除目标数，记录能整除的次数作为指数，
直到商为质数
*/

void prime_divide (int x)
{
    for (int i=2; i <= x/i; i++) {
        if (x % i == 0) // i是因数, 故是底数
        {
            int comp = 0; // comp是指数, 即: 这个数被除的次数
            while (x % i == 0)
            {
                x /= i;
                comp++;
            }
            cout << i << " " << comp << endl;
        }
    }

    if (x > 1) // 最后一个数，是质数
    {
        cout << x << " " << 1 << endl;
    }

    cout << endl; // 每个正整数的质因数全部输出完毕后，输出一个空行
}

约数¶

试除法求约数

C++
/*
试除法求约数:

从1开始遍历，约数 i && x/i 成对出现
*/

vector<int> get_divisors(int x)
{
    vector<int> ans;

    for (int i=1; i<=x/i; i++)
    {
        if (x % i == 0) {
            // 每次push进 i 和 x/i (二者成对出现)
            ans.push_back(i);
            if (i != x/i) ans.push_back(x/i);
        }
    }

    // 按照从小到大的顺序输出
    sort(ans.begin(), ans.end());
    return ans;
}

约数个数 + 约数之和

C++
/*
约数个数: 结论题
1. 先进行算术基本定理分解:
    n = (p1^a1) * (p2^a2) * (p3^a3) ... * (ak+1)
2. 约数个数:
    num = (a1+1) * (a2+1) * (a3+1) ... * (ak+1)
3. 约数之和:
    sum = (p1^0 + p1^1 + p1^2 + ... + p1^a1) *
          (p2^0 + p2^1 + p2^2 + ... + p2^a2) *
          (p3^0 + p3^1 + p3^2 + ... + p3^a3) *
          ...
          (pk^0 + pk^1 + pk^2 + ... + pk^ak)
*/

C++
#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;

typedef long long LL;
const int maxn = 110;
const int mod = 1e9+7;

/*
约数个数: 结论题

1. 先进行算术基本定理分解:
    n = (p1^a1) * (p2^a2) * (p3^a3) ... * (ak+1)
2. 约数个数:
    num = (a1+1) * (a2+1) * (a3+1) ... * (ak+1)
3. 约数之和:
    sum = (p1^0 + p1^1 + p1^2 + ... + p1^a1) *
          (p2^0 + p2^1 + p2^2 + ... + p2^a2) *
          (p3^0 + p3^1 + p3^2 + ... + p3^a3) *
          ...
          (pk^0 + pk^1 + pk^2 + ... + pk^ak)
*/

/*
处理算数基本定理时:
存储 底数p 和 指数a, 要用 mapping
1. map: 红黑树 O(logn)
2. unordered_map: 哈希表 O(1)
*/

int n;
unordered_map<int, int> primes;

void get_divide_res()
{
    // 经算数基本定理分解后
    // 得到: 底数p_i 与 指数a_i
    while (n--)
    {
        int x;
        cin >> x;

        for (int i=2; i<=x/i; i++)
        {
            while (x % i == 0) // i: 底数
            {
                x /= i;
                primes[i]++; // primes[i]: 指数
            }
        }

        if (x > 1) primes[x]++; // 最后一个质数
    }
}

int main()
{
    cin >> n;

    // 存储 底数p_i 与 指数a_i
    get_divide_res();

    LL ans = 1;
    for (auto p : primes) ans = ans * (p.second + 1) % mod;
    cout << ans << endl;

    return 0;
}

最大公约数

模板, 辗转相除法, gcd(a, b) = gcd(b, a%b)

C++
/*
最大公因数: 纯模板

gcd(a, b) = gcd(b, a%b)
*/

int n;

int gcd (int a, int b)
{
    return b ? gcd(b, a%b) : a;
}

int main()
{
    cin >> n;

    while (n--)
    {
        int a, b;
        cin >> a >> b;

        cout << gcd(a,b) << endl;
    }

    return 0;
}

欧拉函数¶

C++
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
/*
欧拉函数: 模板

1. 算术基本定理分解:
    N = (p1^a1) * (p2^a2) * ... * (pk^ak)
2. Phi(N):
    Phi(N) = N * (1 - 1/p1)
               * (1 - 1/p2)
                ...
               * (1 - 1/pk)
*/
int n;

LL phi (int x)
{
    // 将 phi 的计算直接放进算术基本定理的分解过程中
    LL ans = x;
    for (int i = 2; i <= x/i; i++)
    {
        if (x % i == 0)
        {
            ans = ans / i * (i-1); // 只需要底数进行计算
            while (x % i == 0) x /= i; // 将幂次消去
        }
    }

    if (x > 1) ans = ans / x * (x-1);

    return ans;
}

int main()
{
    cin >> n;

    while (n--)
    {
        LL x;
        cin >> x;
        cout << phi(x) << endl;
    }

    return 0;
}

快速幂¶

计算快速幂

C++
/*
快速幂:

def: a^b (mod p)
1. 计算快速幂
2. 利用快速幂求逆元

process in advance:
b = (2^x1) + (2^x2) + (2^x3) + ...
本质就是二进制分解
b: 10110010
b = 2^1 + 2^4 + 2^5 + 2^7
*/

int n;

LL qmi (LL a, LL b, LL p)
{
    LL ans = 1 % p; // 注意一定是1modp
    while (b)
    {
        if (b & 1) ans = ans * a % p; // res *= a^m
        a = a * a % p; // a^m -> a^2m
        b >>= 1;
    }

    return ans;
}

int main()
{
    cin >> n;

    while (n--)
    {
        LL a, b, p;
        cin >> a >> b >> p;
        cout << qmi(a, b, p) << endl;
    }

    return 0;
}

快速幂求乘法逆元

C++
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

/*
快速幂求乘法逆元:

def:
mod运算的逆元: a/b = a*x (mod p)
记: b = x^(-1)

motivation:
除法太慢，我们喜欢乘法替代品

principle:
b存在乘法逆元 <=> b 与 p 互质

cor:
当p是质数时, b^(p-2) 是 b 的逆元
*/

int n;

LL qmi (LL a, LL b, LL p)
{
    // a^b mod p 的模板
    LL ans = 1 % p;

    while (b)
    {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }

    return ans;
}

int main()
{
    cin >> n;

    while (n--)
    {
        LL a, p;
        cin >> a >> p;

        if (a % p == 0) {
            // a 与 p 不互质
            // 用 a%p 可判定是因为 p 是质数
            puts("impossible");
        }
        else {
            cout << qmi(a, p-2, p) << endl;
        }
    }

    return 0;
}

扩展欧几里得算法¶

C++
/*
扩展欧几里得算法:
求(x,y), s.t. ax+by=gcd(a,b)

有数学公式，见笔记

满足条件的元组有很多，只需要取其中一个即可
*/

int n;

LL exgcd (LL a, LL b, LL& x, LL& y)
{
    if (!b) {
        // ax + by = gcd 的解元组
        x=1;
        y=0;
        return a; // gcd = a
    }

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

    return d;
}

int main()
{
    cin >> n;

    while (n--)
    {
        LL a, b;
        cin >> a >> b;
        LL x, y;
        exgcd(a, b, x, y);
        cout << x << " " << y << endl;
    }

    return 0;
}

中国剩余定理¶

C++
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

/*
(x mod a_i) == (m_i mod a_i) 同余方程组

求解, 使用 "中国剩余定理":

x = x1 * M1 * M1^(-1) + 
    x2 * M2 * M2^(-1) +
    ...
    xk * Mk * Mk^(-1)

- M: m1 * m2 * m3 * ... * mk
- Mi: M / mi
*/

int n;

// 太难了，感觉机试不会考
LL exgcd (LL a, LL b, LL& x, LL& y)
{
    if (!b) {
        x=1;
        y=0;
        return a;
    }

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

int main()
{
    cin >> n;
    LL x=0, m1, a1;
    cin >> m1 >> a1;

    for (int i=0; i<n-1; i++)
    {
        LL m2, a2;
        cin >> m2 >> a2;

        LL k1, k2;
        LL d = exgcd(m1,m2,k1,k2);

        if ((a2 - a1) % d) {
            x = -1;
            break;
        }

        k1 *= (a2 - a1) / d;
        k1 = (k1 % (m2/d) + m2/d) % (m2/d);

        x = k1 * m1 + a1;

        LL m = abs(m1 / d * m2);
        a1 = k1 * m1 + a1;
        m1 = m;
    }

    if (x != -1) x = (a1 % m1 + m1) % m1;

    cout << x << endl;

    return 0;
}

高斯消元¶

矩阵求解，非常重要，纯模板

C++
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

/*
高斯消元解线性方程组: 纯模板，非常非常重要!
*/

const int N = 110;
const double eps = 1e-6;

int n;
double a[N][N];

int gauss()
{
    int c, r; // 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;

        // 如果当前这一列的最大数都是 0 ，那么所有数都是 0，就没必要去算了，因为它的约束方程，可能在上面几行
        if (fabs(a[t][c]) < eps) continue;

        // 把当前这一行，换到最上面（不是第1行，是第r行）去!
        for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]);
        // 把当前这一行的第一个数，变成 1，方程两边同时除以 第一个数
        // PS: 必须要倒着算，不然第一个数直接变1，系数就被篡改，后面的数字没法算
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];
        // 把当前列下面的所有数，全部消成 0
        for (int i = r + 1; i < n; i ++ )
            if (fabs(a[i][c]) > eps) // 如果非0就再操作，已经是0就没必要操作了
                for (int j = n; j >= c; j -- ) // 从后往前，当前行的每个数字，都减去对应列 * 行首非0的数字 进行消去
                    a[i][j] -= a[r][j] * a[i][c];

        r++ ; // 这一行的工作做完，换下一行
    }

    if (r < n) // 说明剩下方程的个数是小于n的，说明不是唯一解，现在需要判断是无解还是无穷多解
    {   // 因为已经是阶梯型，所以 r ~ n-1 的值应该都为 0
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps) // a[i][n] 代表 b_i ,即 左边=0，右边=b_i,0 != b_i, 所以无解
                return 2;
        return 1; // 否则，0 = 0，r ~ n-1的方程都是多余方程
    }
    // 唯一解 ↓，从下往上回代，得到方程的解
    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[j][n] * a[i][j]; //因为只要得到解，所以只用对 b_i 进行操作，中间值可以不用操作

    return 0;
}

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

    int t = gauss(); // gauss消元得到的结果

    if (t == 0)
    {
        for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");

    return 0;
}

求组合数¶

(1)

C++
/*
C (a,b) 在数据范围小的时候: 利用递推式预处理

C (a,b) = C (a-1,b) + C (a-1,b-1)
*/

void init()
{
    for (int i = 0; i < maxn; i++) {
        for (int j = 0; j <= i; j++) {
            if (!j) {
                c[i][j] = 1;
            }
            else {
                c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
            }
        }
    }
}

(2)

C++
/*
C (a,b) 在数据范围大的时候: 利用阶乘式部分预处理

C(a,b) = b! / (a! * (a-b)!)
       = fact[b] * infact[a] * infact[a-b]

- fact[x]: x!
- infact[x]: 1 / (x!)
*/

LL fact[maxn], infact[maxn];

LL qmi (LL a, LL b, LL p)
{
    LL ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

int main()
{
    // 初始起点: fact && infact
    fact[0] = infact[0] = 1;

    // 预处理 fact && infact
    for (int i=1; i<maxn; i++)
    {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
        // review: 1/x mod p 逆元 -> 使用快速幂qmi
        // 如果 p 是质数，则 x 的逆元是 x^(p-2)
        // proof: fermart principle
    }

    int n;
    cin >> n;

    while (n--)
    {
        int a, b;
        cin >> a >> b;
        cout << ( (fact[a] * infact[b] % mod) * infact[a-b] ) % mod << endl;
    }

    return 0;
}

(3)

C++
/*
求组合数: 数据范围巨大

采用卢卡斯定理: Cab = C(a%p)(b%p) * C(a/p)(b/p)

review: 求逆元, x mod p 的逆元 = x^(p-2) -- if p is a prime
*/

LL qmi(LL a, LL b, LL p)
{
    LL ans = 1 % p;
    while (b)
    {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

LL C(LL a, LL b, LL p)
{
    // 求 C[a][b] mod p
    // 之前我们用过 fact[a] * infact[b] * infact[a-b]
    // 这次我们换种方式:
    // a * (a-1) * (a-2) * ... * (a-b+1) / b!

    if (b > a) return 0;

    LL ans = 1 % p;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        ans = ans * j % p;
        ans = ans * qmi(i, p - 2, p) % p;
    }

    return ans;
}

LL lucas (LL a, LL b, LL p)
{
    // Lucas Principle 递推式
    if (a < p && b < p) return C(a, b, p);
    return C(a%p, b%p, p) * lucas(a/p, b/p, p) % p;
    /*
    为什么不用定理C(a,b)同余于C(a % p, b % p) * C(a / p, b / p),
    而是使用递归?

    因为C(a / p, b / p)不一定是a / p < p，b / p < p，
    可能还是一个很大的数，要继续套用卢卡斯定理求解
    */
}

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

    while (n--)
    {
        LL a, b, p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

动态规划¶

背包问题¶

0-1 背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次

C++
/*
0-1背包

f[i][j]: 只在前i个物品中选，且总体积不超过j的全部选法 -> 对应的总价值max

(1) 递推式

f[i][j] = max( f[i-1][j], f[i-1][j-v[i]] + w[i])

(2) 滚动数组优化

for i 1 : n
    for j v : v[i]
        f[j] = max (f[j], f[j-v[i]] + w[i])
*/

int v[maxn], w[maxn];
int N, V;
int f[maxn][maxn];

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

    // (1) 朴素递推式 写法
    for (int i=1; i<=N; i++)
    {
        for (int j=0; j<=V; j++)
        {
            // 只在前i个物品中选，且总体积不超过j
            f[i][j] = f[i-1][j];
            if (j - v[i] >= 0)
                f[i][j] = max( f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    }

    cout << f[N][V] << endl;

    return 0;
}

滚动数组优化

C++
// (2) 滚动数组优化 写法
for (int i=1; i<=N; i++) {
    for (int j=V; j>=v[i]; j--) {
        // 只在前i个物品中选，且总体积不超过j
        f[j] = max(f[j], f[j-v[i]] + w[i]);
    }
}

完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用

C++
/*
完全背包

f[i][j]: 只在前i种物品中选，总体积不超过j的选法 -> 对应的总价值max

f[i][j] = max (
        f[i-1][j],
        f[i-1][j-v[i]] + w[i],
        f[i-1][j-2*v[i]] + 2*w[i],
        ...
        f[i-1][j-k*v[i]] + k*w[i]
        ...
    )

(1) 递推式 -- 3-for-loop

for i 1:n
    for j 0:v
        for k=0; k*v[i]<=j; k++
            f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
会TLE, 遂不写了

(2) 优化递推式 -- 2-for-loop

f[i][j] = max( f[i-1][j], f[i][j-v[i]] + w[i]);

(2) 滚动数组优化 -- 2-for-loop

for i 1:n
    for j v[i]:v
        f[j] = max( f[j], f[j-v[i]] + w[i]);
*/

const int maxn = 1010;
int N, V;
int v[maxn], w[maxn];
int f[maxn][maxn];

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

    // (2) 优化递推式 写法
    for (int i=1; i<=N; i++)
    {
        for (int j=0; j<=V; j++)
        {
            // 只在前i种物品中选，总体积不超过j的选法
            f[i][j] = f[i-1][j];
            if (j - v[i] >= 0)
                f[i][j] = max( f[i][j], f[i][j-v[i]] + w[i]);
        }
    }

    cout << f[N][V] << endl;   
    return 0;
}

多重背包

有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 \(s_i\) 件

C++
/*
多重背包

f[i][j]: 只在前i种物品中选，总体积不超过j的选法 -> 对应的总价值max

(1) 朴素递推式

for (int k = 0; k<=s[i] && j>=k*v[i]; k ++) // 枚举这一种选?个
    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

这里无法像之前完全背包一样“优化递推式”了，因为不是无穷多项

(2) 二进制优化
*/

int v[maxn], w[maxn], s[maxn];
int f[maxn][maxn];
int N, V;

int main()
{
    cin >> N >> V;
    for(int i=1; i<=N; i++) cin >> v[i] >> w[i] >> s[i];

    for (int i=1; i<=N; i++) // 枚举背包
    {
        for (int j=1; j<=V; j++) // 枚举体积
        {
            for (int k = 0; k<=s[i] && j>=k*v[i]; k ++)
            {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }

    cout << f[N][V] << endl;
    return 0;
}

二进制优化

C++
/*
多重背包

f[i][j]: 只在前i种物品中选，总体积不超过j的选法 -> 对应的总价值max

(1) 朴素递推式

for (int k = 0; k<=s[i] && j>=k*v[i]; k ++) // 枚举这一种选?个
    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

这里无法像之前完全背包一样“优化递推式”了，因为不是无穷多项

(2) 二进制优化
① 假定物品件数s=200
② 二进制形式k[n]={1,2,4,8,16,32,64,73}  其所有值相加是<=200  可以凑出[0~200]的所有数
③ 除开最后一个数不是二进制形式，73=200-(1+2+4+8+16+31+64)
④ 其余数，若定64，其中64+[0~63]->[0~127]
⑤ 最后一个数73，其中73+[0~127]->[0~200]
*/

const int N = 12010, M = 2010;
// 这里的箱子也就是二进制优化下的s[i]
// 由题 s[i]<=2000 则log2000 < 12 一共最多1000件物品，则我们需要开的范围就是 12*1000+10=12010
int v[N], w[N];
int f[M];

int main()
{
    int n, m;
    cin >> n >> m;
    int cnt = 0; // 重新定义存储物品的编号

    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1; // 定义箱子可以放物品的初始值 第一个箱子可以放一个i号物品

        while (k <= s)
        {
            cnt ++ ; //编号增加 可以看成是每一个箱子的编号
            v[cnt] = a * k; // 该箱子可以存的i号物品总体积
            w[cnt] = b * k; // 该箱子可以存的i号物品总价值
            s -= k;
            k *= 2; // 二进制优化 下一个箱子可以放的物品数量是上一个的两倍
        }

        // 如果物品i还没有被二进制箱子存完,
        // 再开一个可以存还剩下的所有物品i的箱子
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt; // 关键一步！将物品编号更改为所有物品在箱子里装完后箱子的编号

    // 上面结束后 我们将物品全部装进了箱子 我们不管想在背包里装多少个物品i，都可以装箱子的方式实现 
    // 例如要装7个物品i 我们就用物品i的1号 2号 3号箱子 (1号能装1个i 2号能装2个i 3号能装4个i) 
    // 这就是我们使用二进制优化的意义，能将所有需要的物品数量表示出来
    // 由于所有需要的物品数量都能用不同箱子的组合表达 所以现在每个箱子的状态只能是 用或者不用 
    // 从而转化为01背包问题

    //对照01背包代码
    for (int i = 1; i <= n; i ++ ) // 注意n已经被cnt重新赋值
        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;
}

分组背包

有 N 组物品和一个容量是 V 的背包。每组物品有若干个，同一组内的物品最多只能选一个

C++
/*
分组背包:

f[i][j]: 只在前i组物品中选，总体积不超过j的选法 -> 对应的总价值max

递推式:

f[i][j] = max (
        f[i-1][j],
        ...
        f[i-1][j-v[i,k]] + w[i,k]
    )

遍历考察第i组选择第k个物件的情况
*/

const int maxn = 110;

int v[maxn][maxn], w[maxn][maxn];
int s[maxn];
int f[maxn][maxn];
int N, V;

int main()
{
    cin >> N >> V;
    for (int i=1; i<=N; i++) // 组
    {
        cin >> s[i];
        // 组内件
        for (int j=1; j<=s[i]; j++) cin >> v[i][j] >> w[i][j];
    }

    // // 初始化f[0][j]为0
    // for (int j=0; j<=V; j++) f[0][j] = 0;

    for (int i=1; i<=N; i++)
    {
        for (int j=0; j<=V; j++)
        {
            f[i][j] = f[i-1][j];
            for (int k=1; k<=s[i]; k++)
            {
                if (j - v[i][k] >= 0) // 注意这里的下标是v[i][k]
                    f[i][j] = max(f[i][j], f[i-1][j-v[i][k]] + w[i][k]);
            }
        }
    }

    cout << f[N][V] << endl;
    return 0;
}

线性DP¶

最长上升子序列

f[i]: 以第i个数字结尾的上升子序列

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

    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1; // 只有a[i]一个数
        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 = 1; i <= n; i ++ ) res = max(res, f[i]);

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

    return 0;
}

最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少

f[i][j]: 所有由第一个序列的前i个字母和第二个序列的前j个字母构成的公共子序列

C++
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);
    }

    printf("%d\n", f[n][m]);

区间DP¶

f[i][j]: 所有将第i堆到第j堆合并成一堆的方式

C++
int n;
int s[N];
int f[N][N];

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

    // 前缀和预处理: sigma(i ~ j)
    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 ++ )
                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]);
    return 0;
}

数位统计DP¶

计数问题: 给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数

C++
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

/*

001~abc-1, 999

abc
    1. num[i] < x, 0
    2. num[i] == x, 0~efg
    3. num[i] > x, 0~999

*/

int get(vector<int> num, int l, int r)
{
    int res = 0;
    for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
    return res;
}

int power10(int x)
{
    int res = 1;
    while (x -- ) res *= 10;
    return res;
}

int count(int n, int x)
{
    if (!n) return 0;

    vector<int> 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)
        {
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x) res -= power10(i);
        }

        if (num[i] == x) res += get(num, i - 1, 0) + 1;
        else if (num[i] > x) res += power10(i);
    }

    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¶

C++
// 这种结构常用于处理一系列输入数据对，其中输入以一对 0 0 作为结束标记（哨兵值）
while (cin >> n >> m, n || m){
    ......
}

蒙德里安的梦想: 铺地砖

C++
int n, m;
long long f[N][M];
bool st[M];

int main()
{
    while (cin >> n >> m, n || m)
    {
        for (int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1)
                {
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else cnt ++ ;
            if (cnt & 1) st[i] = false;
        }

        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ ) // 0-1串, 状压
                for (int k = 0; k < 1 << n; k ++ )
                    if ((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];

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

最短Hamilton路径:

C++
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20, M = 1 << N;

int n;
int w[N][N];
int f[M][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;

    for (int i = 0; i < 1 << n; i ++ ) // 0-1串, 状压
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1) // i串的第j位是1, 串终点是j
                for (int k = 0; k < n; k ++ )
                    if (i >> k & 1) // i串的第k位是1, k是“路径上某点”
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

    cout << f[(1 << n) - 1][n - 1];

    return 0;
}

树形DP¶

C++
int n;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

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

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);

        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}

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

    for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]);

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

    int root = 1;
    while (has_fa[root]) root ++ ;

    dfs(root);

    printf("%d\n", max(f[root][0], f[root][1]));

    return 0;
}

记忆化搜索¶

核心: 搜索是函数, 存储每个结果用的还是数组

每次搜索时, 如果当前 dfs(i,j) 已经有对应的 f[i][j] 了, 就直接 return f[i][j]. 反之再进行搜索处理

C++
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 310;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int a[maxn][maxn]; // 地形
int f[maxn][maxn]; // f[i][j]表示从(i,j)出发的最大值
int r, c;

int dp(int x, int y)
{
    // 出口
    if (f[x][y] != -1) return f[x][y]; // 记忆化搜索

    f[x][y] = 1; //当前点即使啥也不干, path长度也至少是1
    for (int i=0; i<4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx < 1 || xx > r || yy < 1 || yy > c) continue; // 边界

        if (a[xx][yy] < a[x][y]) {
            f[x][y] = max(f[x][y], dp(xx, yy) + 1);
        }
    }

    return f[x][y];
}

int main()
{
    cin >> r >> c;
    memset(f, -1, sizeof(f));
    for (int i=1; i<=r; i++) {
        for (int j=1; j<=c; j++) {
            cin >> a[i][j];
        }
    }

    int res = 0xc0c0c0c0;
    for (int i=1; i<=r; i++) {
        for (int j=1; j<=c; j++) {
            // cout << dp(i, j) << " ";
            res = max(res, dp(i,j));
        }
        // puts("");
    }

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

贪心算法¶

这一部分的重点是多见题型, 不要想着考试推什么“循环不变式”之类的...

区间问题¶

区间选点

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点

区间右端点排序

C++
int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {//区间右端点排序
        return r < W.r;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

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

    return 0;
}

最大不相交区间数量

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。输出可选取区间的最大数量

区间右端点排序

C++
int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {//区间右端点排序
        return r < W.r;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
        if (ed < range[i].l)
        {
            res ++ ;
            ed = range[i].r;
        }

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

    return 0;
}

区间分组

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小

区间左端点排序

C++
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {// 区间左端点排序
        return l < W.l;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, 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);
        }
        else { // "组右端点" < "当前区间左端点", 区间另立新组
            heap.pop();
            heap.push(r.r);
        }
    }

    printf("%d\n", heap.size());

    return 0;
}

区间覆盖

给定 N 个区间 [ai,bi] 以及一个区间 [s,t]，请你选择尽量少的区间，将指定区间完全覆盖。输出最少区间数，如果无法完全覆盖则输出 −1

左端点排序

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

int main()
{
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ )
    {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j ++ ;
        }

        if (r < st)
        {
            res = -1;
            break;
        }

        res ++ ;
        if (r >= ed)
        {
            success = true;
            break;
        }

        st = r;
        i = j - 1;
    }

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

    return 0;
}

Huffman 树¶

C++
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

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

    // 小根堆
    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);
    return 0;
}

排序不等式¶

排队打水: 费时越多者, 排到越后面

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

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

    return 0;
}

绝对值不等式¶

货仓选址: 选“中点”

C++
const int N = 100010;

int n;
int q[N];

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

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

    sort(q, q + n);

    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(q[i] - q[n / 2]);

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

    return 0;
}

推公式¶

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