acwing模板

0 语法与STL

0.1 重定向输入输出

1
2
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);

0.2 程序运行时间

1
2
3
4
5
double start,finish; /* 开始时间,结束时间 */ 
start=(double)clock(); /* 我的time.h内没有CLOCKS_PER_SEC */ 
//中间放要测试的代码
finish=(double)clock(); 
printf("%.4fms",(finish-start));

0.3 函数

c++常用函数

函数名 解释 返回值类型
isalpha() 判断是否是字母 bool
tolower() 将字符转为小写 char
ceil() 向上取整
floor() 向下取整

函数名称 返回值【输入是字符char】
isalnum() 如果是字母或数字，返回true
isalpha() 如果是字母，返回true
isdigit() 如果是数字，返回true
islower() 如果是小写字母，返回true
ispunct()
如果是标点符号，返回true

isspace() 如果是空白字符，包括空格、进纸、换行符、回车、制表符等，返回true
isupper() 如果是大写字符，返回true
tolower() 如果是大写字符，返回其小写
toupper() 如果是小写字符，返回其大写
isxdigit() 如果是16进制数，返回true，如0-9、a-f、A-F
iscntrl() 如果是控制字符，返回true
isgraph() 如果是除空格以外的打印字符，返回true
isprint() 如果是打印字符，返回true

0.1.1 结构体定义（带初始化）

1
2
3
4
5
6
7
struct Node {
    int x, y;
    Node(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

0.4 对拍

0.5 加速cin和cout

禁用输入输出缓存区

速度可以达到 scanf/printf，甚至比它还快

1
2
3
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(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
inline int read() 
{
    int x=0,f=1;
    char c=getchar();
    while (c<'0' || c>'9') 
    { 
        if (c=='-')  f=-1; 
        c=getchar(); 
    } 
    while (c>='0' && c<='9') 
    { 
        x=x*10+c-'0';
         c=getchar(); 
     } 
    return x*f;
}
 
inline void print(int x) 
{
    if (x<0) 
    {
        putchar('-');x=-x;
    }
    if (x>9) print(x/10);
    putchar(x%10+'0');
}

1 基础算法

1.1 排序

1.1.1 快速排序

1
2
3
4
5
6
7
8
9
10
11
void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j) {
        while (q[++ i] < x);
        while (q[-- j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

1.1.2 快速选择

选择数组里第k小数

1
2
3
4
5
6
7
8
9
10
11
12
13
int quick_sort(int l, int r, int k) {
    if (l == r) return a[l];
    int x = a[(l + r) >> 1], i = l - 1, j = r + 1;
    while (i < j) {
        while (a[ ++ i] < x);
        while (a[ -- j] > x);
        if (i < j) swap(a[i], a[j]);
    } 
    int sl = j - l + 1;
    if (sl >= k) return quick_sort(l, j, k);
    return quick_sort(j + 1, r, k - sl);

}

1.1.2 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void merge_sort(int q[], int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid),merge_sort(q, mid + 1, r);
    
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        tmp[k ++] = q[i] <= q[j] ? q[i ++] : q[j ++];
        
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    
    for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}

1.2 查找

1.2.1 二分查找

x的左边界

1
2
3
4
5
6
int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r >> 1;
    if (q[mid] >= x) r = mid;
    else l = mid + 1;
}

x的右边界

1
2
3
4
5
6
7
int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r + 1 >> 1;
    if (q[mid] <= x) l = mid;
    else r = mid - 1;
}
cout << l << endl;

1.3 高精度

1.3.1 高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
//C = A + B
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i ++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    return C;
}

1.3.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
//(bool) A >= B
bool cmp(vector<int> &A, vector<int> &B) {
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i --) 
        if (A[i] != B[i])
            return A[i] > B[i];
    
    return true;
}
//C = A - B
vector<int> sub(vector<int> &A, vector<int> &B) 
    if (!cmp(A, B)) return sub(B, A);
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ ) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    
    while (C.size() > 1 && C.back() == 0) C.pop_back(); 	//去掉前导零
    return C;
}

1.3.3 高精度乘法（vector * int)

1
2
3
4
5
6
7
8
9
10
11
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

1.3.4 高精度除法

1
2
3
4
5
6
7
8
9
10
11
12
13
//C = 商， r = 余
vector<int> div(vector<int> &A, int b, int &r) {
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i --) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

1.4 前缀和差分

1.4.1 一维前缀和

含义: s[i] = a[1] + a[2] + … + a[i]

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

1.4.2 二维前缀和

含义: s[i][j] = a[0][0] 与a[i][j] 组成的矩阵的和

二维矩阵和： s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

1
2
3
4
5
6
7
for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j ++)
            scanf("%d", &a[i][j]);
            
    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];

1.4.3 一维差分

1
2
3
4
5
6
int a[N], b[N];

void insert(int l, int r, int x) {
    b[l] += x;
    b[r + 1] -= x;
}

1.4.4 二维差分

1
2
3
4
5
6
7
8
int a[N][N], b[N][N];

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

1.5 双指针算法

核心：将O(n^2)的算法， 利用双指针能降为O(n)

思路：先写一个暴力做法， 看一下i和j有没有单调规律

1.5.1 模板1

1
2
3
4
5
6
7
8
for (int i = 0, j = 0; i < n; i ++) {
    //加入i
    s[a[i]] ++;	//s[]，计数器
    //假如不满足， 右移j直到满足
    while (check()) j ++;
    //记录答案
    ans = max(ans, j - i + 1);
}

1.6 位运算

1.6.1 求n的二进制表示中第k位

1
(n >>) k & 1

1.6.2 x的最后一位1

1
2
3
int lowbit(int x) {
    return x & -x; 	// x & (~x + 1) 
}

1.7 离散化

大范围内少数量的数， 映射到从0开始的一段连续的值（下标）；

  1. 可能存在重复元素 （去重）
  2. 如何算出x离散化后的值 （二分）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;

int find(int x) {
    int l = 0, r = alls.size() -1 ;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

1.8 区间合并

将存在交集的区间合并为一个区间。

思路：

  1. 按左边界为主序、右边界为次序排序
  2. 初始化一个初始区间（初始手里的区间）（起始边界都为负无穷）
  3. 从左往右遍历排序好的区间， 做如下合并操作：
    1. 如果遍历到的区间左边界大于当前手里区间的右边界， 说明从该区间往后的区间都不可能与当前区间合并（即不重合、没有交集）（因为区间是排序好的），则手里区间是一个已合并后的确定区间，将该区间加入合并后的数组。手里区间替换为当前区间
    2. 如果遍历到的区间左边界小于当前手里区间的右边界， 说明两个区间存在交集、可以合并。则合并后的区间右边界为两者区间的最右边界，左边界不变（因为是按左边界排序，手里区间的左边界必<=当前区间的左边界， 所以不用考虑左边界）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(vector<PII> &segs) {
    vector<PII> res;
    sort(segs.begin(), segs.end());
    
    int st = -2e9, ed = -2e9;
    for (auto seg : segs) 
        if (ed < seg.first) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else 
            ed = max(ed, seg.second);
            
    if (st != -2e9) res.push_back({st, ed});
    
    segs = res;
}

2 数据结构

2.1 单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 100010;
int n;
int head, e[N], ne[N], idx;

void init(){
    head = -1, idx = 0;
}
//头插
void add_to_head(int x) {
    e[idx] = x, ne[idx] = head, head = idx ++;
}

//k后插x
void add(int k, int x) {
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++;
}

//移除k后一个
void remove(int k) {
    ne[k] = ne[ne[k]];
}

2.2 双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 100010;
int n;
int l[N], r[N], e[N], idx;

//初始化
void init() {
    r[0] = 1, l[1] = 0, idx = 2;
}

//在k的右边插入x
void add(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) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

2.3 栈

1
2
3
4
5
6
7
8
9
10
11
const int N = 100010;
int q[N], tt = 0;
//push
q[tt ++] = x;

//pop
tt --;

//empty?
tt >= 0?

2.4 队列

1
2
3
4
5
6
7
8
9
10
const int N = 100010;
int q[N], hh, tt;
 //push x – 向队尾插入一个数 x；
q[++ tt] = x;
// pop – 从队头弹出一个数；
++ hh;
// empty – 判断队列是否为空；
cout << (hh <= tt ? "NO" : "YES") << endl;
// query – 查询队头元素。
cout << q[hh] << endl;

2.4 单调栈

1
2
3
4
5
6
7
8
9
const int N = 100010;
int stk[N], a[N], tt;
void init() {
    tt = -1;
    stk[ ++ tt] = -1;
}
//单调递增
while (tt && stk[tt] >= a[i]) tt --;
stk[++ tt] = x;

2.5 滑动窗口 （单调队列）

  1. 先考虑暴力解法
  2. 考虑能不能去掉其中一些元素
  3. 考虑去掉元素后是否构成单调队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>

using namespace std;

const int N = 1000010;
int n, k;
int a[N], q[N];

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++) {
    if (hh <= tt && q[hh] < i - k + 1) hh ++;
    //单调递增
    while (hh <= tt && a[q[tt]] >= a[i]) tt--;
    q[++ tt] = i;
    if (i >= k - 1) printf("%d ", a[q[hh]]);
}

2.6 KMP

利用要匹配的字符串p的前字串的最大前后缀匹配长度，来对当前s[i] != p[j]时的，利用next[j + 1]的最大匹配度，直接跳转到s[i]匹配p[j]的阶段，从而减少重复计算，优化时间复杂度的算法。

重点：

  • 理解前后缀
  • 理解为什么当前不匹配时可以跳到上一个最大匹配下标
  • 理解next数组
  • 理解next数组生成。

变量定义

1
2
3
const int N = 100010, M = 1000010;	//字符数组的最大长度
char p[N], s[M];	//s中匹配字符串p，从下标1开始
int ne[N];	//p的next数组，从下标1开始

读入字符串

1
cin >> n >> p + 1 >> m >> s + 1;	//n为字符串p的长度，m为字符串s的长度。两个字符数组都从1开始，方便代码

next数组

next[i] ：前i个字符形成的字符串的，前缀和后缀最大匹配

因为真前缀和真后缀不能取同样的起点和终点。同样的起点和终点不构成真前缀和真后缀。所以字符串长度最少为2，才有意义。

即长度小于2时，最大匹配为0。所以next[i]的i从2开始计算

  • ne[i]：前i个字符的前后缀最大匹配长度
  • j：前i-1个字符的前后缀最大匹配长度
1
2
3
4
5
6
7
8
9
10
11
for (int i = 2, j = 0; i <= n; i ++) {	//i:前i个字符，j：前i-1个字符最大匹配长度
    while (j && p[i] != p[j + 1]) j = ne[j];	//寻找最大匹配j，可能为0
    //当j为0时说明前面的字串都没有任何匹配，就利用不到之前的匹配
    //p[i]!=p[j + 1]，假如前一个字串的最大匹配长度是j，那么说明[1.j] 和[i-j,i-1]两个字串相同，那么就需要判断p[i]和p[j+1]
    //1. p[i]==p[j+1]：即_abca时j=1, i=4;计算_abcab时，i=5, p[i]==p[j+1]，退出循环，即当前j对ne[i]是有效的
    //2. p[i]!=p[j+1]: 即_abca时j=1, i=4;计算_abcaa时，i=5, p[i]!=p[j+1]意味着最大匹配不能以p[i-1]作为开始，要以多少作为开始，就从j=ne[j]开始（这里也利用到KMP思想），在这里j=ne[j]=ne[1]=0，这时j=0退出循环，即从头开始计算最大匹配
    if (p[i] == p[j + 1]) j ++;	//while循环处理好最大匹配
    //可能为0，当为0时意味着从新匹配，就需要判断p[i]是否和p[j+1]（记住这里j+1即第一个字符，字符串数组从下标1开始），相等则匹配度为1；
    //当j不为0即意味着不需要从头开始匹配，那么也意味着p[i]必定等于p[j+1]，这时候j++;
    ne[i] = j;	//记录值
}

KMP求S中的P的字符串匹配

利用next数组求字符串匹配（查找S中是否存在子串P）。

1
2
3
4
5
6
7
8
9
10
for (int i = 1, j = 0; i <= m; i ++) {	//i=1从头开始，一开始的最大匹配是j=0
    while (j && s[i] != p[j + 1]) j = ne[j];	//对于当前s[i]，求可利用的j的最大值
    //如果j为0，意味从头开始匹配，j没法再退
    //否则s[i]!=p[j+1]时，j=ne[j]表示左移P串，即拿s[i]与p[ne[j]]比较
    if (s[i] == p[j + 1]) j ++;	//如果两个字符相等，匹配长度+1
    if (j == n)  {	 //如果匹配长度=p的长度，则匹配成功
        printf("%d ", i - n);
        j = ne[j]; //求下一个匹配时，需要将j回退，也就是考虑当前s[i]!=p[j],
    }
}

2.7 Trie树

2.7.1 字符串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
const int N = 20010;
int n;
int s[N][26], cnt[N], idx;

//插入
void insert(string str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!s[p][u]) s[p][u] = ++idx;
        p = s[p][u];
    }
    cnt[p] ++;
}

//查询
int query(string str) {
    int p = 0;
    for (int i = 0; str[i]; i ++) {
        int u = str[i] - 'a';
        if (!s[p][u]) return 0;
        p = s[p][u];
    }
    return cnt[p];
}

2.7.2 数字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
const int N = 3100010;
int son[N][2], idx;

//0-1 Trie 插入x
void insert(int x) {
    int p = 0;
    for (int i = 31; i >= 0; i --) {
        int u = (x >> i) & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}

//查询最大异或值
int query(int x) {
    int p = 0, ret = 0;
    for (int i = 31; i >= 0; i --) {
        int u = (x >> i) & 1;
        ret <<= 1;
        if (son[p][!u]) ret += 1, p = son[p][!u];
        else p = son[p][u];
    }
    return ret;
}

2.8 并查集

什么时候可以试用并查集：

  • 有传递性质
  • 相互的传递性质

两个操作：

  1. 合并两个集合
  2. 查询两个元素是否在同一个集合

两个优化：

  1. 路径压缩 (logn)

  2. 按秩合并(logn)：

将两个优化都运用后，可以认为并查集的两个操作都是O1的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 100010;

int n, m;
int p[N], len[N];

//初始化
void init() {
    for (int i = 0; i <= n; i ++) p[i] = i, len[i] = 1;
}

//查
int find(int x) {
    return p[x] == x? x : p[x] = find(p[x]);
}

//并
void merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    if (len[fx] < len[fy]) swap(fx, fy);
    len[fx] += len[fy];
    p[fy] = fx;
}

2.9 堆

  1. 插入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

const int N = 100010;
int n, m;
int h[N], len;

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

//up
void up(int u) {
    int t = u;
    while (u / 2 && h[u / 2] > h[u]) {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

2.9.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
const int N = 100010;
int n;
int h[N], hp[N], ph[N], len;	//ph：第i个插入的数在堆的哪个位置
							//hp: 堆的第i个位置是第几个插入的数

void heap_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

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

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

3 哈希表

3.1 模拟散列表

3.1.1 拉链法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 100003;
int n;
int h[N], e[N], ne[N], idx;

void insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;
}

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

3.1.2 开放式寻址法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 200003, null = 0x3f3f3f3f;
int n;
int h[N];

int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) {
        k ++;
        if (k == N) {
            k = 0; 
        }
    }
    return k;
}

3.2 字符串哈希 （字符串前缀哈希法）

原理：将一个字符串看成一个P进制的数，将P进制数转换成十进制数，得到该字符串的哈希值。

例字：ABCD: A * P^3 + B * P^2 + C * P^1 + D * P^0所得的十进制数就是该字符串的哈希值。

由于字符串可能很大，得到的数值会非常大，故对该数进行取模。由ULL溢出后自动取模做到这一步。取模后的数可能会由冲突，该算法的前提假设人品足够好，不考虑冲突的情况。

  1. 不能映射成0（如果A映射成0，那么A与AA、AAA将冲突

  2. 假设人品(Rp)足够好，假定不存在冲突

经验值：p取131/13331， Q取2^64

好处：利用前缀哈希，计算出任何字串的哈希值。

求区间[l,r]的字串的哈希值：
由于左边是高位，右边是低位，需要最低位对其。将h[l - 1]右移与h[r]右对齐（最低位）对齐后，相减的差即为该区间字串的哈希值。（右移r - l + 1位需要乘上P^(r - l + 1)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef unsigned long long ULL;
const int N = 100010, P = 131;

int n, m;
char s[N]; //字符串数组，下标从1开始，方便处理
ULL h[N], p[N];	//h[N]字符串前缀哈希值，p[N] p的n次方数组（对ull取模后的值）
//求区间[l,r]的字串的哈希值：
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

p[0] = 1;
//求取字符串前缀哈希值、P的次方值（p数组存）
for (int i = 1; i <= n; i ++) {
    p[i] = p[i - 1] * P;
    h[i] = h[i - 1] * P + s[i];
}

3. 搜索与图论

3.1 DFS

3.1.1 交换法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 10;
int n;
int a[N];

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++) printf("%d ", a[i]);
        puts("");
    }
    
    for (int i = u; i < n; i ++) {
        swap(a[i], a[u]);
        dfs(u + 1);
        swap(a[i], a[u]);
    }
}

3.1.2 回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 10;
int n;
int a[N];
bool vis[N];

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++) printf("%d ", a[i]);
        puts("");
    }
    
    for (int i = 0; i < n; i ++) {
        if (vis[i]) continue;
        vis[i] = true;
        a[u] = i + 1;
        dfs(u + 1);
        vis[i] = false;
    }
}

3.1.3 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
#include <iostream>

using namespace std;

const int N = 20;
int n;
char g[N][N];
int col[N], dg[N], udg[N];

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++) puts(g[i]);
        puts("");
        return;
    }
    
    for (int i = 0; i < n; i ++)
        if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            g[i][j] = '.';
            
    dfs(0);
    
    return 0;
}

3.1.4 n皇后问题 (位运算解法)

3.2 BFS

3.2.1 BFS

按层级穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 110;
int q[N];

void bfs() 
{
    int hh =0,  tt = 0;
    q[0] = 1;
    
    while (hh <= tt) {
        auto t = q[hh ++];
        //将t的周围加入队列q
        //...
    }
}

3.2.2 A*

bfs的变种。普通bfs采用队列进行穷举最短路，由于某些时候穷举是必超时的，需要用A*来优化剪枝。A*相对于普通BFS由队列改为优先队列，队列内的元素按照不同场景下的优先度排序，即需要实现估价函数，根据估价函数来决定哪些状态在前，优先值高的状态优先出队，优先搜索，避免了BFS中路列内的元素全部更新一次的花费。

优点：一种基于贪心的BFS,不用穷举所有状态

缺点：如果估价函数没有意义或者是非正确的，依旧需要穷举所有状态，且优先队列还需要消耗时间排序。

八数码

求八数码任意一条最短路径并输出。如果采用普通的BFS穷举是能找到正确答案并且通过一定的数据，但所有用例会超时。通过A*优化的思路为，实现一个估价函数，每个数字相对于正确位置的曼哈顿距离的和。由此可推出，若曼哈顿距离和小，那优先遍历这一个状态，更容易找到答案，从而避免了更新队列内所有状态。是一个贪心思路。

为什么该估价函数能求到正确值？假如当前队列首的位置为1，则求其能达到的状态可能得到2,3,4三个状态，注意～这三个状态还得重新入队！因为我们没法保证说曼哈顿距离小的操作步数一定也小，只能说通过这个估价函数来猜，即曼哈顿距离小的操作步数可能也小（猜错了也没关系！因为新的状态会重新入队参与估价排序，从而不断更新，直到队列头是最有的操作步骤中的状态之一！），这样通过不断枚举的过程，不断逼近答案，最终得到答案！并且注意，这样的贪心策略，是不枚举更新所有队列状态的！

这是A*的魅力和优势，经过如上的推论，那么代码的思路也比较清晰了， 即将普通队列换成优先队列，还需要额外的估价函数，整体上和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
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
83
84
85
86
#include <cstring>
#include <unordered_map>
#include <queue>
#include <iostream>
#include <iostream>
#include <algorithm>

using namespace std;

int f(string state) {
    int res = 0;
    for (int i = 0; i < state.size(); i ++) {
        if (state[i] != 'x') {
            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    }
    return res;
}

string bfs(string start) {
    
    int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
    char op[]="rldu";
    string end = "12345678x";
    unordered_map<string, bool> st; // 状态
    unordered_map<string, int> dist; // 距离
    unordered_map<string, pair<string, char>> prev; // 上一步做了哪个移位
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>> > q; 
    q.push({f(start), start});
    dist[start] = 0;
    
    while (q.size()) {
        auto t = q.top(); q.pop();
        string state = t.second;
        if (state == end) break;
        
        if (st[state]) continue;
        st[state] = true;
        
        int step = dist[state];
        int x, y;
        for (int i = 0; i < state.size(); i ++) {
            if (state[i] == 'x') {
                x = i / 3, y = i % 3;
            }
        }
        string source = state;
        for (int i = 0; i < 4; i ++) {
            int tx = x + dx[i];
            int ty = y  + dy[i];
            if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3) {
                swap(state[x * 3 + y], state[tx * 3 + ty]);
                if (!dist[state] || dist[state] > step + 1) {
                    dist[state] = step + 1;
                    prev[state] = {source, op[i]};
                    q.push({f(state) + dist[state], state});
                }
                swap(state[x * 3 + y], state[tx * 3 + ty]);
            }
        }
    }
    string res;
    while (end != start) {
        res += prev[end].second;
        end = prev[end].first;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string g, c, seq;
    while (cin >> c) {
        g += c;
        if (c != "x") seq += c;
    }
    int t = 0;
    for (int i = 0; i < seq.size(); i ++) 
        for (int j = i + 1; j < seq.size(); j ++) 
            if (seq[i] > seq[j]) ++t;
    if (t & 1) puts("unsolvable");
    else cout << bfs(g) << endl;
    
    return 0;
}

补一个IDA*的写法，具体思路参考3.2.2 IDA*

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int path[100], depth;
string st, ed= "12345678x";
int mp[10];

char op[]="dlru";
int dx[] = {1, 0, 0, -1}, dy[] = {0, -1, 1, 0};

int f() {
    int res = 0;
    for (int i = 0; i < st.size(); i ++)
        if (st[i] != 'x') {
            int t = st[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    return res;
}
bool dfs(int u) {
    if (f() + u > depth) return false;
    if (st == ed) return true;
    
    int x, y;
    for (int i = 0; i < st.size(); i ++) 
        if (st[i] == 'x') 
            x = i / 3, y = i % 3;
        
    for (int i = 0; i < 4; i ++) {
        int a = x + dx[i], b = y + dy[i];
        if (u && path[u - 1] + i == 3) continue;
        if (a >= 0 && a < 3 && b >= 0 && b < 3) {
            swap(st[x * 3 + y], st[a * 3 + b]);
            path[u] = i;
            if (dfs(u + 1)) return true;
            swap(st[x * 3 + y], st[a * 3 + b]);
        }
    }
    return false;
}
void solve() {
    for (depth = 0;; ++depth) 
        if (dfs(0))
            break; 
    for (int i = 0; i < depth; i ++) 
        cout << op[path[i]];
}
int main() {
    char c;
    while (cin >> c) {
        st += c;
    }
    
    int t = 0;
    for (int i = 0; i < st.size(); i++) 
        for (int j = i + 1; j < st.size(); j ++)
            if (st[i] != 'x' && st[j] != 'x' && st[i] > st[j])
                ++t;
    if (t & 1) cout << "unsolvable" << endl;
    else solve();
    return 0;
}

3.2.3 迭代加深搜索

3.2.4 IDA*

前置知识：

  1. A*
  2. ID （迭代加深搜索）

由于 IDA * 改成了迭代加深搜索的方式，相对于 A * 算法，它的优点如下：

  1. 不需要记录已经遍历过的状态（省内存。因为是按层遍历，即使会多次经过一个状态，当其到达一定层次后，也会return。可以通过一点判断来阻止其左右左右左右一直来回抖动），
  2. 天然有序（dfs特性，按深度优先遍历时，会优先一个方向走到头，在求有序答案时，可考虑dfs相关）
  3. 避免优先队列花销。在A*中通常使用优先队列作为容器，出入队不仅需要排序，且队列还可能增长的比较大，此时无论是空间花费还是排序的时间消耗都是十分严重的。

缺点：

  1. 重复搜索：迭代加深搜索每次加深搜索层级时，都会对之前的状态也枚举一次。

取舍：某些重复计算的场景，有时候也是可以采取的。去除重复计算，不一定是最优解。

八数码II

求八数码A->B的最短路径中，字典序最小的一条

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

using namespace std;

const int N = 100;
int n, path[N];
string st, ed;
int mp[10];

char op[] = "dlru";
int dx[] = {1, 0, 0, -1}, dy[] = {0, -1, 1, 0};
int depth;
// distance
int f() {
    int dist = 0;
    for (int i = 0; i < st.size(); i ++) 
        if (st[i] != 'X') {
            int a = i / 3, b = i % 3;
            int x = mp[st[i] - '0'] / 3, y = mp[st[i] - '0'] % 3;
            dist += abs(a - x) + abs(b - y);
        }
    return dist;
}
// ida*
bool dfs(int u) {
    if (u + f() > depth) return false;
    if (st == ed) return true;
    // find X
    int x, y;
    for (int i = 0; i < st.size(); i ++)
        if (st[i] == 'X')
            x = i / 3, y = i % 3;
    // try
    for (int i = 0; i < 4; ++ i) {
        int a = x + dx[i], b = y + dy[i];
        // 去抖动
        if (u && path[u - 1] + i == 3) continue;
        // 回溯
        if (a >= 0 && a < 3 && b >= 0 && b < 3) {
            swap(st[x * 3 + y], st[a * 3 + b]);
            path[u] = i;
            if (dfs(u + 1)) return true;
            swap(st[x * 3 + y], st[a * 3 + b]);
        }
    }
    return false;
}
void solve() {
    // mp
    for (int i = 0; i < ed.size(); ++ i) 
        if (ed[i] != 'X')
            mp[ed[i] - '0'] = i;
    // ida*
    for (depth = 0;; ++ depth)
        if (dfs(0)) break;
    // output ans
    cout << depth << endl;
    for (int i = 0; i < depth; ++i) {
        cout << op[path[i]];
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> st >> ed;
        cout << "Case "<< i << ": ";
        solve();
    }
    return 0;
}

3.3 树与图的DFS

3.3.1 领接表

1
2
3
4
5
6
7
8
9
const int N = 100010, M = N * 2;

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

//领接表加边a->b
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

1
2
3
4
5
int h[N], w[N], e[N], ne[N], idx;
//add,a->b ，权重c
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

3.3.2 深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int h[N], e[M], ne[M], idx;
int vis[N];

//树的dfs
void dfs(int u) 
{
    vis[u] = true;
    
    for (int i = h[u]; i != -1; i = ne[i]) 
    {
        if (!vis[e[i] ]) {
            dfs(e[i])
        }
    }
}

3.4 树与图的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
const int N = 100010;

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

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

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

3.5 拓扑排序

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
const int N = 100010;

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

int n, m;

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

3.6 最短路

  1. 单源最短路
  2. 多源汇最短路 ： 多个询问， 起点和终点的最短距离

3.6.1 Dijkstra（无负权边）

n ：点数， m ： 边数

求两点之间的最短路，

前提条件：所有边都是正全权边（不存在负权边）

3.6.1.1 朴素Dijkstra

  1. 初始化所有点的路径为无穷大，起点的路径修改为0
  2. 从未确定的点中，选取距离起点最近的点，将该点加入以确定的点的集合
  3. 用该点更新其他所有未确定的点距离
  4. 重复2-3，直到所有的点全部确定。

时间O(n ^ 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
const int N = 510;

int n, m;
int g[N][N];	//领接矩阵
int dist[N];	//最短距离
bool st[N];		//已确定的点集合

int dijkstra() 
{
    //初始化
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    
    dist[1] = 0;
    
    //循环n次， 确定n个点的最短距离
    for (int i = 0; i < n; i ++) 
    {
        int t = -1;
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
                
        st[t] = true; 
        for (int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

3.6.1.2 堆优化Dijkstra

时间O(m * lgn)， 适合稀疏图

思路：利用优先队列， 将查找未确定的、距离最短的点这一步时间复杂度优化到logn

  1. 初始点的距离为0， 加入优先队列
  2. 取出队列里头结点（该点的距离为未确定的点中的最短距离）
  3. 如果该点已经确定， 回到2
  4. 更新该点到邻点的距离（假如更新后的点距离更短），并将邻点的距离加入优先队列
  5. 重复2-4， 直至队列为空
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
using namespace std;

const int N = 150010;
typedef pair<int, int> PII;

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

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

int dijkstra() 
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    
    dist[1] = 0;
    heap.push({0, 1});
    
    while (heap.size() )
    {
        auto t = heap.top(); heap.pop();
        int ver = t.second, distence = t.first;
        //这个点已确定
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
                // cout << dist[j] << ' ';
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

3.6.2 带负权的最短路

3.6.2.1 Bellman-Ford

O(n * m)

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
const int N = 510, M = 10010;

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

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


int bellman_ford() 
{
    memset(dist, 0x3f, sizeof dist);
    
    dist[1] = 0;
    for (int i = 0; i < k; i ++) 
    {
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m; j ++) 
        {
            auto [a, b, c] = edges[j];
            dist[b] = min(dist[b], backup[a] + c);
        }
    }
        
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

3.6.2.2 SPFA求最短路

O(m)， 最坏O(nm)

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

const int N = 100010, INF = 0x3f3f3f3f;

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

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

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while (q.size() ) 
    {
        auto t = q.front(); q.pop();
        st[t] = false;
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

3.6.2.3 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
const int N = 10010;

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

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

bool spfa()
{
    queue<int> q;
    for (int i = 1; i <= n; i ++) {
        q.push(i);
        st[i] = true;
    }
    
    while(q.size() )
    {
        auto t = q.front(); q.pop();
        st[t] = false;
        
        for (int i = h[t]; i != -1; i = ne[i]) 
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) 
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                
                if (cnt[j] >= n) return true;
                
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    return false;
}

3.7 多源汇最短路

3.7.1 Floyd

O(n ^ 3)

1
2
3
4
5
6
7
8
9
10
11
const int N = 210, INF = 1e9;
int n, m, k;
int d[N][N];

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

3.8 最小生成树

3.8.1 普利姆算法（Prim）

3.8.1.1 稠密图（朴素版Prim）

O(n^2)

思路：

  1. 初始化所有点的距离为正无穷
  2. 每次找到离集合最近的点， 用该点更新其余所有点到集合的距离
  3. 将该点加入集合
  4. 重复第2-3步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
const int N = 510, INF = 0x3f3f3f3f;

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

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    
    int res = 0;
    for (int i = 0; i < n; i ++)
    {
        int t = -1;
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        //不是第一个点且距离是正无穷， 说明与集合没有边相连        
        if (i && dist[t] == INF) return INF;
        // 第一个点时， 不用加权重
        if (i) res += dist[t];
        
        for (int j = 1; j <= n; j ++)
            if (!st[j] && dist[j] > g[t][j])
                dist[j] = g[t][j];
        
        st[t] = true;
    }
    
    return res;
}

3.8.1.2 稀疏图 （堆优化版Prim）

O(m logn)

1

3.8.2 克鲁斯卡尔算法（Kruskal）

O(mlogm)

  1. 从小到大排序所有边 （O(mlogm)
  2. 枚举每条边， 假如a，b不连通， 将这条边加入集合里（选了这条边用以连通a,b) (O(m))
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
typedef tuple<int, int, int> TIII;

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

int n, m;
TIII g[M];
int p[N];

int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}

int kruskal()
{
    sort(g, g + m);
    //初始化并查集
    for (int i = 1; i <= n; i ++) p[i] = i;
    
    int res = 0;    //最小生成树
    int num = n;    //集合数量
    for (int i = 0; i < m; i ++)
    {
        auto [c, a, b] = g[i];
        a = find(a), b = find(b);
        //如果a,b不连通， 连通a,b
        if (a != b)
        {
            p[a] = b;
            res += c;
            num --;
        }
    }
    
    if (num == 1) return res;
    return INF;
}

3.9 二分图

3.9.1 判断二分图（染色法）

  1. 遍历所有点
  2. 如果该点未染色， dfs染色该点及后面的点
  3. dfs过程中， 遇到未染色的点， dfs染色该点
  4. dfs过程中， 遇到已染色的点。 该点的颜色和要染的颜色一样，不处理。 不一样则返回false，说明不是二分图
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
const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

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

bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j])
        {
            if (!dfs(j, 3 - c)) return false;
        }
        if (color[j] == c) return false;
    }
    return true;
}

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

3.9.2 二分图最大匹配 （匈牙利算法）

O(n*m)

思路：

  1. 遍历所有点
  2. find当前点的所有边，如果对点没有对象， 则找到一个匹配
  3. 如果有对象， 则find这个对象， 如果这个匹配的对象能找到另外的匹配。则当前点能与这个对点成匹配
  4. 两者都不符合， 则当前点无对象
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
const int N = 510, M = 100010;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

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

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
        
    }
    return false;
}

int xyl()
{
    int res = 0;
    for (int i = 1; i <= n1; i ++)
    {
        memset(st, false, sizeof st);
        if (find(i)) res ++;
    }
    return res;
}

4. 数学知识

4.1 质数

4.1.1 试除法-判定质数

O(sqrt(n))

1
2
3
4
5
6
7
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++)
        if (x % i == 0) return false;
    return true;
}

4.1.2 试除法-分解质因数

O(sqrt(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void divised(int n)
{
    for (int i = 2; i <= n / i; i ++)
    {
        if (n % i == 0)
        {
           
            int s = 0;
            while (n % i == 0)
            {
                n /= i;
                s ++;
            }
            printf("%d %d\n", i, s);
        }
    }
    
    if (n > 1) printf("%d %d\n", n, 1);
    puts("");
}

4.1.3 质数筛

埃氏筛法 O(nloglogn)

欧拉筛 O(n)

埃氏筛法

对于每个质数， 都把以它为质因子的数筛去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 1000010;
int prime[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++)
        if (!st[i])
        {
            prime[cnt ++] = i;
            for (int j = i + i; j <= n; j += i)
                st[j] = true;
        }
}

欧拉筛

ps : pj 是 i 的最小质因子时， pj 也是 pj * i 的最小质因子！

根据这个条件就能保证每个合数只被最小质因子筛一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 1000010;
int prime[N], cnt;
bool st[N];

void get_primes(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;	// 重
        }
    }
}

4.2 约数

4.2.1 试除法-求一个数的约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> get_divisors(int n)
{
    vector<int> res;
    for (int i = 1; i <= n / i; i ++)
    {
        if (n % i == 0)
        {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }
    
    sort(res.begin(), res.end());
    return res;
}

4.2.2 约数个数

分解质因数后， 约数个数为所有质因数的指数+1的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n;
scanf("%d", &n);

unordered_map<int, int> mp;
while (n --)
{
    int x;
    scanf("%d", &x);

    for (int i = 2; i <= x / i; i ++)
        while (x % i == 0)
        {
            x /= i;
            mp[i] ++;
        }
    if (x > 1) mp[x] ++;
}

LL res = 1;
for (auto [_x, v] : mp) res = res *(v + 1) % mod;

4.2.3 约数之和

所有约数可用质因数求出， 约数之和 = (p1^0 * p1^1*…*p1^a) * (p2^0*…*p2^a) * (px^0*…*px^a)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
unordered_map<int, int> mp;
    while (n --)
    {
        int x;
        scanf("%d", &x);
        
        for (int i = 2; i <= x / i; i ++)
            while (x % i == 0)
            {
                x /= i;
                mp[i] ++;
            }
            
        if (x > 1) mp[x] ++;
    }
    
    LL res = 1;
    for (auto [p, a] : mp)
    {
        LL t = 1;
        while (a --) t = (t * p + 1) % mod;
        res = res * t % mod;
    }

4.2.4 欧几里得算法

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

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

4.3 欧拉函数

4.3.1 欧拉函数

n的欧拉函数：1-n中与n互质的数的个数

= n (1 - 1 / p1) ( 1 - 1 / p2) (1 - 1 / p3)…(1 - 1 / pk)

分解质因数， 假设质因数为p1 p2 p3 … pk:

  1. 从1-n中去掉p1、p2、…pk的所有倍数
  2. 加上所有pi * pj 的倍数
  3. 减去所有pi * pj * pk的倍数
  4. 加上所有pi * pj * pk * pl的倍数
  5. …
  6. （根据容斥原理得到 = n (1 - 1 / p1) ( 1 - 1 / p2) (1 - 1 / p3)…(1 - 1 / pk) ）
1
2
3
4
5
6
7
8
9
10
int euler_phi(int n) {
    int res = n;
    for (int i = 2; i <= n / i; i ++)
        if (n % i == 0) {
            while (n % i == 0) n /= i; 
            res = res - (res / i);
        }
    if (n > 1) res = res - (res / n);
    return res;
}

4.3.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
LL euler_shai(int n)
{
    phi[1] = 1;
    
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i])
        {
            phi[i] = i - 1;
            primes[cnt ++] = i;
        }
        
        for (int j = 0; primes[j] <= n / i; j ++)
        {
            auto pj = primes[j];
            st[pj * i] = true;
            if (i % pj == 0) {
                phi[i * pj] = (LL)phi[i] * pj;
                break;
            }
            phi[i * pj] = (LL)phi[i] * phi[pj];
        }
    }
    
    LL res = 0;
    for (int i = 1; i <= n; i ++) res += phi[i];
    return res;
}

4.4 快速幂

4.4.1 快速幂

1
2
3
4
5
6
7
8
9
10
11
typedef long long LL;

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

4.4.2 快速幂求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

typedef long long LL;

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

void niyuan(int a, int b) {
    if (a % p) printf("%d\n", qmi(a, p - 2, p));
    else puts("impossible");
}

4.5 扩展欧几里得算法

1
2
3
4
5
6
7
8
9
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d =  exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

4.5.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
#include <iostream>

using namespace std;

typedef long long LL;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n --)
    {
        int a, b, m;
        scanf("%d%d%d", &a, &b, &m);
        int x, y;
        int d = exgcd(a, m, x, y);
        
        if (b % d) puts("impossible");
        else printf("%d\n", (LL)x * (b / d) % m);
    }
}

5.动态规划

5.1 01背包

题目：有n个体积和价值分别为vi和wi的物品，求体积不超过m的最大价值

01背包-朴素解法

  • 集合表示

    • f[i][j]:从前i个物品中挑选（每个只能选一次）， 总体积不超过j的最大价值的所有集合。
    • Max 所有集合中最大的价值

  • 状态转移：

    • 不选第i个物品：f[i][j] = f[i - 1][j]
    • 选第i个物品：f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]) j >= v[i]
1
2
3
4
5
6
7
8
9
const int N = 1010;
int n, m;
int v[N], w[N], f[N][N];    

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

01背包-滚动数组

朴素解法中使用二维数组，仔细思考当前i的状态只由i-1转移得来，跟i-2、i-3等状态无关，即当前层只与上一层的状态有关，这种情况就可以用滚动数组来优化空间复杂度。滚动数组即开一个f[2][m]的数组，将一维重复利用，达到记录当前状态和上一状态目的。

使用滚动数组优化原数组，只需在滚动维度下边&1即可。当i为奇数时，&1=1；当i为偶数时，&1=0，使用位运算可以方便编码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 1010;
int n, m;
int f[2][N];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w;
        cin >> v >> w;
        for (int j = 1; j <= m; j ++) {
                f[i & 1][j] = f[i - 1 & 1][j];
                if (j >= v)
                    f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - v] + w);
            }
    }
    cout << f[n & 1][m];
    return 0;
}

01背包-一维优化

从朴素解法到滚动数组解法，优化了空间复杂度。思考二维的更新，当前v只会更新到v + j，即对数组前面的数值是没有影响的。若只使用一维记录时， 当j从大到小遍历，数组右边已遍历的视为当前i的记录，未遍历的视为i-1的记录（左边），即可无干扰的对数组进行更新。

注意一维优化的核心是，必须从大到小遍历容积j更新f[j]（若从小到大遍历j， 则可能当前物品被使用多次，即f[j]被更新多次）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 1010;
int n, m;
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w;  cin >> v >> w;
        for (int j = m; j >= v; j --)
            f[j] = max(f[j], f[j - v] + w);
    }
    cout << f[m];
    return 0;
}

5.2 完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。求不超过背包体积的最大价值

完全背包朴素解法

集合表示：

  • f[i][j]: 前i个物品（每个可以无限选）， 总体积不超过j的最大价值。
  • max：f[i][j]的所有集合中的最大价值

状态转移：

  • f[i][j] = f[i - 1][j]：不选当前物品i

  • f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k) j >= v[i] * k：选当前物品i，且总体积不超过j的的最大价值

n^3，超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 1010;
int n, m;
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w; cin >> v >> w;
        for (int j = 1; j <= m; j ++) {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k * v <= j; k ++)
            	f[i][j] = max(f[i][j], f[i - 1][j - v * k] + w * k);
        }
    }
    cout << f[n][m];
    return 0;
}

完全背包-时间优化（去重复计算

当某个物品体积小，可以选取多件时，更大的体积也支持选取多件，这两者中间就产生了重复的计算。计算大体积时，次大体积的为最优解，故不用比较此次大体积以下的计算。

当计算f[i][j]时，由 f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k)展开，可得如下：

f[i][j] = max(f[i-1][j], f[i-1][j-v] + w, f[i-1][j-2v]+2w, f[i-1][j-3v]+3w, ……, f[i-1][j-kv]+kw)

f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v] + w, f[i-1][j-3v] + 2w, ……, f[i-1][j-kv] + (k-1)w)

状态转移：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 1010;
int n, m;
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w;
        cin >> v >> w;
        for (int j = 1; j <= m; j ++) {
            f[i][j] = f[i - 1][j];
            if (j >= v)
            f[i][j] = max(f[i][j], f[i][j - v] + w);
        }
    }
    cout << f[n][m];
    return 0;
}

完全背包-一维空间优化

当某些题目情况下内存限制，需要优化空间内存，完全背包可以使用一维数组来求解。

理解思路1：完全背包的空间优化中，可以直接去掉一维的数组，来完成记录即可。

  • f[i][j] = f[i - 1][j]转换成f[j]=f[j]（省略不写）
  • f[i][j] = max(f[i][j], f[i][j - v] + w)转换成f[j]=f[j - v] + w（省略不写）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 1010;
int n, m;
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w;
        cin >> v >> w;
        for (int j = 1; j <= m; j ++) {
            if (j >= v)
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    cout << f[m];
    return 0;
}

理解思路2：01背包中的一维空间优化受限于每个物品只能选取一次，需要从大往小遍历体积，如若从小往大遍历，会造成物品重复选取。重复选取则正是完全背包符合的，重复的次数从0到无限次，符合完全背包的题目需求。所以只需要将01背包的思路反向遍历一次即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 1010;
int n, m;
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w;
        cin >> v >> w;
        for (int j = v; j <= m; j ++)
            f[j] = max(f[j], f[j - v] + w);
    } 
    
    cout << f[m];
    return 0;
}

5.3 多重背包

有 N种物品和一个容量是 V 的背包。第 i 种物品最多可选择Si件，每件体积是 vi，价值是 wi。求使物品体积总和不超过背包容量的最大价值。

01背包思路

第i种物品最多有si件，可以看成01背包中的si件相同的物品，这样即可套用01背包的思路和代码来解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 110;
int n, m;
int f[N];

int main() {
    cin >> n >> m;
    while (n --) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int i = 1; i <= s; i ++)
            for (int j = m; j >= v; j --)
                f[j] = max(f[j], f[j - v] + w);
    }
    
    cout << f[m];
    return 0;
}

完全背包思路

可以将多重背包当成完全背包来推，只是每个i物品的数量k有限制。

集合表示：

  • f[i][j]: 前i个物品（每个可以无限选），总体积不超过j的所有集合。
  • max：f[i][j]的所有集合中的中求最大价值的

状态转移：

  • f[i][j] = f[i - 1][j]：不选当前物品i
  • f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]*k] + w[i] * k) j >= v[i] * k && k <= s ：选当前物品i，且总体积不超过j，数量不超过s的最大价值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 110;
int f[N][N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 1; j <= m; j ++) {
            for (int k = 0; k * v <= j && k <= s; k ++) 
                f[i][j] = max(f[i][j], f[i - 1][j - v * k] + w * k);
        }
    }
    
    cout << f[n][m];
    return 0;
}

一维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 20010;
int n, m;
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = m; j >= 0; j --)
            for (int k = 1; k <= s && v * k <= j; k ++)
                f[j] = max(f[j], f[j - v * k] + w * k);
    }
    cout << f[m];
    return 0;
}

二进制优化

物品i有数量si个时，可选的数量区间为[0,si]，物品i对最优解的贡献数量一定位于该闭区间内。是否存在一种优化，使得枚举该区间的所有数量值的复杂度优于O(n)？答案是使用二进制枚举。

将s个物品拆分成1，2，4，8，2^k，·······，c个，且1+2+4+8+2^k+c的和为s，可证明[0,si]区间内的所有数都可由这些数相加组成。将原有的n个数转化为logn个数的，再运用01背包思路求解这些数，可求出所有体积下应选该物品的数量和最大价值，时间复杂度将每个物品的O(n)优化到O(logn)。运用该二进制优化到所有的物品中，即可将多重背包转化成优化的01背包问题。套用01背包求解，即可得出答案。

难点：理解二进制优化的思想，为什么可以使用二进制优化？

代码一：将每个物品分割都记录下来，和思路一样。

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
#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    cin >> n >> m;
    int cnt = 0;
    while (n --) {
        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 <<= 1;
        }
        if (s > 0) {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    for (int i = 1; i <= cnt; i ++)
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[m];
    return 0;
}

代码二：将物品的每个分割不做记录直接计算，省一点空间，但比较绕一丢丢，需要深刻理解01背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 2010;
int n, m;
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w, s; cin >> v >> w >> s;
        int k = 1;
        while (k <= s) {
            for (int j = m; j >= v * k; j --)
                f[j] = max(f[j], f[j - v * k] + w * k);
            s -= k;
            k <<= 1;
        }
        if (s) 
            for (int j = m;  j >= v * s; j --)
                f[j] = max(f[j], f[j - v * s] + w * s);
    }
    cout << f[m];
    return 0;
}

单调队列优化

完全背包：求所有前缀的最大值

多重背包：求前一个区间的最大值

当计算f[i][j]时，由 f[i][j] = max(f[i][j], f[i - 1][j - v * s] + w * s)展开，可得如下：

f[i][j] = max(f[i-1][j], f[i-1][j-v] + w, f[i-1][j-2v]+2w, f[i-1][j-3v]+3w, ……, f[i-1][j-sv]+sw)

f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v] + w, f[i-1][j-3v] + 2w, ……, f[i-1][j-(s + 1)v] + sw)

f[i][j-2v] = ...

f[i][j-3v] = ...

将其不断展开，得出规律：j、j-v、j-2v、j-3v都是模v余r的数，且f[i,j]=max(f[i, j], max(f[i, j - v] + w, f[i, j - 2v] + 2w, ... , f[i, j - sv] + sw)+w)登前[j, j - sv]总共s项区间内的最值；f[i, j -v]=max(f[i, j - v], f[i, j - 2v] + w, f[i, j - 3v] + 2w, ... , f[i, j - (s + 1)v] + sw)也可取前[j - v, j - (s + 1)v]内的最大值，同理f[i, j - 2v]可取[j - 2v, j - (s + 2)v]共s个区间内的值，对连续区间内求区间最大值即滑动窗口，可用单调队列求解

image-20231009224923023

再求取f[i][j-v]时，可以使用单调队列维护f[i][j-v]使得查找该过程的复杂度为O(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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 20010;
int n, m;
int f[N], g[N], q[N];

int main () {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        int v, w, s; cin >> v >> w >> s;
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++) {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v) {
                while (hh <= tt && q[hh] < k - s * v) hh ++;
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt --;
                q[++ tt] = k;
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

5.4 分组背包

分组背包解决的是有n组，每组最多选一个物品，装进总容量为V的背包中，求最大价值。

状态表示：

  • 集合：f[i][j]：前i组背包中选，总体积不超过j的最大价值
  • 属性：Max

状态计算：

  • f[i][j] = max(f[i][j], f[i - 1][j])：当前i组不选
  • f[i][j]= max(f[i - 1][j], max(f[i - 1][j - vk] + wk))：当前i组选第i个

注意分组背包的题目中，要把物品输入用数组记录下来，不能一边输入一边计算，因为容量的遍历要在分组背包前。否则就是01背包不是分组背包了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> s[i];
        for (int j = 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 = 1; k <= s[i]; k ++)
                if (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    
    cout << f[m];
    return 0;
}

5.5 最长上升子序列

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 <iostream>
using namespace std;

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

/*
f[i] = max(f[i], f[j] + 1) (a[i] > a[j])
*/
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;
        for (int j = 1; j < i; j ++)
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++)
        res = max(res, f[i]);
        
    cout << res;
    return 0;
}

n log n：

单调优化：即f[i]为0~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
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;
int a[N];
int q[N];
int n;

int main()
{
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    
    
    q[0] = -2e9;
    int len = 0;
    for (int i = 0; i < n; i ++)
    {
        int l = 0, r = len;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    
    cout << len << endl;
    
    return 0;
}

5.6 最长公共子序列

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>
#include <algorithm>

using namespace std;

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

/*
f[i][j] = max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1)
*/
int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", 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;
}

5.7 区间DP-石子合并

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 <algorithm>

using namespace std;

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

/*
f[i][j] = min(f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
*/
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &s[i]);
    
    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] = 1e9;
            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;
}

5.8 计数DP

计数问题

求某个区间内的所有数字上0-9出现的次数。

考虑 abcdefg 中第四位上1出现的次数

  1. 如果前三位 = 0~abc-1, 那1的次数是： abc * 1000 （加入x = 0 时要从001开始，所以是 (abc -1) * 1000)
  2. 如果前三位 = abc：
    1. d < 1, 那么无论后面efg取什么，都是不符合：0
    2. d = 1, 后三位可取0~efg：efg+1
    3. d > 1, 后三位可取0~999：1000
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 <iostream>
#include <algorithm>

using namespace std;

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

int power10(int i) {
    int res = 1;
    while (i --) res *= 10;
    return res;
}
int count(int n, int x)
{
    if (!n) return 0;
    
    vector<int> v;
    for (; n; n /= 10)
        v.push_back(n % 10);
    
    n = v.size();
    int res = 0;
    for (int i = n - 1 - !x; i >= 0; i --)
    {
        if (i < n - 1) {
            res += get(v, i + 1, n - 1) * power10(i);
            if (!x) res -= power10(i);
        }
        // cout <<"--" << res << endl;
        if (v[i] == x) res += get(v, 0, i - 1) + 1;
        else if (v[i] > x) res += power10(i);
        // cout << "--" << res << endl;
    }
    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b, a || b)
    {
        if (a > b) swap(a, b);
        for (int i = 0; i < 10; i ++)
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }
    
    return 0;
}

5.9 状态压缩

状态压缩，将某一状态用二进制01表示，用十进制存储，从而可以快速利用与或非等位运算，优化时空复杂度。

状态压缩通常会在题目上给出范围，当数据范围小时，就可以考虑是否能运用状态压缩

例题：

蒙德里安的梦想

核心：先放横着的，再放竖着的。总的方案数等于合法的放置横着的方案数。

怎么判断横着的方案是否合法？所有列的竖着的连续空格是偶数个，才是合法

可以预处理一些状态，优化时间复杂度

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
/*
f[i][j]表示i-1列的横着放着的长方形伸到i列的状态为j的合法方案数
f[i][j] = sum(f[i-1][k]) (k & j == 0 && state[k|j])
*/

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

using namespace std;

typedef long long  LL;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
vector<int> state[M];
bool st[M];

int main()
{
    while (cin >> n >> m, n || m) {
        //预处理st：能否合法放置的列
        for (int i = 0; i < 1 << n; i ++)
        {
            int cnt = 0, is_vaild = true;
            for (int j = 0; j < n; j ++)
            {
                if ((i >> j) & 1) {
                    if (cnt & 1) { is_vaild = false; break; }
                    cnt = 0;
                } else cnt ++;
            }
            if (cnt & 1) is_vaild = false;
            st[i] = is_vaild;
            // cout << st[i] << " ";
        }
        
        //预处理两列伸出不重叠冲突
        for(int i = 0; i < 1 << n; i ++)
        {
            state[i].clear();
            for (int j = 0; j < 1 << n; j ++)
            {
                if ((i & j) == 0 && st[i | j])
                state[i].push_back(j);
            }
            // cout << state[i].size() << endl;
        }
        
        memset(f, 0, sizeof f);
        //dp
        f[0][0] = 1;
        for (int i = 1; i <= m; i ++)
            for (int j = 0; j < 1 << n; j ++)
                for (auto k : state[j])
                    f[i][j] += f[i - 1][k];
                    
        cout << f[m][0] << endl;
    }
}

最短Hamilton路径

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
/*
状态表示：f[i][j]:从0走到j点的路径经过的点集合为i的所有路径最短的长度
状态转移：f[i][j] = min(f[i-(j)][k]) + w[k][j], 枚举倒数第二个点k，表示从0走到k的点最小路径长度，再从k走到j点
*/

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

using namespace std;

const int N = 21, 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 ++)
        for (int j = 0; j < n; j ++)
            if (i >> j & 1)
                for (int k = 0; k < n; k ++)
                    if (i - (1 << j) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                        
    cout << f[(1 << n) - 1][n - 1];
    return 0;
}

5.10 树形DP

解决的是树形结构的问题：通过子树的状态，转移到当前树的状态

没有上司的舞会

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
/*
f[u][0]:表示以u为根节点的子树，不选u的最大值
f[u][1]:表示以u为根节点的子树，选u的最大值

f[u][0] = sum(max(f[j][0], f[j][1])): 	j为u的子节点
f[u][1] = happy[u] + sum(f[j][0]):		j为u的子节点
*/
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 6010;
int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_fat[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 != -1; 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);
        has_fat[a] = true;
        add(b, a);
    }
    
    int root = 1;
    while (has_fat[root]) root ++;
    
    dfs(root);
    
    printf("%d\n", max(f[root][1], f[root][0]));
}

5.11 记忆搜索

优势：代码简单

滑雪

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

using namespace std;

const int N = 310;
int n, m;
int h[N][N];
int f[N][N];

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

int dp(int x, int y)  
{
    int &v = f[x][y];
    if (v != -1) return v;
    
    v = 1;
    for (int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
            v = max(v, dp(a, b) + 1);
    }
    
    return v;
}
int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            scanf("%d", &h[i][j]);
    
    memset(f, -1, sizeof f);
    
    int res = -1;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            res = max(res, dp(i, j));
            
    cout << res <<endl;
    
    return 0;
}

5.12 数字三角形模型

6. 贪心

6.1 区间问题

区间问题的贪心，一般要以区间左端点或者区间右端点排序，再去尝试。

AcWing 算法基础

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！