算法基础

ASCII码表

常用模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//万能
#include <bits/stdc++.h> //C++

#include <algorithm>>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
using namespace std;
#define int long long
void solve()
{

}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

读入优化

1
2
std::ios::sync_with_stdio(0);
std::cin.tie(0);

读入方式

当未知要读入几组数据时可以用while(scanf("%d%d", &n, &m) != -1)

离散化

1
2
3
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//unique会将不重复的元素放在前面，重复的元素放在后面，并且返回第一个不重复元素的位置

double的inf

1
2
#include <limits>
double inf = std::numeric_limits<double>::infinity();

STL

lower_bound

（左边界取等）

在从小到大排序的数组中：lower_bound(begin, end, num)

从数组的begin位置到end - 1位置二分查找第一个\(\color{red}{大于或等于}\)num的数，找到返回该数的地址，不存在返回end；通过返回的地址减去begin，得到数字在数组中的下标

在从大到小排序的数组中：lower_bound(begin ,end, num, greater())

从数组的begin位置到end - 1位置二分查找第一个\(\color{red}{小于或等于}\)num的数

upper_bound

在从小到大排序的数组中：upper_bound(begin, end, num)

从数组的begin位置到end - 1位置二分查找第一个\(\color{red}{大于}\)num的数，找到返回该数的地址，不存在返回end；通过返回的地址减去begin，得到数字在数组中的下标

在从大到小排序的数组中：upper_bound(begin ,end, num, greater())

从数组的begin位置到end - 1位置二分查找第一个\(\color{red}{小于}\)num的数

vector

操作：

  • push_back()
  • pop_back()
  • size()
  • clear()
  • insert()
  • erase()
    • erase(_position) --删除某个元素
    • erase(position_start, position_end)--删除区间\([position\_start,position\_end)\)内的元素

set

特点：

  1. set的含义是集合，所有操作都在\(O(logn)\)的时间复杂度内完成
  2. set插入的元素不能相同
  3. 所有元素会根据值排序（默认是从小到大），set<int, greater<int>>就是从大到小
  4. set中元素的值不能被直接修改
  5. set不支持下标访问操作，只支持迭代器
  6. 模版：set s;

操作：

  • begin()--返回指向第一个元素的迭代器
  • end()--返回指向最后一个元素的迭代器
  • clear()
  • empty() --如果集合为空，返回true，否则返回false
  • erase()
  • count()
  • find(k)
  • insert()/emplace()
  • lower_bound(k) -- 返回一个迭代器，指向键值大于等于k的第一个元素
  • upper_bound(k) --返回一个迭代器，指向键值大于k的第一个元素
  • size()

queue

操作：

  • 模板：queue<数据类型，容器类型> q
  • push()
  • pop()
  • size()
  • front()--返回队首
  • back()--返回队尾
  • empty()

priority_queue

特点：

  1. 包含头文件\(\verb|#include <queue>|\)​
  2. 默认从大到小排序（less 从大到小，greater 从小到大）

操作：

  • push()
  • pop()
  • empty()
  • top()
  • size()

map

特点：

  1. 使用头文件\(\verb|#include <map>|\)

  2. 具有唯一键值对

  3. 模版：map<key_type, value_type>变量名

  4. 可以保证元素的有序性，默认按照键（key）从小到大排序

    如果想从大到小排序：\(\verb|map<string, int, greater<string> > m;|\)

操作：

  • size()
  • count()
  • empty()
  • erase()
  • clear()
  • find()
  • insert()
  • begin()
  • end()
  • lower_bound()
  • upper_bound()

unordered_map

特点：

  1. 快速查找特定元素
  2. 存储时元素是无序的
  3. 头文件\(\verb|#include <unordered_map>|\)

操作：

  • 插入：insert({key, value})/map[key] = value
  • 删除：clear()/erase()
  • 迭代器：begin()/end()
  • 元素个数：size()/count()

pair

1
2
3
typedef pair<int, int> PII;
vector<PII> a;
int l = a[0].first, int r = a[0].second;//注意！！！是first和second

multiset

multiset是\(<set>\)库中一个非常有用的类型，它可以看成一个序列，插入一个数，删除一个数都能够在\(O(logn)\)的时间内完成，而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//找到k的左边界，找大于等于k的第一个元素
int dic_left(int k)
{
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(a[mid] < k) l = mid + 1;
        else r = mid;
    }
    return l;
}
//找到k的右边界，找到小于等于k的第一个元素
int dic_right(int k)
{
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(a[mid] > k) r = mid - 1;
        else l = mid;
    }
    return l;
}

前缀和

一维前缀和：

s[i] = s[i - 1] + a[i]

数列a中任意\(\text\ [l, r]\)的和为s[r] - s[l - 1]

二维前缀和：

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

求以\(\text\ (x1, y1)\)为左上角，\(\text\ (x2, y2)\)为右下角的子矩阵元素和s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

差分

差分序列的前缀和序列就是原序列，利用差分数组将“区间操作”变成“单点操作”

一维差分数组：

dp[i] = a[i] - a[i - 1]

把a数组的[l, r]上的每个数加上c，则dp[l] += c, dp[r + 1] -= c;

对差分数组求前缀和a[i] = dp[i] + a[i - 1]

二维差分数组：

dp[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]

把矩阵中左上角为\(\text\ a[x1][y1]\)右下角为\(\text\ a[x2][y2]\)的小矩形中每个元素加上c，则

1
2
3
4
dp[x1][y1] += c;
dp[x1][y2 + 1] -= c;
dp[x2 + 1][y1] -= c;
dp[x2 + 1][y2 + 1] += c;

对差分矩阵求前缀和得原矩阵

即a[i][j] = dp[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

位运算

二进制状态压缩

&
1
2
3
4
5
6
7
8
9
10
11
12

![](https://raw.githubusercontent.com/LUCKYCYYYY/PictureBed/master/img/202406301623301.png)

### 位运算交换两数

```c++
void swap(int& a, int &b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

lowbit运算

lowbit(n)运算表示非负整数n在二进制表示下“最低位的1和其后所有的0”所构成的数值lowbit(n) = n & (~n + 1) = n & (-n)

数据结构

单调栈

寻找某个数左边第一个小于它的数

维护一个栈，栈顶元素即是当前准备入栈元素的左边第一个小于它的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int st[N], tt = 0;
int main()
{
    int n;  cin >> n;
    while(n--)
    {
        int x;  cin >> x;
        while(tt && st[tt] >= x) tt--;//如果栈不为空，并且栈顶元素比当前元素大，就出栈
        if(!tt) cout << -1 << " ";
        else cout << st[tt] << " ";
        st[++tt] = x;//当前元素入栈，先++，保证tt==0的时候栈为空
    }
    return 0;
}

单调队列

滑动窗口：找区间最大值和最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N], a[N];//q是队列，a是存储数据的数组
int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    //最小值
    int hh = 0, tt = -1;
    for(int i = 0; i < n; i++)
    {
        //判断需不需要让窗口往后移
        if(hh <= tt && i - k + 1 > q[hh]) ++hh;
        //因为是找最小值，所以如果新出现的元素比左边的元素小，那么在窗口右移的过程中，左边的那个更大的元素必定用不到，所以删去
        while(hh <= tt && a[i] <= a[q[tt]]) --tt;
        q[++tt] = i;//将新元素加进队列
        //整个队列单调增，所以hh位置元素最小
        if(i >= k - 1) cout << a[q[hh]] << " ";
    }
    cout << '\n';
    
    //最大值
    hh = 0, tt = -1;
    for(int i = 0; i < n; i++)
    {
        //如果当前队列中的元素个数大于k，需要队首出队
        if(hh <= tt && i - k + 1 > q[hh]) ++hh;
        //因为找最大值，所以如果新出现元素更大，同上，删去左边的元素
        while(hh <= tt && a[i] >= a[q[tt]]) --tt;
        q[++tt] = i;//在队列里面存下标
        //整个队列单调减，hh位置元素最大
        if(i >= k - 1) cout << a[q[hh]] << " ";
    }
    return 0;
}

并查集

1
2
3
4
5
6
for(int i = 1; i <= n; i++) p[i] = i;//初始化自己的根节点是自己
int find(int x)//寻找根节点
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

树状数组

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct Node
{
    int l, r;
    int v;
}tree[N * 4];
void build(int u, int l, int r)
{
    tree[u] = {l,r};
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int x, int v)//修改一个节点的数
{
    if(tree[u].l == x && tree[u].r == x)
    {
        tree[u].v = v;
        return;
    }
    int mid = (tree[u].l + tree[u].r) >> 1;
    if(x <= mid) modify(u << 1, x, v);
    else modify(u << 1 | 1, x, v);
    tree[u].v = max(tree[u << 1].v, tree[u << 1 | 1].v);//根据所求设定修改条件
}
int query(int u, int l, int r)//求数列最后L个数的最大值
{
    if(l <= tree[u].l && r >= tree[u].r) return tree[u].v;
    int mid = (tree[u].l + tree[u].r) >> 1;
    int v = 0;
    if(l <= mid) v = query(u << 1, l, r);
    if(r > mid) v = max(v, query(u << 1 | 1, l, r));
    return v;
}

带懒标记的线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct Node
{
    int l, r;
    int sum, tag;
}tree[N * 4];
void pushup(int u)
{
    tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum; 
}
void pushdown(int u)
{
    Node& root = tree[u], & left = tree[u << 1], & right = tree[u << 1 | 1];
    if(root.tag)
    {
        left.tag += root.tag, left.sum += (left.r - left.l + 1) * root.tag;
        right.tag += root.tag, right.sum += (right.r - right.l + 1) * root.tag;
        root.tag = 0;
    }
}
void build(int u, int l, int r)
{
    if(l == r) 
    {
        tree[u] = {l, r, a[l], 0};
        return;
    }
    tree[u] = {l, r};
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void modify(int u, int l, int r, int v)
{
    if(tree[u].l >= l && tree[u].r <= r)
    {
        tree[u].sum += (tree[u].r - tree[u].l + 1) * v;
        tree[u].tag += v;
    }
    else
    {
        pushdown(u);
        int mid = (tree[u].l + tree[u].r) >> 1;
        if(l <= mid) modify(u << 1, l, r, v);
        if(r > mid) modify(u << 1 | 1, l, r, v);
        pushup(u);
    }
}
int query(int u, int l, int r)
{
    if(tree[u]. l >= l && tree[u].r <= r) 
    {
        return tree[u].sum;
    }
    pushdown(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    int s = 0;
    if(l <= mid) s = query(u << 1, l, r);
    if(r > mid) s += query(u << 1 | 1, l, r);
    return s;
}

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstring>
using namespace std;
#define int unsigned long long
const int P = 131, N = 1e5 + 10;
int h[N], p[N];
int query(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
signed main()
{
    int n, m;
    cin >> n >> m;
    string x;
    cin >> x;//从0开始
    p[0] = 1;
    for(int i = 0; i < n; i++)
    {
        p[i + 1] = p[i] * P;
        h[i + 1] = h[i] * P + x[i];
    }
    while(m--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(query(l1, r1) == query(l2, r2)) cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }
    return 0;
}

Trie字符串统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], cnt[N], idx;
void Insert(string s)
{
    int p = 0;
    for(int i = 0;s[i]; i++)
    {
        int u = s[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}
int Query(string s)
{
    int p = 0;
    for(int i = 0; s[i]; i++)
    {
        int u = s[i] - 'a';
        if(son[p][u]) p = son[p][u];
        else return 0;
    }
    return cnt[p];
}
int main()
{
    int n;  cin >> n;
    while(n--)
    {
        char op; cin >> op;
        string s; cin >> s;
        if(op == 'I')
        {
            Insert(s);
        }
        else
        {
            cout << Query(s) << '\n';
        }
    }
    return 0;
}

最大异或对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 31 * N;
int son[M][2], idx;
int a[N];
void Insert(int a)
{
    int p = 0;
    for(int i = 30; i >= 0; i--)
    {
        int u = a >> i & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
int search(int a)
{
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i--)
    {
        int u = a >> i & 1;
        if(son[p][!u])
        {
            p = son[p][!u];
            res = res * 2 + 1;
        }
        else
        {
            p = son[p][u];
            res = res * 2 + 0;
        }
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        Insert(a[i]);
    }
    int res = 0;
    for(int i = 0; i < n; i++)
        res = max(res, search(a[i]));
    cout << res;
    return 0;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
char p[N], s[M];
int ne[N];
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    for(int i = 0, j = 2; j <= n; j++)//计算next数组
    {
        while(i && p[i + 1] != p[j]) i = ne[i];
        if(p[i + 1] == p[j]) i++;
        ne[j] = i;
    }
    for(int i = 0, j = 1; j <= m; j++)
    {
        while(i && p[i + 1] != s[j]) i = ne[i];
        if(p[i + 1] == s[j]) i++;
        if(i == n)
        {
            cout << j - n << " ";
            i = ne[i];
        }
    }
    return 0;
}

AC自动机

KMP：以\(O(n)\)判断一个单词在文章中出现的次数和具体的位置

Trie：计算一个单词出现的次数

AC自动机：以\(O(n)\)判断多个单词是否在文章中出现

计算一篇文章中出现了多少个列举的单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10, M = 1e6 + 10, S = 55;
int n;
int tr[N * S][26], cnt[N * S], idx;
char str[M];
int q[N * S], ne[N * S];
void insert()//创建trie树
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int t = str[i] - 'a';
        if(!tr[p][t]) tr[p][t] = ++idx;
        p = tr[p][t];
    }
    cnt[p]++;
}
void build()
{
    int hh = 0, tt = -1;
    for(int i = 0; i < 26; i++)//因为根节点以及第一层的节点都是直接指向根节点，所以直接从第一层进行遍历即可
    {
        if(tr[0][i]) q[++tt] = tr[0][i];
    }
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = 0; i < 26; i++)
        {
            int p = tr[t][i];
            if(!p)//如果没有找到儿子节点，那么父节点对应的next指针就是要跳到的位置
                tr[t][i] = tr[ne[t]][i];
            else //如果存在儿子节点，那么这个节点的父亲节点的next指针对应的儿子节点字母i就是该儿子的next指针指向的位置
            {
                ne[p] = tr[ne[t]][i];
                q[++tt] = p;
            }
        }
        
    }
}
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            cin >> str;
            insert();
        }
        build();
        cin >> str;//文章
        int res = 0;
        for(int i = 0, j = 0; str[i]; i++)
        {
            int t = str[i] - 'a';
            j = tr[j][t];
            int p = j;
            while(p)//因为如果p出现了，那么以p为前缀的单词一定也出现了，所以要不断更新为next指针
            //遍历到she的后缀he的时候 her的相同前缀he肯定是逐层遍历到了的 len(he)<len(she) 逐层遍历
            //把所有ne 指针全部加一遍  比如当前p到了she的e  把cnt[p]+进res后 
            //把p通过ne[p]跳到he的e 再加上此时指向he中e的p的cnt[p] 
            {
                res += cnt[p];
                cnt[p] = 0;//因为只记录是否出现过不记录个数，所以置为0
                p= ne[p];
            }
        }
        cout << res <<'\n';
    }
    return 0;
}

图论

DFS和BFS

DFS

dfs重点在递归，每次递归需要考虑递归传递的参数、结束条件，并且要及时“还原”改变的参数

全排列

  1. 递归传递的参数：表示当前答案中有多少个数字
  2. 递归结束的条件：当前答案中的数字达到n
  3. 递归的过程：设置st数组，判断该数字是否被使用过；每次递归后需还原st的状态

全排列的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int x)//递归的参数
{
    if(x > n)//结束条件
    {
        for(int i = 1; i <= n; i++) cout << res[i] << " ";
        cout << '\n';
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!st[i])
        {
            res[x] = i;
            st[i] = true;
            dfs(x + 1);
            st[i] = false;
        }
    }
}

n皇后

  1. 递归传递的参数：表示当前放到了第几行
  2. 递归结束的条件：遍历到了最后一行
  3. 递归的过程：每一行利用for循环遍历每一列，每次递归后“还原”place以及行列斜的状态数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;
const int N = 20;
char place[N][N];
bool row[N], col[N], dg[N], udg[N];
int n;
void dfs(int x)//遍历x行
{
    if(x == n)//结束条件
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                cout << place[i][j];
            }
            cout << '\n';
        }
        cout << '\n';
        return;
    }
    for(int y = 0; y < n; y++)//遍历列
    {
        if(!row[x] && !col[y] && !dg[x + y] && !udg[y - x + n])
        {
            row[x] = col[y] = dg[x + y] = udg[y - x + n] = true;
            place[x][y] = 'Q';
            dfs(x + 1);
            row[x] = col[y] = dg[x + y] = udg[y - x + n] = false;
            place[x][y] = '.';
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) 
            place[i][j] = '.';
    dfs(0);
    return 0;
}

BFS

BFS即每次往”外“走一圈，利用队列模拟，每次出队时让与之相连的结点加入队列；单独设置一个“数组”，用来更新距离，并充当标记数组

走迷宫

  1. 设置方向数组dx，dy，方便“行走”
  2. 注意d数组，不仅充当表示距离的作用，也用来标记该点是否加入过队列中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int bfs()
{
    memset(d, -1, sizeof d);
    q.push({0, 0});
    d[0][0] = 0;
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        int a = t.first, b = t.second;
        for(int i = 0; i < 4; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && road[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[a][b] + 1;
                q.push({x, y});
            }
        }
    }
    return d[n - 1][m - 1];
}

最短路问题

图的宽度优先搜索

与上题的bfs类似，只是存图的方式变成了链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int head[N], to[N], ne[N], idx;
int n, m;
int d[N];
queue<int> q;
void add(int x, int y)
{
    to[idx] = y, ne[idx] = head[x], head[x] = idx++;
}
int bfs()
{
    q.push(1);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = head[t]; i != -1; i = ne[i])
        {
            int j = to[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    return d[n];
}
int main()
{
    memset(head, -1, sizeof head);
    memset(d, -1, sizeof d);
    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    d[1] = 0;c++
    cout << bfs();
    return 0;
}

Dijkstra算法

\(\color{blue}（不能存在负权边）\)

  • 朴素版本 ：时间复杂度 \(O(n^2)\)，适合稠密图（利用邻接矩阵存储）
    1. 将起点距离初始化为0，其他点的初始距离设置为无穷
    2. 每次找到距离起点距离最近的节点，将该点做标记，表示已经设置过
    3. 更新与该点有关的结点的距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
const int M = 1e5 + 10;
int n, m;
int g[N][N];
bool st[N];
int dist[N];
int dijkstra()
{
    dist[1] = 0;
    for(int i = 1; i <= n - 1; i++)//循环n-1次（除了开始的结点），每次都找到到某一个点的最短路径
    {
        int t = -1;//寻找当前还未找的结点距离起点的最短路
        for(int j = 1; j <= n; j++)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
            //找到一个距离起点更小的未被标记过的结点，就让t等于那个结点
        }
        st[t] = true;//设置标记表示已经找到最小距离了
        for(int j = 1; j <= n; j++)//更新与该结点有关结点的最小距离
        {
            if(dist[j] > dist[t] + g[t][j]) dist[j] = dist[t] + g[t][j];
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
int main()
{
    cin >> n >> m;//n个结点m条边
    memset(g,  0x3f3f, sizeof(g));
    memset(dist, 0x3f3f, sizeof dist);//初始化距离为无穷大
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);//利用邻接矩阵进行存储，因为有重边所以取min
    }
    cout << dijkstra();
}
  • 利用堆排序优化：时间复杂度\(O(mlogn)\)，适合稀疏图（利用邻接表存储）\({\color{red}(除了找最小距离的时候利用堆优化，其他与朴素算法一致)}\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 5e4 + 10;
int head[N], e[N], ne[N], w[N],idx;//利用链式前向星存储
int dist[N];
bool st[N];
int n, m;

typedef pair<int, int> PII;//一个用来存距离，一个用来存结点
//只能将距离存在前面，因为要根据距离排序
priority_queue<PII,vector<PII>, greater<PII>> heap;

void add(int x, int y, int z)//存图
{
    w[idx] = z;
    e[idx] = y;
    ne[idx] = head[x];
    head[x] = idx++;
}
int dijsktra()
{
    memset(dist, 0x3f3f, sizeof dist);
    dist[1] = 0;
    heap.push({0, 1});
    while(heap.size())
    {
        PII q = heap.top();//取堆顶元素
        int a = q.second, b = q.first;//a是路径的尾节点，b是这条路径的长度
        heap.pop();//删除刚刚用过的堆顶元素
        if(st[a]) continue;
        st[a] = true;
        for(int i = head[a]; i != -1; i = ne[i])//遍历
        {
            int j = e[i];
            if(dist[j] > dist[a] + w[i]) 
            {
                dist[j] = dist[a] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m;
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    cout << dijsktra();
    return 0;
}

BellmanFord算法

求出从 1号点到 n号点的最多经过 k 条边的最短距离

可以处理负边权回路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int dist[N], cpy[N];//一个同来记录最短距离，一个同来当做临时拷贝，防止出现连续更新的情况，因为该算法要保证循环k次只能走k条边，所以每次只能更新一条边的距离，如果只有一个dist就会出现，先用a更新b，再用b更新c的情况，导致循环k次只能走k条边条件不满足。
struct Edge
{
    int a, b, w;
}edges[M];

void BellmanFord()
{
    memset(dist, 0x3f3f, sizeof dist);
    dist[1] = 0;//设置初始距离
    for(int i = 0; i < k; i++)
    {
        memcpy(cpy, dist, sizeof dist);//拷贝
        for(int j = 0; j < m; j++)
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], cpy[e.a] + e.w);//用上一次循环的距离cpy更新这一次的距离
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    int x, y, z;
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y >> z;
        edges[i].a = x, edges[i].b = y, edges[i].w = z;
    }
    BellmanFord();
    if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");//因为可能存在负边所以是0x3f3f3f3f / 2
    else cout << dist[n];
    return 0;
}

Spfa算法

类似于宽搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;//建立队列，保证每次更新的前一个结点是更新的
    q.push(1);
    st[1] = true;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;//出队列 队列中无该结点 设置为false
        for(int i = head[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])//没有才加到队列里
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

spfa判断负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 2010,M = 10010;
int to[M], ne[M], w[M], head[N], idx;
bool st[N];
int dist[N], cnt[N];
int n, m;
void add(int x, int y, int z)
{
    to[idx] = y, ne[idx] = head[x], w[idx] = z, head[x] = idx++;
}
bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    for(int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = head[t]; i != -1; i = ne[i])
        {
            int j = to[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;
                if(!st[j]) 
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m;
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    if(spfa()) cout << "Yes";
    else cout << "No";
    return 0;
}

Floyd算法（多源最短路）

将所有情况一一列出来

1
2
3
4
5
6
7
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]);
}

拓扑排序

每次找到度为0的节点加入到最终的序列中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int head[N], e[N], ne[N], idx;
int d[N];
int q[N];
int n, m;

void add(int x, int y)
{
    e[idx] = y;
    ne[idx] = head[x];
    head[x] = idx++;
}

bool TopSort()
{
    int hh = 0, tt = 0;
    for(int i = 1; i <= n; i++)
        if(!d[i]) q[tt++] = i;//先找到一开始度为0的结点
    while(hh <= tt)
    {
        int t = q[hh++];//删除t结点
        for(int i = head[t]; i != -1; i = ne[i])//更改与t结点有关的边的度数
        {
            int j = e[i];
            if(--d[j] == 0) q[tt++] = j;//如果度为0就加入序列
        }
    }
    return tt == n;
}
int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    while(m--)
    {
        int x, y;
        cin >> x >> y;
        d[y]++;
        add(x, y);
    }//存图
    if(TopSort())
    {
        for(int i = 0; i < n; i++) cout << q[i] << " ";
    }
    else cout << -1;
    return 0;
}

数论

质数

筛法求质数

1
2
3
4
5
6
7
8
9
10
11
12
13
int get_prime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;//如果未被标记过说明是质数
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
    return cnt;//返回质数的个数
}

二次筛质数

  1. 用二次筛：假设一个数n是合数，那么它一定有\(d,\frac{n}{d}\)两个因子，假设\(d<\frac{n}{d}\)，则\(d<\sqrt{n}\)，所以只需要找出\(1\sim\sqrt{n}\)的所有素数，然后用这些素数更新\([l,r]\)的所有合数即可
  2. 对于素数p，要找到\([l,r]\)中所有以p为最小质因子的合数，可以从max(2 * p, (l + p - 1) / p * p)开始寻找，然后不断+p即可，其中(l + p - 1) / p * p等价于\(\lceil\frac{l}{p}\rceil\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
int prime[N], cnt;
ll prime2[N], k;
bool st[N];

void get_prime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
int main()
{
    int l, r;
    get_prime(50000);
    while(scanf("%d%d", &l, &r) != -1)
    {
        memset(st, 0, sizeof st);
        memset(prime2, 0, sizeof prime2);
        k = 0;
        for(ll i = 0; i < cnt; i++)
        {
            ll p = prime[i];
            for(ll j = max(2 * p, (l + p - 1) / p * p); j <= r; j += p)
                st[j - l] = true;   
        }
        for(int i = 0; i <= r - l; i++)
        {
            if(!st[i] && i + l > 1)
                prime2[k++] = i + l;
        }
        if(k < 2) cout << "There are no adjacent primes." << '\n';
        else
        {
            int minp = 0, maxp = 0;
            for(int i = 0; i + 1 < k; i++)
            {
                int d = prime2[i + 1] - prime2[i];
                if(d < prime2[minp + 1] - prime2[minp]) minp = i;
                else if(d > prime2[maxp + 1] - prime2[maxp]) maxp = i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", prime2[minp], prime2[minp + 1], prime2[maxp], prime2[maxp + 1]);
        }
    }
    return 0;
}

约数

约数个数

把一个数N写成\(N=p_1 ^ {x_1}\cdot p_2^{x_2}\cdot ... \cdot p_k^{x_k}\), 则约数个数为\((x_1+1)(x_2+1)...(x_k+1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <unordered_map>
using namespace std;
const int mod = 1e9 +7;
int main()
{
    int n;
    cin >>n;
    unordered_map<int, int> mp;
    while(n--)
    {
        int a;
        cin >>a;
        for(int i = 2; i <= a / i; i++)
        {
            while(a % i == 0)
            {
                mp[i]++;
                a /= i;
            }
        }
        if(a >1) mp[a]++;
    }
    long long ret = 1;
    for(auto& [x, y] : mp)
    {
        ret = ret * (y + 1) % mod;
    }
    cout << ret % mod;
    return 0;
}

约数之和

把一个数N写成\(N=p_1 ^ {x_1}\cdot p_2^{x_2}\cdot ... \cdot p_k^{x_k}\), 则约数之和为\(( p_1^0+p_1^1+..._+p_1^{x_1})\times...\times (p_k^0+p_k^1+...+p_k^{x_k})\)

1
2
3
4
5
6
7
8
9
10
11
unordered_map<int, int> mp;//存储质因数对应的个数
ll res = 1;
for(auto& [x, y]: mp)
{
    ll t = 1;
    while(y--)
    {
        t = (t * x + 1) % mod;//得到每个质因子对应的加和值
    }
    res = res * t % mod;//将所有质因子的加和值乘起来
}

最大公约数

1
2
3
4
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);    
}

欧拉函数

1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。 若在算数基本定理中，\(N=p_1^{a_1}p_2^{a_2}…p_m^{a_m}，则：ϕ(N) = N×\frac{p_1−1}{p1}×\frac{p_2−1}{p2}×…×\frac{p_m−1}{p_m}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a;  cin >> a;
        ll res = a;
        for(int i = 2; i <= a / i; i++)
        {
            if(a % i == 0) res = res / i * (i - 1);
            while(a % i == 0) a /= i;
        }
        if(a > 1) res = res / a * (a - 1);
        cout << res << '\n';
    }
    return 0;
}

筛法求欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
ll phi[N], prime[N];
bool st[N];
ll n, cnt;

int main()
{
    cin >> n;
    phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            phi[i] = i - 1;
            prime[cnt++] = i;
        }
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) 
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    ll res = 0;
    for(int i = 1; i <= n; i++) res += phi[i];
    cout << res;
    return 0;
}

阶乘分解

求阶乘中各个因子的个数

8！中因数2的个数：8 / 2 + 8 / 4 + 8 / 8 = 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int prime(int x)
{
    if(x == 2) return 1;
    for(int i = 2; i <= x / i; i++)
    {
        if(x % i == 0) return 0;
    }
    return 1;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 2; i <= n; i++)
    {
        if(!prime(i)) continue;
        long long x = i, ans = 0;//因为n！可能很大，所以用long long存储x
        while(x <= n) ans += n / x, x *= i;
        cout << i << " " << ans << '\n';
    }
    return 0;
}

快速幂

给定n组\(a_i,b_i,p_i\)，对于某组数据，求出\(a_i^{b_i}modp_i\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
typedef long long ll;
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()
{
    cin >> n;
    while(n--)
    {
        ll a, b, p;
        cin >> a >> b >> p;
        cout << qmi(a, b, p) % p << '\n';
    }
    return 0;
}

快速幂求逆元

\(b^{m-2}\)即为b的乘法逆元（m为mod的数）

求组合数

利用逆元O(nlogn)

\(b!^{-1} = ((b-1)!b)^{-1}=(b-1)!^{-1}b^-1 = (b-1)!^{-1}b^{m-2}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, mod = 1e9 + 7;
ll f[N], inf[N], n;//f用来存储阶乘，inf用来存储阶乘的逆元
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;
}
void Init()
{
    f[0] = inf[0] = 1;
    for(int i = 1; i < 1e5 + 10; i++)
    {
        f[i] = f[i - 1] * i % mod;
        inf[i] = inf[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}
int main()
{
    cin >> n;
    Init();
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        cout << f[a] * inf[b] % mod * inf[a - b] % mod << '\n';
    }
    return 0;
}

lucas定理

lucas定理：\(C_a^b = C_{\frac{a}{p}}^{\frac{b}{p}}C_{a\ mod\ p}^{b\ mod\ p}(mod\ p)\)

适用于p较小的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, p, n;
ll qmi(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
ll C(ll a, ll b)
{
    if(b > a) return 0;
    ll res = 1;
    for(int i = 1, j = a; i <= b; i++, j--)
    {
        res = res * j % p;
        res = res * qmi(i, p - 2) % p;
    }
    return res;
}
ll lucas(ll a, ll b)
{
    if(a < p && b <p) return C(a, b);
    return C(a % p, b % p) * lucas(a / p, b / p) % p; 
}
int main()
{
    cin >> n;
    while(n--)
    {
        cin >> a >> b >> p;
        cout << lucas(a, b) << '\n';
    }
}

高精度

将\(C_a^b=\frac{a!}{b!(a-b)!}\)中的\(a!\ b!\ (a-b)!^{-1}\)用质因子进行表示，只进行上标的减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
const int N = 5100;
int prime[N], st[N], cnt, num[N];
int a, b;
void get_prime(int x)//筛质数
{
    for(int i = 2; i <= x; i++)
    {
        if(!st[i]) prime[cnt++] = i;;
        for(int j = 0; prime[j] <= x / i; j++)
        {
            st[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
int count(int p, int n)//数n中含多少个因子p
{
    int res = 0;
    while(n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}
vector<int> mul(const vector<int>& A, const int p)//高精度乘法
{
    if(p == 0) return {0};
    int t = 0;
    vector<int> res;
    for(int i = 0; i < A.size() || t > 0; i++)
    {
        if(i < A.size()) t += A[i] * p;
        res.push_back(t % 10);
        t /= 10;
    }
    while(res.size() > 0 && res.back() == 0) res.pop_back();
    return res;
}
int main()
{
    cin >> a >> b;
    get_prime(a);
    for(int i = 0; i < cnt; i++)
        num[i] = count(prime[i], a) - count(prime[i], b) - count(prime[i], a - b);
    vector<int> res = {1};
    for(int i = 0; i < cnt; i++)
        for(int j = 0; j < num[i]; j++)
            res = mul(res, prime[i]);
    for(int i = res.size() - 1; i >= 0; i--) cout << res[i];
    return 0;
}

动态规划

背包问题

01背包问题

1
2
3
4
5
6
7
8
9
10
int main()
{
    cin >> N >> V;
    for(int i = 1; i <= N; i++)	cin >> v[i] >> w[i];
    for(int i = 1; i <= N; i++)
        for(int j = V; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[V];
    return 0;
}

完全背包

每个物品可以使用无数次，求拿容量不超过V的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N];
int f[N];
int n, m;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++) 
        for(int j = v[i]; j <= m; j++)//与01背包代码唯一不同的地方
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}

多重背包

每个物品只能拿一次，每个物品最多有s件，求拿总容量不超过V的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const int N = 12010;
int v[N], w[N];
int n, m;
int f[N];
int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i++) 
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt++;
            v[cnt] = a * k, w[cnt] = b * k;
            s -= k, k *= 2;
        }
        if(s > 0)
        {
            cnt++;
            v[cnt] = a * s, w[cnt] = b * s;
        }
    }
    n = cnt;
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}

分组背包

每组有若干个物品，每组只能选一个物品，求拿总容量不超过V的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N];
int v[N][N], w[N][N], s[N];
int n, m;
int main()
{
    cin >> n >> m;
    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];
    }
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--)
            for(int k = 0; k <= s[i]; k++)
                if(v[i][k] <= j)    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m];
    return 0;
}

线性Dp

最长上升子序列

法一：时间复杂度\(O(n^2)\)

\(f(i) = max(f(j)+1)\)，其中\(w[j]<w[i],j<i\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int N = 1010;
int w[N], f[N];
int n, ans;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j <= i; j++)
            if(w[i] > w[j]) f[i] = max(f[i], f[j] + 1);//找到以比w[i]小的节点结尾的最长上升子序列
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}

方式二：时间复杂度\(O(nlogn)\)

  1. 状态表示\(f(i)\)
    • 集合：表示长度为i的序列的最小结尾
    • 属性：序列中最后一个值的最小值
  2. 状态计算：
    • 如果\(w[i]\)大于\(f(cnt)\)，直接加到cnt之后即可
    • 如果小于等于\(f(cnt)\)，找到f数组中第一个大于\(w[i]\)的位置，进行替换
  3. 答案：f数组的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int w[N], f[N];
int n, cnt;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];
    f[++cnt] = w[1];//初始化
    for(int i = 2; i <= n; i++)
    {
        if(w[i] > f[cnt]) f[++cnt] = w[i];
        else f[lower_bound(f + 1, f + cnt + 1, w[i]) - f] = w[i];
    }
    cout << cnt;
    return 0;
}

最长公共子序列

状态计算：

  1. \(a[i] == b[j]\)，\(a[i],b[j]\)都在，那么最长子序列的长度是前一个 + 1，即\(f[i-1][j-1]+1\)
  2. \(a[i]!=b[j]\)
    • \(a[i]\)在，\(b[j]\)不在：那就是算A的前i个字符，B的前i - 1个字符的公共子序列的最长长度，即\(f[i][j - 1]\)
    • \(a[i]\)不在，\(b[j]\)在：那就是算A的前i - 1个字符，B的前i个字符的公共子序列的最长长度，即\(f[i-1][j]\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
char a[N], b[N];
int n, m;
int f[N][N];
int main()
{
    cin >> n >> m >> a + 1 >> b + 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m];
    return 0;
}

区间Dp

石子合并

状态计算：

  1. 涉及区间和问题，使用前缀和
  2. \(f(i,j) = f(i,k)+f(k+1,j)+s[j]-s[i-1]\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
const int N = 310;
int f[N][N], a[N];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
    
    for(int len = 2; len <= n; len++)
    {
        for(int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            f[i][j] = 0x3f3f3f3f;
            for(int k = i; k <= j; k++)
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
            }
        }
    }
    cout << f[1][n];
    return 0;
}

贪心

区间选点

给定 N个闭区间 \([ai,bi]\)，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。相当于问最少有多少重叠区间的集合

根据观察我们可以根据下一个区间左端点和上一个区间右端点的比较，判断是否有重叠，为了更好的比较就需要排序，那么就有两种解决方法：按右端点排序/按左端点排序

按右端点排序：

  1. 因为是按右端点排序的，所以在ed >= e[i].l的情况下，ed <= e[i].r是一定的，所以不需要特殊判断
  2. ed = e[i].r需要放在判断条件的里面，因为这个公共点不在新扩展的那部分区域；如果放在判断条件外面，就相当于默认那段新展开的区域也是有选择的点的，但是那一段新展开的区域显然不是和前面的区间的公共段，所以那个选择的公共点不在新展开的区域
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edges
{
    int l, r;
    bool operator<(const edges& W)const
    {
        return r < W.r;
    }
}e[N];
int n;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> e[i].l >> e[i].r;
    sort(e, e + n);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i++)
    {
        if(ed < e[i].l) 
        {
            res++;
            ed = e[i].r;
        }
    }
    cout << res;
    return 0;
}

按左端点排序：

  1. 在ed >= e[i].l情况下，需要更新公共点所在区间
  2. 在ed < e[i].l情况下，证明当前区域和之前的区域没有重叠区间，集合数加1，更新区间边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edges
{
    int l, r;
    bool operator<(const edges& W)const 
    {
        return l < W.l;
    }
}e[N];
int n;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> e[i].l >> e[i].r;
    sort(e, e + n);
    int res = 1, ed = e[0].r;
    for(int i = 1; i < n; i++)
    {
        if(ed >= e[i].l)
        {
            ed = min(ed, e[i].r);
        }
        else
        {
            res++;
            ed = e[i].r;
        }
    }
    cout << res;
    return 0;
}

最大不相交区间的数量

给定 N个闭区间\([ai,bi]\)，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

  1. 按照前一题区间选点的方式，将所有区间分成几个集合，每个集合中的各个区间都有公共区域。
  2. 若要选择不相交的区域，不相交的区域一定在不同的集合里，所以总集合数就是最大不相交的区域，即区间选点的数量
  3. 和区间选点代码相同

区间分组

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

引入小根堆，对区间右端点进行操作比较，如果当前区间的左端点大于最小的区间右端点，可以直接加入到已有的组；否则，新开一个组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edges
{
    int l, r;
    bool operator<(const edges& W)const
    {
        return l < W.l;
    }
}e[N];
int n;
priority_queue<int, vector<int>, greater<int>> q;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> e[i].l >> e[i].r;
    sort(e, e + n);
    for(int i = 0; i < n; i++)
    {
        if(q.empty() || q.top() >= e[i].l)   q.push(e[i].r);
        else 
        {
            q.pop();
            q.push(e[i].r);
        }
    }
    cout << q.size();
    return 0;
}

区间覆盖

给定 N 个闭区间 \([ai,bi]\) 以及一个线段区间 \([s,t]\)，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 −1。

  1. 按照区间左端点进行排序，在包含start点的所有区间中找到右端点最大的区间

  2. 判断条件

    1. 如果左端点小于start，就将它的右端点和当前最大右端点进行比较

    2. 得到的最大右端点如果仍小于start，说明没有包含start的区间，break，res = -1

    3. 得到的最大右端点如果大于end，那么表示整个区间都被表示了，可以退出

    4. \(\color{red}{注意：}\)因为可能存在

      1 5

      2

      -1 2

      2 4

      这种情况，即待表示的区间右端点5大于目前拥有的区间的最大右端点，所以需要再大于end的情况下加一个判断，表示走到了结尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edges
{
    int l, r;
    bool operator<(const edges&W)const
    {
        return l < W.l;
    }
}e[N];
int n, s, t, res;
int main()
{
    cin >> s >> t;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> e[i].l >> e[i].r;
    sort(e, e + n);
    bool success = false;
    for(int i = 0; i < n; i++)
    {
        int j = i, st= -2e9;
        while(j < n && e[j].l <= s)
        {
            st = max(st, e[j].r);
            j++;
        }
        if(st < s) 
        {
            res = -1;
            break;
        }
        res++;
        if(st >= t) 
        {
            success = true;
            break;
        }
        s = st;
        i = j - 1;
    }
    if(!success) res = -1;
    cout << res;
    return 0;
}