洛谷之旅（to be continued...）

发表于 | 分类于

珂朵莉.jpg

【算法 1-1】模拟与高精度

  P1601、A+B Problem：高精加

1
2
3
4
5
6
7
8
void pplus(int* a, int* b){
    int carry = 0;
    for(int i = 0; i <= 502; i++){
        a[i] += b[i] + carry;
        carry = a[i] / 10;
        a[i] %= 10;
    }
}

  P1303、A*B Problem：高精乘

1
2
3
4
5
6
7
8
9
10
11
void ttimes(int* a, int* b, int* c){
    for(int i = 0; i < 2001; i++){
        for(int j = 0; j < 2001; j++){
            c[i+j] += a[i] * b[j];
            if(c[i+j] >= 10){
                c[i+j+1] += c[i+j] / 10;
                c[i+j] %= 10;
            }
        }
    }
}

  P1009、阶乘之和：高精乘 + 高精加

1
2
3
4
5
6
7
8
void times(int* a, int k){
    int carry = 0;
    for(int i = 0; i < 2001; i++){
        a[i] = a[i] * k + carry;
        carry = a[i] / 10;
        a[i] %= 10;
    }
}

  P1591、阶乘数码：高精乘，遍历计数
  P1045、麦森数：高精乘，取后 500 位即可
  P1249、最大乘积：因数越多乘积越大，和比该数大一则去掉 2，末因数 + 1；和比该数大 k 则去掉 k；注意 3 和 4 两个特例
  P5461、赦免战俘：分形题，经典递归

【算法 1-2】排序

  P1271、选举学生会：桶计数
  P1177、快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void qsort(int L, int R){
    int mid = a[L + (R - L) / 2];
    int i = L, j = R;
    do{
        while(a[i] < mid) i++;
        while(a[j] > mid) j--;
        if(i <= j){
            swap(a[i], a[j]);
            i++; j--;
        }
    }while(i <= j);
    if(i < R) qsort(i, R); 
    if(j > L) qsort(L, j); 
}

  P1923、求第 k 小的数：经典 kth 问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void findKth(int L, int R){
    int mid = a[L + (R - L) / 2];
    int i = L, j = R;
    do{
        while(a[i] < mid) i++;
        while(a[j] > mid) j--;
        if(i <= j){
            swap(a[i], a[j]);
            i++; j--;
        }
    }while(i <= j);
    if(k <= j) findKth(L, j);
    else if(k >= i) findKth(i, R);
    else{
        printf("%d", a[j + 1]);
        return;
    }
}

  P1093、奖学金：结构体排序
  P1781、宇宙总统：结构体排序
  P1068、分数线划定：结构体排序
  P5143、攀爬者：结构体排序
  P1104、生日：结构体排序，注意 c++ 中稳定排序为 stable_sort()
  P1012、拼数：注意本题非贪心，不能简单用字典序排序；本题使用了一个巧妙的字符串拼接比较方法

1
2
3
4
5
6
struct node{
    string s;
    inline bool operator<(const node &t) const{
        return s + t.s > t.s + s;
    }
}p[21];

  P1908、逆序对：基于相邻元素比较的排序算法中元素交换次数，本题数据规模大，使用归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void msort(int L, int R){
    if(L == R)
        return;
    int mid = L + (R - L) / 2;
    msort(L, mid); msort(mid + 1, R);
    int i = L, j = mid + 1, cur = L;
    while(i <= mid && j <= R){
        if(a[i] <= a[j])
            b[cur++] = a[i++];
        else{
            b[cur++] = a[j++];
            res += mid - i + 1; // 逆序数
        }
    }
    while(i <= mid) b[cur++] = a[i++];
    while(j <= R) b[cur++] = a[j++];
    for(int i = L; i <= R; i++)
        a[i] = b[i];
}

【算法 1-3】暴力枚举

  P2241、统计方形：遍历长宽，相等即方形，乘数计数
  P2089、烤鸡：约束型 dfs，全遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int sum){
    if(tmp.size() == 10){
        if(sum == n){
            res.push_back(tmp);
            cnt++;
        }
        return;
    }
    for(int i = 1; i <= 3; i++){
        if(sum + i > n || 9 + i > n) break;
        tmp.push_back(i);
        dfs(sum + i);
        tmp.pop_back();
    }
}

  P1618、三连击（升级版）：暴力 9 位数全排列即可
  P1036、选数：dfs，无重升序扫描，因为不需要保存路径所以 dfs 的过程可以简化

1
2
3
4
5
6
7
8
void dfs(int dep, int sum, int left){
    if(dep == k){
        if(isPrime(sum)) res++;
        return;
    }
    for(int i = left; i < n; i++)
        dfs(dep + 1, sum + a[i], i + 1);
}

  P1157、组合的输出：无重升序扫描，模板题

1
2
3
4
5
6
7
8
9
10
11
void dfs(int left){
    if(tmp.size() == k){
        res.push_back(tmp);
        return;
    }
    for(int i = left; i <= n; i++){
        tmp.push_back(i);
        dfs(i + 1);
        tmp.pop_back();
    }
}

  P1706、全排列问题：全排列模板题，可以用 next_permutation 逃课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(){
    if(tmp.size() == n){
        res.push_back(tmp);
        return;
    }
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            vis[i] = 1;
            tmp.push_back(i);
            dfs();
            tmp.pop_back();
            vis[i] = 0;
        }        
    }
}

  P1088、火星人：全排列的第 k 种情况，dfs 或逃课
  P3392、涂国旗：三重循环暴力枚举
  P3654、First Step：网格搜索，注意是直线，不能在 dfs 内部扩展

1
2
3
4
5
6
7
8
9
void dfs(int x, int y, int sum, int pos){
    if(mat[x][y] != '.' || x >= n || y >= m)
        return;
    if(sum == k){
        res++;
        return;
    }
    dfs(x + dx[pos], y + dy[pos], sum + 1, pos);
}

  P1217、回文质数：埃筛判断是否为回文数即可
  P1149、火柴棒等式：打表，暴力枚举即可
  P3799、妖梦拼木棒：暴力枚举两条短边
  P2036、PERKET：dfs，每个状态结点分选和不选两种状态，决策树的雏形

1
2
3
4
5
6
7
8
9
10
void dfs(int dep, int sour, int bitter){
    if(dep == n){
        if(sour == 1 && bitter == 0)
            return;
        res = min(res, abs(sour - bitter));
        return;
    }
    dfs(dep + 1, sour, bitter);
    dfs(dep + 1, sour * a[i], bitter + b[i]);
}

【算法 1-4】递推与递归

  

【算法 1-6】二分查找与二分答案

  二分答案的标准例程

1
2
3
4
5
6
7
while(L <= R){
    int mid = L + (R - L) / 2;
    if(judge(mid)) // pass
        L = mid + 1;
    else R = mid - 1;
}
printf("%d", R); // 视题意取 L 或 R

  P2249、【深基13.例1】查找：有序数组二分查找

1
2
3
4
5
6
7
8
9
10
int bfind(int L, int R, int k){
    while(L <= R){
        int mid = L + (R - L) / 2;
        if(a[mid] < k)
            L = mid + 1;
        else R = mid - 1;
    }
    if(a[L] == k) return L;
    return -1;
}

  P1102、A-B 数对：转换为 A - C = B，标准 $f(X)\in X$ 问题

1
2
3
4
5
6
7
for(int i = 0; i < n; i++){
    a[i] = read();
    mat[a[i]]++;
    a[i] -= c; // 
}
for(int i = 0; i < n; i++)
    res += mat[a[i]];

  P1873、砍树：二分答案

1
2
3
4
5
6
7
8
9
10
while(L <= R){
    long long mid = L + (R - L) / 2, tmp = 0;
    for(int i = 0; i < n; i++)
        if(a[i] > mid)
            tmp += a[i] - mid;
    if(tmp < m) // 保证 R 是个可行解
        R = mid - 1;
    else L = mid + 1;
}
printf("%lld", R); // R = L - 1

  P1678、烦恼的高考志愿：查询前驱即可，善用 STL 逃课，lower_bound(a + 1, a + 1 + n, t) - a - 1 指示前驱位置；upper_bound(a + 1, a + 1 + n, t) - a 指示后继位置
  P2440、木材加工：二分答案
  P2678、跳石头：双指针扫描，贪心删数（删当前数右边一位）；二分答案求最短跳跃距离的最大值
  P3853、路标设置：二分答案
  P1182、数列分段 Section II：二分答案

【算法 1-7】搜索

  P1219、八皇后：经典 dfs，八皇后的线性 vis 很值得回味

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int row){
    if(row > n){
        print();
        return;
    }
    for(int col = 1; col <= n; col++){
        if(!(b[col] || c[row + col] || d[row - col + n])){
            a[row] = col;
            b[col] = 1;
            c[row + col] = 1;
            d[row - col + n] = 1;
            dfs(row + 1);
            b[col] = 0;
            c[row + col] = 0;
            d[row - col + n] = 0;
        }
    }
}

【数据结构 1-1】线性表

P3156、询问学号：签到题 P3613、寄包柜：数据稀疏，使用哈希

1
2
3
struct node{
    map<int, int> mat;
}desk[100005]; // 第 i 个柜子的第 j 个格子放了 k 个物品

P1449、后缀表达式：栈经典习题

1
2
3
4
5
6
7
8
9
10
11
12
// 3.233.+5.*156.-
while(scanf("%c", &c) && c != '@'){
    switch(c){
        case '+': x = s.top(); s.pop(); y = s.top(); s.pop(); s.push(x + y); break;
        case '-': x = s.top(); s.pop(); y = s.top(); s.pop(); s.push(y - x); break;
        case '*': x = s.top(); s.pop(); y = s.top(); s.pop(); s.push(x y); break;
        case '/': x = s.top(); s.pop(); y = s.top(); s.pop(); s.push(y / x); break;
        case '.': s.push(t); t = 0; break;
        default: t = t 10 + c - '0'; break;
    }
}
printf("%d", s.top());

P1996、约瑟夫问题：队列经典习题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 1; i <= n; i++)
    q.push(i);
while(!q.empty()){
    if(cnt % m != 0){
        cnt++;
        q.push(q.front());
        q.pop();
    }
    else{
        cnt = 1;
        printf("%d ", q.front());
        q.pop();
    }
}

P1160、队列安排：频繁的插入删除，链表题

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
struct node{
    int L, R;
    bool flag; // lazy delete
}list[100005];

void insert(int pos, int k, int f){
    if(f){
        list[k].R = list[pos].R;
        list[pos].R = k;
        list[k].L = pos;
        list[list[k].R].L = k;
    }
    else{
        list[k].L = list[pos].L;
        list[pos].L = k;
        list[k].R = pos;
        list[list[k].L].R = k;
    }
}

insert(0, 0, 1); // dummy
// 以哑结点为起点进行遍历
for(int i = list[0].R; i; i = list[i].R){
    if(!list[i].flag)
        printf("%d ", i);
}

P1540、机器翻译：页面置换，由于涉及到遍历查找，使用 vector 模拟队列

1
2
3
vector<int> v;
v.erase(v.begin()); // q.pop()
v.push_back(t);

P2058、海港：顺序维护区间无重复计数，使用队列存储，判断队首元素是否满足区间要求；使用桶来完成计数

1
2
3
4
5
int mat[1000005]; // 桶
struct node{
    int s, t; // 国籍、到达时间
};
queue<node> q;

P1241、括号序列：对每一个右括号，找到在它左边最靠近它的左括号匹配，不匹配则补全；扫描，左括号入栈，右括号看是否和栈顶符号匹配

1
2
3
4
5
6
7
8
9
10
11
12
stack<int> st;
bool ok[105]; string s;

int id(char c){
    switch(c){
        case '(' : return -2;
        case '[' : return -1;
        case ']' : return 1;
        case ')' : return 2;
        default  : return 0;
    }
}

P4387、验证栈序列：栈模拟

1
2
3
4
5
6
7
8
9
for(int i = 0; i < n; i++){
    s.push(a[i]);
    while(s.top() == b[cur]){
        s.pop(); cur++;
        if(s.empty()) break;
    }
}
if(s.empty()) printf("Yes\n");
else printf("No\n");

P2234、营业额问题：大规模数据，多次查找某数的前驱和后继，该题数据使用 BST 会卡常，需要使用平衡树，可用 multiset 逃课

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
multiset<int> s;
multiset<int>::iterator it;

int queryVal(int x){
    it = s.lower_bound(x);
    multiset<int>::iterator i = s.begin();
    int pos = 0;
    while(i != it){
        pos++;
        i++;
    }
    return pos;
}

int queryKth(int k){
    int pos = 0;
    it = s.begin();
    while(pos != k){
        pos++;
        it++;
    }
    return *it;
}

// 注意！multiset 和 set 查找前驱后继的方式是不同的
int queryNext(int x, int f){
    if(f == 0){
        it = s.lower_bound(x);
        it--;
        return *it;
    }
    else{
        it = s.upper_bound(x);
        return *it;
    }
}

【数据结构 1-2】二叉树

P4715、淘汰赛：亚军，平分后在线选取左/右最大元素比较即可
P4913、二叉树深度：签到题
P1827、美国血统：给出中序和前序遍历，求后序遍历，经典递归习题，注意子树的字串长是相同的

1
2
3
4
5
6
7
void postOrder(string in, string pre){
    if(pre.size() == 0) return;
    int pos = in.find(pre[0]); // 根的位置
    postOrder(in.substr(0, pos), pre.substr(1, pos));
    postOrder(in.substr(pos + 1), pre.substr(pos + 1));
    printf("%c",  pre[0]);
}

P5076、普通二叉树（简化版）：二叉搜索树 BST 模板题，偷懒可用 multiset 逃课

1
// TODO: 等一个 BST 模板

P1364、医院设置：带权树的重心，本题数据很水，可用 Floyd 逃课

1
// TODO: 等一个树的重心标程

P1229、遍历问题：给出前序和后序遍历，求中序遍历有几种情况，显然只要存在单子节点即有两种情况

1
2
3
4
5
6
7
8
// ab, ba -> 单子节点
int res = 1, len = a.size();
for(int i = 0; i < len - 1; i++){
    for(int j = 1; j < len; j++){
        if(a[i] == b[j] && a[i + 1] == b[j - 1])
            res *= 2;
    }
}

P1305、新二叉树：前序遍历，签到题
P1030、求先序排列：给出中序和后序遍历，求先序遍历，经典递归习题

1
2
3
4
5
6
7
8
void preOrder(string in, string post){
    if(post.size() == 0) return;
    int len = post.size();
    int pos = in.find(post[len - 1]);
    printf("%c", post[len - 1]);
    preOrder(in.substr(0, pos), post.substr(0, pos));
    preOrder(in.substr(pos + 1), post.substr(pos, len - pos - 1));
}

P3884、二叉树问题：求二叉树深度、宽度、节点间距离，经典树习题

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
int maxDepth(int root){
    if(root == 0) return 0;
    return 1 + max(maxDepth(BTree[root].L), maxDepth(BTree[root].R));
}

// dfs 用桶存储每层宽度，数据量大的时候建议 bfs
void dfs(int root, int level){
    if(root == 0) return;
    bucket[level] += 1;
    dfs(BTree[root].L, level + 1);
    dfs(BTree[root].R, level + 1);
}

int maxWidth(int root, int cnt){
    dfs(root, 1);
    int _max = 0;
    for(int i = 1; i <= cnt; i++){
        if(bucket[i] > _max)
            _max = bucket[i];
    }
    return _max;
}

int lca(int root, int p, int q){
    if(root == 0) return 0;
    if(root == p || root == q) return root;
    int L = lca(BTree[root].L, p, q);
    int R = lca(BTree[root].R, p, q);
    if(L != 0 && R != 0) return root;
    if(L != 0 && R == 0) return L;
    if(L == 0 && R != 0) return R;
    return 0; 
}

int distance(int root, int pos, int dis){
    if(root == 0) return 0;
    if(root == pos) return dis;
    return max(distance(BTree[root].L, pos, dis + 1), distance(BTree[root].R, pos, dis + 1));
}

// dis = distance(_lca, a, 0) + distance(_lca, b, 0)

P3369、普通平衡树：splay 模板题

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
int root, snt, n, opt, num;
struct node{
    int father; // 父节点
    int val; // 权值
    int siz; // 子树节点个数，包含等值节点和子树根
    int cnt; // 等值节点个数
    int ch[2]; // 左右子节点
}sp[100005];

void update(int pos){
    sp[pos].siz =  sp[sp[pos].ch[0]].siz + sp[sp[pos].ch[1]].siz + sp[pos].cnt;
}

int identify(int pos){
    return sp[sp[pos].father].ch[0] == pos? 0 : 1;
}

void connect(int pos, int fa, int son){
    sp[pos].father = fa;
    sp[fa].ch[son] = pos;
}

void rotate(int pos){
    int y = sp[pos].father;
    int R = sp[y].father;
    int Rson = identify(y);
    int yson = identify(pos);
    int B = sp[pos].ch[yson ^ 1];
    connect(B, y, yson); connect(y, pos, yson ^ 1);
    connect(pos, R, Rson);
    update(y); update(pos);
}

void splay(int pos, int goal){
    while(sp[pos].father != goal){
        int up = sp[pos].father;
        if(sp[up].father == goal)
            rotate(pos);
        else if(identify(pos) == identify(up)){
            // 一子形上旋
            rotate(up); rotate(pos);
        }
        else{
            // 之字形上旋
            rotate(pos); rotate(pos);
        }
    }
    if(goal == 0)
        root = pos; // 上旋至根节点
}

void insert(int x){
    int u = root, fa = 0;
    while(u && sp[u].val != x){
        fa = u;
        u = sp[u].ch[x > sp[u].val]; // 大于则右插
    }
    if(u)
        sp[u].cnt++; // 有等值节点
    else{
        u = ++snt;
        if(fa) sp[fa].ch[x > sp[fa].val] = u;
        sp[snt].ch[0] = sp[snt].ch[1] = 0;
        sp[snt].father = fa; sp[snt].val = x;
        sp[snt].siz = sp[snt].cnt = 1;
    }
    splay(u, 0);
}

// 查询树中已存在值 x
void queryVal(int x){
    int u = root;
    if(!u) return;
    while(sp[u].ch[x > sp[u].val] && x != sp[u].val)
        u = sp[u].ch[x > sp[u].val];
    splay(u, 0);
}

// 查询某值的前驱或后继
int queryNext(int x, int f){
    queryVal(x);
    int u = root;
    if((sp[u].val > x && f) || (sp[u].val < x && !f))
        return u;
    u = sp[u].ch[f];
    while(sp[u].ch[f ^ 1])
        u = sp[u].ch[f ^ 1];
    return u;
}

void del(int x){
    int pre = queryNext(x, 0);
    int post = queryNext(x, 1);
    splay(pre, 0); splay(post, pre);
    int d = sp[post].ch[0];
    if(sp[d].cnt > 1){
        sp[d].cnt--;
        splay(d, 0);
    }
    else sp[post].ch[0] = 0;
}

int queryKth(int k){
    int u = root;
    if(sp[u].siz < k) return -1;
    while(true){
        int y = sp[u].ch[0];
        if(k > sp[y].siz + sp[u].cnt){
            k -= sp[y].siz + sp[u].cnt;
            u = sp[u].ch[1];
        }
        else if(k <= sp[y].siz)
            u = y;
        else return sp[u].val;
    }
}

insert(-2147483647);
insert(+2147483647); // 删除需要前驱和后继，因此预先插入 INF 定区间

【数据结构 1-3】集合

P1551、亲戚：并查集模板题，find(i) 表示 i 节点的祖先节点

1
2
3
4
5
6
7
8
9
10
11
12
13
int find(int pos){
    int root = pos, tmp;
    while(root != a[root])
        root = a[root];
    while(pos != a[pos]){
        tmp = a[pos];
        a[pos] = root;
        pos = tmp;
    }
    return root;
}

a[find(t1)] = find(t2); // 祖先节点合并

P1536、村村通：并查集，祖先节点个数减一即修路条数
P3370、字符串哈希：模板题，进制哈希，可使用 unsigned long long 自然溢出自动对 2^64-1 取模；哈希题偷懒可用 unordered_map 逃课

1
2
3
4
5
6
7
8
9
10
// base == 131
ull hash(string s){
    ull val = 0;
    for(int i = 0; i < s.size(); i++)
        val = val base + (ull)s[i];
    return val;
}

unordered_map<string, int> mat;
mat.size();

P3405、Cities and States S：逆序对计数

1
2
3
4
5
6
7
// 双字母进制哈希
int A = (a[0] - 'A') 26 + a[1] - 'A';
int B = (b[0] - 'A') 26 + b[1] - 'A';
if(A != B){
    mat[A][B]++;
    res += mat[B][A];
}

P5250、木材仓库：set 练习题，也可作为平衡树练习题
P5266、学籍管理：map 练习题，unordered_map 的查找性能要远优于 map
P1102、A-B 数对：R(S) = S，用桶保存结果比较即可；数据规模过大时使用哈希表代替桶
P1918、保龄球：高性能查找，BST 和二分查找的练习题，偷懒可以用 map 逃课
P1525、关押罪犯：贪心，尽可能让愤怒值高的罪犯不共边，并查集补集思想，敌人的敌人就是我们的朋友

1
2
3
// 补集并查集大小开为普通的二倍
a[find(p[i].x + n)] = find(p[i].y);
a[find(p[i].y + n)] = find(p[i].x);

P1621、集合：埃筛 + 并查集，注意是公共质因数，唯一分解定理可证明这种算法的正确性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
res = m - n + 1;
for(int i = 2; i <= m; i++){
    if(!b[i]){
        if(i >= p){
            for(int j = i 2; j <= m; j += i){
                b[j] = true;
                if(j - i >= n && find(j) != find(j - i)){
                    res--;
                    a[find(j)] = find(j - i);
                }
            }
        }
        else{
            for(int j = i 2; j <= m; j += i)
                b[j] = true;
        }
    }
}

P1892、团伙：并查集补集问题
P1955、程序自动分析：大范围数据，离散化 + 并查集，很不错的练习题

1
2
3
4
5
6
sort(b, b + tot); // 排序
int cps = unique(b, b + tot) - b; // 去重
for(int i = 1; i <= n; i++){ // 重定位
    p[i].x = lower_bound(b, b + cps, p[i].x) - b;
    p[i].y = lower_bound(b, b + cps, p[i].y) - b;
}

P4305、不重复数字：结构体离散化应用，本题也可作为哈希表练习题
P3879、阅读理解：map 练习题，也可以做 Trie 树练习题

1
2
// 单词 string 所在行数存于 vector
unordered_map<string, vector<int>> mat;

P2814、家谱：哈希表 + 并查集

【数据结构 1-4】图的基本应用

P5318、查找文献：图的 dfs 与 bfs，涉及了节点排序不建议使用链式前向星
P3916、图的遍历：能到达的最大的节点，反向建边 + dfs

1
2
3
4
5
6
7
8
int vis[100005];
// 按节点从大到小 dfs
void dfs(int pos, int val){
    if(vis[pos]) return;
    vis[pos] = val;
    for(int i = 0; i < edge[pos].size(); i++)
        dfs(edge[pos][i], val);
}

P1113、杂务：拓扑排序，因为本题数据输入是有序的，可以不建图在线 dp，转移方程为 dis[v] = max(dis[v], dis[u] + w[v])
P4017、最大食物链计数：拓扑，转移方程为 f[v] = f[v] + f[u]
P1807、最长路：拓扑，转移方程为 dis[v] = max(dis[v], dis[u] + w[v])，注意事先要删除除 1 外入度为零的节点，生成单源图

1
2
3
4
5
6
7
8
// 去除非 1 源节点生成单源图
for(int i = 2; i <= n; i++){
    dis[i] = -1;
    if(ind[i] == 0){
        for(int e = head[i]; e; e = edge[e].next)
            ind[edge[e].to]--;
    }
}

P2853、Cow Picnic S：dfs，可抵达数等于牛数目即该节点可被所有牛访问

【数据结构 2-1】二叉堆与 ST 表

【动态规划】动态规划的引入

P1048、采药：01 背包，逆推，dp[j] = max(dp[j], dp[j - w[j]] + v[j])
P1616、疯狂的采药：完全背包，顺推，dp[j] = max(dp[j], dp[j - w[j]] + v[j])
P1115、最大子段和：经典 DP，可以在线处理，状态决策为 t > t + maxCur
P2392、kkksc03考前临时抱佛脚
P1216、数字三角形：当前层数值只与上一层数值及其左边一位数有关，所以可以在线 DP 逆推，转移方程为 dp[i] = a[i] + max(dp[i], dp[i - 1])
P1434、滑雪：记忆化 + 暴搜，记忆化顾名思义即开辟一个额外的答案数组实时存储 dfs 的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[105][105], f[105][105];
// 网格搜索
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int dfs(int x, int y){
    if(f[x][y]) return f[x][y];
    f[x][y] = 1;
    for(int i = 0; i < 4; i++){
        int tx = x + dx[i];
        int ty = y + dy[i];
        if(tx && ty && tx <= n && ty <= m && a[x][y] > a[tx][ty]){
            dfs(tx, ty);
            // dfs 的特性，f[tx][ty] 会优先展开
            f[x][y] = max(f[x][y], f[tx][ty] + 1);
        }
    } 
}
return f[x][y];

P2196、挖地雷：前驱节点要在后继节点之前遍历完毕，转移方程为 f[v] = max(f[v], f[u] + a[v])，用 pre 数组存储路径前驱

1
2
3
4
5
6
7
8
9
10
11
// 注意外循环为后继节点
for(int v = 1; v <= n; v++){
    for(int u = 1; u < v; u++){
        if(edge[u][v]){
            if(f[v] < f[u] + a[v]){
                f[v] = f[u] + a[v];
                pre[v] = u;
            }
        }
    }
}

P1802、5 倍经验日：01 背包，dp[j] = max(dp[j] + lose[i], dp[j - use[i]] + win[i]);，注意打不赢都要加上输掉的经验
P1002、过河卒：棋盘 DP，注意限制条件
P1521、求逆序对