算法板子+期末考试题（回忆版

Connor
  2026-01-25 00:04:07 2026-01-25 00:04:07 Created   2026-01-27 02:15:15 2026-01-27 02:15:15 Updated    

说在前面

24级的算法考试相较于23级来说，去掉了很多送分的傻瓜题，总的来说难度不是很低

大一的程设和数据结构都是要求用C做的，不讲C++，但是到了大二的算法不会C++做题会很吃力。不过这学期现学也是来得及的！从做算法题的角度上说，C++要学的东西不是很多。个人建议尽量早点学会C++（最起码在讲到图论之前！用C做图论题会吐血的

要注意，机房的电脑很可能vscode是只能运行C而运行不了C++的！要解决这个问题，你需要：

如果vscode没有compilerun只有runcode，但是点了运行报错的话，点那个报错弹窗的debug，把里面的gcc改成g++就能运行cpp代码了

当然，你也可以选择使用dev来写，但是众所周知用dev写起来会很吃力（
但dev也不能直接用，不然的话是用不了auto,for循环冒号这些语法的，也需要配置！
如果想用dev，下面的板子的c++部分的配置dev那里有完整的步骤

以上配置步骤建议自己用机房的电脑试一下

24级算法考试我还能回想到的考试题放在最后了

下面是我考试前打印出来的板子（转成PDF只有六十多页，已经算相对偏少了（

用Obsidian整理好板子后，可以用Ob的插件Table of Contents生成目录，再转成PDF，用WPS来插入页号，最后打印出来再在目录上写上对应的页号

Hexo不自带渲染数学公式的配置，所以下面的数学公式都是渲染前的样子😟，有需要的话可以复制到Obsidian（更推荐）或者typora来看

最后，重中之重！！一定要确保板子的正确性！建议整理板子的时候把代码发给AI来确认是不是正确的！考试的时候敲了半天板子，一运行发现是错的，真的会绝望的。。。

下面是板子

一些常识知识：

  1. $o \approx <$ ; $O \approx \leq$ ; $\Theta \approx =$ ; $\Omega\approx\geq$ ; $\omega\approx>$
  2. $1<\log n < \sqrt n < n < n\log n < n^2 < n^3 < \dots < 2^n < 3^n <\dots < n^n$
  3. 图灵机提出 “状态自动转移” 的指令逻辑，但无法存储指令、缺乏程序结构；
  4. 冯诺依曼体系通过 “程序数据存储” 解决图灵机缺陷，奠定现代计算机硬件基础，而硬件的运算规则（如逻辑 / 算术运算）本质也是算法。

领域核心人物 ：

人物 核心贡献 荣誉与代表作
Donald E. Knuth（高德纳） 1. 算法与程序设计理论先驱；
2. 发明计算机排版系统 TEX/METAFONT；
3. 提出 “分析算法的双重幸福”（数学美 + 实际价值）		 1974 年图灵奖；
代表作《计算机程序设计艺术》（被誉为 “计算机程序设计理论的荷马史诗”）
Nicklaus Wirth（尼古拉斯・沃斯） 1. 提出 “程序 = 数据结构 + 算法”（媲美物理学 “E=MC²”）；
2. 设计 Pascal 编程语言；
3. 推动结构化程序设计		 1984 年图灵奖；

奠定程序设计的核心逻辑框架
Alan Turing（图灵） 提出图灵机模型，定义 “可计算性”，为算法理论奠定数学基础 计算机科学之父，图灵奖以其命名
John Von Neumann（冯诺依曼） 提出 “程序数据存储” 思想，解决图灵机缺陷，奠定现代计算机硬件架构 冯诺依曼体系创始人

一些特殊时间复杂度：

  1. f(n) = f(n-1) + f(n-2) $\rightarrow$ T = $(1.618)$$^n$

  2. $T(n)=\left{ \begin{array}{l} 1 , n=1 \ T(n-1)+1 , n>1 \end{array} \right.$ $\rightarrow$ T(n) = n

  3. $T(n)=\left{ \begin{array}{l} 1 , n=1 \ 2T(n/2)+1 , n>1 \end{array} \right.$ $\rightarrow$ T(n) = $n\log n + n$

  4. $T(n)=\left{ \begin{array}{l} 1 , n=1 \ T(\sqrt n)+1 , n>1 \end{array} \right.$ $\rightarrow$ T(n) = $\log \log n$

  5. $T(n)=\left{ \begin{array}{l} 1 , n=1 \ T(n/3)+T(2n/3)+n , n>1 \end{array} \right.$ $\rightarrow$ T(n) = $\Theta(n\log n)$

P、NP、NPC、NPH

1. 复杂性等级 (Complexity Classes)

  • P (Polynomial): 易解。存在多项式时间算法能直接求出答案。
  • NP (Nondeterministic Polynomial): 易验证。虽然不一定能快点算出来，但如果给你一个解，你可以在多项式时间内验证它是否正确。
  • NP-Complete (NPC): NP中最难的问题。
    • 特征：如果能解决任何一个 NPC 问题，就能解决所有 NP 问题。
  • NP-Hard (NPH): 至少和 NPC 一样难。它不一定属于 NP（甚至可能无法验证），但所有 NP 问题都能归约到它。

2. 归约 (Reduction) 的逻辑

  • 概念： 问题 $A \leq_p$ 问题 $B$。含义是“利用解决 $B$ 的能力来解决 $A$”。
  • 结论： $B$ 的难度 $\geq A$ 的难度。
    • 若 $A$ 是难的（NPC），则 $B$ 也是难的（NP-Hard）。
    • 若 $B$ 是简单的（P），则 $A$ 也是简单的（P）。

二、 关键人物与标志性事件

人物 考点标签 核心贡献
Rivest, Shamir, Adleman RSA加密 利用“大数分解质因数”的计算困难性发明了非对称加密。
Stephen Cook (库克) SAT问题 / 库克定理 证明了 SAT（布尔可满足性问题） 是第一个 NPC 问题。
Richard Karp (卡普) 21个NPC问题 通过归约法证明了团、覆盖、哈密顿路径等 21 个经典问题均为 NPC。

三、 经典例子与对比总结

选择题常通过“相似但不同”的描述设陷阱，请记住以下分类：

1. P 类问题（看到它们就选“容易”、“多项式时间可解”）

  • 图论： 最短路径 (Dijkstra)、最小生成树 (MST)、欧拉回路（走过每条边）。
  • 数学： 最大公约数 (GCD)、素数判定 (AKS算法)、大数相乘、模幂运算 ($a^b \bmod n$)。
  • 其他： 字符串匹配 (KMP)、排序算法。

2. NP-Complete / NP-Hard 问题（看到它们选“目前难解”、“NPC”）

  • 路径类： 哈密顿回路（走过每个点）、最长简单路径、旅行商问题 (TSP)。
  • 逻辑类： SAT、3-SAT（注：2-SAT 是 P 问题）。
  • 集合类： 团问题 (Clique)、顶点覆盖 (Vertex Cover)、独立集问题。
  • 数值类： 子集和问题、背包问题。

3. 特殊案例：大数分解 (Integer Factorization)

  • 分类： 属于 NP，但目前不确定它是否属于 NPC。
  • 应用： RSA 算法的安全性依赖于“分解大数”没有多项式时间解法。

四、 考试易错命题点拨

  1. 关于 $P$ 与 $NP$：
    • 错项： “NP 问题是不可解的问题”。（纠正： NP 只是没找到快速解法，但能快速验证）。
    • 错项： “如果 $P \neq NP$，那么 NP 问题都不能在多项式时间内求解”。（纠正： P 里的问题也是 NP 问题，它们能被快速求解）。
  2. 关于 RSA：
    • 易解的部分： 找大素数（概率算法）、模幂运算（快速幂）、求模逆元（扩展欧几里得）。
    • 难解的部分： 已知 $n$ 求 $p, q$（大数分解）、已知密文在不知道私钥的情况下求明文。

c++

配置dev

解决方法：开启 C++11 标准
打开编译选项： 在菜单栏点击 工具 (Tools) -> 编译选项 (Compiler Options)。

勾选命令参数： 在弹出的窗口中，选中第一个选项卡 编译器 (Compiler)。 勾选 “在连接器命令行加入以下命令” (Add the following commands when calling the compiler)。

输入命令： 在下方的输入框中填入： -std=c++11 (注意要删掉-static-lbgcc一整行，如果你想支持更现代的语法，也可以填入 -std=c++14 或 -std=c++17)。

确认保存： 点击底部的 确定 (OK)。

重新编译： 重新按下 F11 (编译运行)，程序应该就能顺利通过并运行了。

字符串

1
2
3
4
5
s.substr(pos, len); //取子串
s.find("abc");  //查找
s.find('a');

if (s.find("abc") != string::npos)//表示找到！

字符串split

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<string> split(const string& s, char delim) {
    vector<string> res;
    string cur;
    for (char c : s) {
        if (c == delim) {
            if (!cur.empty()) res.push_back(cur);
            cur.clear();
        } else {
            cur.push_back(c);
        }
    }
    if (!cur.empty()) res.push_back(cur);
    return res;
}

字符串去前后空格

1
2
3
4
5
6
string strip(const string &s){
	int l = 0, r = s.size() - 1;
	while(l <= r && isspace(s[l])) l++;
	while(l <= r && isspace(s[r])) r--;
	return s.substr(l, r - l + 1);
}

二分查找

C

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
int upper_bound(int a[], int n, int x) {
    int left = 0, right = n;  // 注意 right = n

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] <= x)
            left = mid + 1;
        else
            right = mid;
    }
    return left;  // 第一个 > x 的位置（可能等于 n）
}

int lower_bound(int a[], int n, int x) {
    int left = 0, right = n;  // 注意 right = n

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < x)
            left = mid + 1;
        else
            right = mid;
    }
    return left;  // 可能等于 n
}

while (left <= right) {
	int mid = left + (right - left) / 2;
	if (check(mid)) {
		ans = mid;
		right = mid - 1;
	} else {
		left = mid + 1;
	}
}//满足check(x) == true的最小的ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
// 在升序序列中找第一个 > val 的位置
auto it = upper_bound(begin, end, val); 

// 在降序序列中找第一个 < val 的位置 (需要配合 greater)
auto it = upper_bound(begin, end, val, greater<int>());

// 在升序序列中找第一个 >= val 的位置
auto it = lower_bound(begin, end, val); 

// 在降序序列中找第一个 <= val 的位置 (需要配合 greater)
auto it = lower_bound(begin, end, val, greater<int>());

string和char*

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include<string>

using namespace std;

int main(){
    char* c = "hello, world";
    // char* -> string
    string s = c;
    cout << s << endl;
	// string -> char*
    printf("%s", s.c_str());
}

快速幂

1
2
3
4
5
6
7
8
9
long long binpow(long long a, long long b, long long p) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
void insertSort(vector<int>& k,int n){  
	int temp;
    int j;
    for(int i = 1; i < n; i++){
        temp = k[i];
        for(j = i - 1; j >= 0 && temp < k[j]; j--){
            k[j + 1] = k[j];
        }
        k[j + 1] = temp;
    }
}

归并排序

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

using namespace std;

using keytype = int;
void insertSort(keytype k[ ],int n){  
	keytype temp;
    int j;
    for(int i = 1; i < n; i++){
        temp = k[i];
        for(j = i - 1; j >= 0 && temp < k[j]; j--){
            k[j + 1] = k[j];
        }
        k[j + 1] = temp;
    }
}
int tmp[50005];
void Merge(int a[], int l, int m, int r){
    int i = l, j = m + 1, k = i;
    while(i <= m && j <= r){
        if(a[i] <= a[j]){
            tmp[k++] = a[i++];
        }else
            tmp[k++] = a[j++];
    }

    while(i <= m)
        tmp[k++] = a[i++];
    while(j <= r)
        tmp[k++] = a[j++];

    for(int t = l; t <= r; t++){
        a[t] = tmp[t];
    }
}
void Mergesort(int a[], int l, int r){
    if(l < r){
        int m = (l + r) / 2;
        Mergesort(a, l, m);
        Mergesort(a, m + 1, r);
        Merge(a, l, m , r);
    }
}


int main(){
    int a[5] = {3, 2, 1, 5, 5};
    Mergesort(a, 0, 4);
    for(auto i : a)
        cout << 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
38
39
40
41
42
43
44
45
#include<iostream>
#include<string>

using namespace std;
int tmp[50005];

int inv_cnt = 0;
void Merge(int a[], int l, int m, int r){
    int i = l, j = m + 1, k = i;
    while(i <= m && j <= r){
        if(a[i] <= a[j]){
            tmp[k++] = a[i++];
        }else{
            tmp[k++] = a[j++];
            inv_cnt += m - i + 1;
        }

    }

    while(i <= m)
        tmp[k++] = a[i++];
    while(j <= r)
        tmp[k++] = a[j++];

    for(int t = l; t <= r; t++){
        a[t] = tmp[t];
    }
}
void Mergesort(int a[], int l, int r){
    if(l < r){
        int m = (l + r) / 2;
        Mergesort(a, l, m);
        Mergesort(a, m + 1, r);
        Merge(a, l, m , r);
    }
}


int main(){
    int a[5] = {3, 2, 1, 5, 5};
    Mergesort(a, 0, 4);
    for(auto i : a)
        cout << i << ' ';
    cout << endl << inv_cnt;
}

k重逆序对

问满足a[i] > k * a[j]并且 i < j的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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<string>
#define int long long
using namespace std;

int kk;

int tmp[100005];

long long inv_cnt = 0;
void Merge(int a[], int l, int m, int r){
    for(int i = l, j = m + 1; i <= m; i++){
        while(j <= r && (long long)a[i] > (long long)kk * a[j]){
            j++;
        }
        inv_cnt += j - (m + 1);
    }

    int i = l, j = m + 1, k = i;
    while(i <= m && j <= r){
        if(a[i] <= a[j]){
            tmp[k++] = a[i++];
        }else{
            tmp[k++] = a[j++];
        }

    }

    while(i <= m)
        tmp[k++] = a[i++];
    while(j <= r)
        tmp[k++] = a[j++];

    for(int t = l; t <= r; t++){
        a[t] = tmp[t];
    }
}
void Mergesort(int a[], int l, int r){
    if(l < r){
        int m = (l + r) / 2;
        Mergesort(a, l, m);
        Mergesort(a, m + 1, r);
        Merge(a, l, m , r);
    }
}

long long a[100005];
signed main(){
    int n;
    cin >> n >> kk;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    Mergesort(a, 0, n - 1);
    cout << inv_cnt;
}

寻找第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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<vector>
using namespace std;
int select(vector<int> &a , int left , int right , int k) //找到第k小的数
{
    if(left == right) return a[left];

    int temp = a[right];
    int i = left-1;
    for(int j=left;j<=right-1;j++)
    {
        if(a[j]<temp) //若要找第k大的，将这里的<改为>即可
        {
            swap(a[++i] , a[j]);
        }
    }
    swap(a[i+1] , a[right]);
    int partition = i+1;

    int re = partition-left+1;
    if(re == k) return a[partition];
    else if(re > k) return select(a,left,partition-1,k);
    else return select(a,partition+1,right,k-re);
}
void quicksort(vector<int> &a, int left, int right) {
    if (left >= right) return;

    int temp = a[right];        // pivot
    int i = left - 1;

    for (int j = left; j <= right - 1; j++) {
        if (a[j] < temp) {
            swap(a[++i], a[j]);
        }
    }
    swap(a[i + 1], a[right]);
    int partition = i + 1;

    // 左右都递归
    quicksort(a, left, partition - 1);
    quicksort(a, partition + 1, right);
}
int main(){
    vector<int> a = {4, 2, 6,32 ,234,23, 2,34,1324,123,432,6,54,7564,7865,4,1324,1324};

    cout << select(a, 0, a.size() - 1, a.size());
    quicksort(a, 0, a.size() -1);

    cout << '\n';
    for(auto i : a){
        cout << i << ' ';
    }
    
}

moore庄园投票

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
#include <iostream>
#include <vector>
using namespace std;
int boyer_moore(const vector<int>& nums) {
    int candidate = 0;
    int count = 0;
    // 第一遍遍历：找出候选人
    for (int num : nums) {
        if (count == 0) {
            // 如果计数器为0，设立新的候选人
            candidate = num;
            count = 1;
        } else if (num == candidate) {
            // 如果是候选人，票数+1
            count++;
        } else {
            // 如果不是候选人，票数-1 (一换一抵消)
            count--;
        }
    }
    // 注意：如果题目保证一定存在多数元素，此时 candidate 就是结果。
    // 如果题目不保证一定存在，需要进行第二遍遍历来验证 candidate 的次数是否 > n/2。
    // 这里假设题目保证存在多数元素，直接返回。
    return candidate;
}
/* 
// 验证环节（如果需要的话）：
bool verify(const vector<int>& nums, int candidate) {
    int count = 0;
    for (int x : nums) if (x == candidate) count++;
    return count > nums.size() / 2;
}
*/
int main() {
    vector<int> nums = {2, 3, 2, 1, 3, 2, 2, 2};
    cout << boyer_moore(nums) << endl;
    return 0;
}

卡特兰数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;

long long f(int n){
    if(n == 0 || n == 1){
        return 1;
    }
    long long ans = 0;
    for(int i = 0; i < n; i++){
        ans += f(i) * f(n - 1 - i);
    }
    return ans;
}
int main(){
    int n;
    cin >> n;
    printf("%lld", f(n));
    return 0;
}

高精度乘法

$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
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<string.h>

using namespace std;
char a1[1000001],b1[1000001];
int a[1000001],b[1000001];
int i,x,len,j,c[1000001];
int main ()
{
	int T;
	cin >> T;
	while(T--){
		for(int i = 0; i < 200005;i++){
			a1[i] = b1[i] = a[i] = b[i] = c[i] = 0;
		}
		cin>>a1>>b1;
		int lena=strlen(a1);
		int lenb=strlen(b1);
		for(i=1;i<=lena;i++)
			a[i]=a1[lena-i]-'0';
		for(i=1;i<=lenb;i++)
			b[i]=b1[lenb-i]-'0';
		for(i=1;i<=lenb;i++)
			for(j=1;j<=lena;j++)
				c[i+j-1]+=a[j]*b[i];
		for(i=1;i<lena+lenb;i++)
			if(c[i]>9)
			{
				c[i+1]+=c[i]/10;
				c[i]%=10;
			}
		len = lena + lenb;
		while(c[len] == 0&&len > 1)
			len--;
		for(i=len;i>=1;i--) 
			cout<<c[i];
		cout << endl;
	}
	
    return 0;
}

$O(nlgn)$

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

const int MAXN = 1000000 + 7;
const double PI = acos(-1.0);

struct Complex {
    double x, y;
};

inline Complex addc(const Complex &a, const Complex &b) {
    return {a.x + b.x, a.y + b.y};
}

inline Complex subc(const Complex &a, const Complex &b) {
    return {a.x - b.x, a.y - b.y};
}

inline Complex mulc(const Complex &a, const Complex &b) {
    return {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};
}

Complex a[MAXN * 3], b[MAXN * 3];
long long ans[MAXN * 3];
int pos[MAXN * 3];

void FFT(Complex *A, int len, int type) {
    for (int i = 0; i < len; i++) {
        if (i < pos[i]) swap(A[i], A[pos[i]]);
    }

    for (int L = 2; L <= len; L <<= 1) {
        int H = L / 2;
        Complex Wn = {cos(2 * PI / L), type * sin(2 * PI / L)};

        for (int R = 0; R < len; R += L) {
            Complex w = {1, 0};

            for (int k = 0; k < H; k++) {
                Complex t = mulc(w, A[R + k + H]);
                Complex u = A[R + k];

                A[R + k] = addc(u, t);
                A[R + k + H] = subc(u, t);

                w = mulc(w, Wn);
            }
        }
    }

    if (type == -1) {
        for (int i = 0; i < len; i++) {
            A[i].x /= len;
            A[i].y /= len;
        }
    }
}

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

    while (T--) {

        pos[0] = 0;
        int maxLen = 1, l = 0;

        static char s1[MAXN], s2[MAXN];
        scanf("%s %s", s1, s2);

        int n = strlen(s1);
        int m = strlen(s2);

        while (maxLen < n + m + 1) {
            maxLen <<= 1;
            l++;
        }

        for (int i = 0; i <= maxLen; i++) {
            a[i].x = a[i].y = 0;
            b[i].x = b[i].y = 0;
            ans[i] = 0;
        }

        for (int i = 0; i < n; i++) a[i].x = s1[n - 1 - i] - '0';
        for (int i = 0; i < m; i++) b[i].x = s2[m - 1 - i] - '0';

        for (int i = 0; i < maxLen; i++) {
            pos[i] = (pos[i >> 1] >> 1) | ((i & 1) << (l - 1));
        }

        FFT(a, maxLen, 1);
        FFT(b, maxLen, 1);

        for (int i = 0; i < maxLen; i++)
            a[i] = mulc(a[i], b[i]);

        FFT(a, maxLen, -1);

        for (int i = 0; i < maxLen; i++) {
            ans[i] += (long long)(a[i].x + 0.5);
            ans[i + 1] += ans[i] / 10;
            ans[i] %= 10;
        }

        int p = maxLen;
        while (p > 0 && ans[p] == 0) p--;

        for (; p >= 0; p--) printf("%lld", ans[p]);
        printf("\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
#include <iostream>
#include <algorithm>

using namespace std;

long long a[305];
long long m[305][305];

long long memMCMaux(int i, int j) {
    if(i == j) return 0;          
    if(m[i][j] != -1) return m[i][j]; 

    m[i][j] = LLONG_MAX;
    for(int k = i; k < j; k++) {
        long long q = memMCMaux(i, k) + memMCMaux(k + 1, j) + a[i-1]*a[k]*a[j];
        if(q < m[i][j]) m[i][j] = q;
    }
    return m[i][j];
}

long long memMCM(int n) {
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            m[i][j] = -1;
    return memMCMaux(1, n);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    cout << memMCM(n) << endl;
}

钢管切割

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<iostream>
#include<algorithm>
using namespace std;
long long p[10005];
long long dp[10005]; //i段长度价格
int s[10005]; // 切割处

void outp(int n){
    while(n > 0){
        cout << s[n] << ' ';
        n = n - s[n];
    }
    
}
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> p[i];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            if(p[j] + dp[i - j] > dp[i]){
                dp[i] = p[j] + dp[i - j];
                s[i] = j;
            }
        }
    }
    int count = 0;
    cout << dp[n] << endl;
    int n0 = n;
    while(n > 0){
        n = n - s[n];
        count++;
    }
    cout << count << endl;
    outp(n0);
}

流水线调度

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;

long long p[4][10005];
long long t[4][4];
long long dp[4][10005];
const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T, m;
    cin >> T;
    while (T--) {
        cin >> m;

        // 输入 p[i][j]
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> p[i][j];
            }
        }

        // 输入 t[i][j]
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                cin >> t[i][j];
            }
        }

        // 初始化第一站
        for (int i = 1; i <= 3; i++) {
            dp[i][1] = p[i][1];
        }

        // 状态转移
        for (int j = 2; j <= m; j++) {
            for (int i = 1; i <= 3; i++) {
                dp[i][j] = INF;
                for (int k = 1; k <= 3; k++) {
                    long long cost = dp[k][j - 1] + p[i][j] + t[k][i];
                    dp[i][j] = min(dp[i][j], cost);
                }
            }
        }

        long long ans = min({dp[1][m], dp[2][m], dp[3][m]});
        cout << ans << "\n";
    }

    return 0;
}

OBST最优二叉搜索树

有查找失败概率的OBST

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
#include <iostream>
#include <vector>
#include <limits>

using namespace std;
const int INF = 1e9;
vector<vector<int>> root;

double optimalBST(const vector<double>& p, const vector<double>& q, int n) {
    vector<vector<double>> e(n + 2, vector<double>(n + 1, 0));
    vector<vector<double>> w(n + 2, vector<double>(n + 1, 0));
    root.assign(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= n + 1; ++i) {
        e[i][i - 1] = q[i - 1];
        w[i][i - 1] = q[i - 1];
    }

    for (int l = 1; l <= n; ++l) {
        for (int i = 1; i <= n - l + 1; ++i) {
            int j = i + l - 1;
            e[i][j] = INF; //注意INF
            w[i][j] = w[i][j - 1] + p[j] + q[j];

            for (int k = i; k <= j; ++k) {
                double t = e[i][k - 1] + e[k + 1][j] + w[i][j];
                if (t < e[i][j]) {
                    e[i][j] = t;
                    root[i][j] = k;
                }
            }
        }
    }
    return e[1][n];
}

void printRootTree(int i, int j, int parent, bool isLeft) {
    if (i > j) return;
    int r = root[i][j];
    if (parent == -1)
        cout << "Root: " << r << "\n";
    else
        cout << (isLeft ? "Left child of " : "Right child of ") << parent << ": " << r << "\n";

    printRootTree(i, r - 1, r, true);
    printRootTree(r + 1, j, r, false);
}

int main() {
    int n;
    cout << "Number of nodes: ";
    cin >> n;

    vector<double> p(n + 1, 0);
    vector<double> q(n + 1, 0);

    //输入p[1...n]
    for (int i = 1; i <= n; ++i) cin >> p[i];

    //输入q[0...n]
    for (int i = 0; i <= n; ++i) cin >> q[i];

    double res = optimalBST(p, q, n);
    cout << "Optimal BST expected cost: " << res << "\n";

    printRootTree(1, n, -1, false);

    return 0;
}

无查找失败概率的OBST

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

using namespace std;
vector<vector<int>> root(505, vector<int>(505, 0));
vector<int> Tleft(505, -1);
vector<int> Tright(505, -1);
void build(int l, int r){
    if(l > r) return;
    int k = root[l][r];

    if(l <= k - 1){
        Tleft[k] = root[l][k - 1];
        build(l, k - 1);
    }else{
        Tleft[k] = -1;
    }
    if(k + 1 <= r){
        Tright[k] = root[k + 1][r];
        build(k + 1, r);
    }else{
        Tright[k] = -1;
    }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;  
    cin >> n;
    vector <int> p(n + 1, 0);
    for(int i = 1; i <= n; i++) cin >> p[i];

    vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, 0));
    vector<vector<long long>> sum(n + 2, vector<long long>(n + 2, 0));
    

    vector<long long> prefixSum(n + 1, 0);
    for(int i = 1; i <= n; i++) prefixSum[i] = prefixSum[i - 1] + p[i];

    for(int i = 1; i <= n + 1; i++) dp[i][i - 1] = 0;

    for(int len = 1; len <= n; len++){
        for(int i = 1; i + len - 1 <= n; i++){
            int j = i + len - 1;
            dp[i][j] = (long long)1 << 60;

            for(int k = i; k <= j; k++){
                long long cost = dp[i][k - 1] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1];
                if(cost < dp[i][j]){
                    dp[i][j] = cost;
                    root[i][j] = k;
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    build(1, n);
    for(int i = 1; i <= n; i++)
        cout << Tleft[i] << ' ' << Tright[i] << endl;
    
}

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

using namespace std;
int a[2005];
int v[2005];
int dp[2005][2005];

int bag01(int n, int w){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= w; j++){
            if(j - a[i] >= 0)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + v[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[n][w];
}

int bagfull(int n, int w){
    for(int i = 1; i <= n; i++){
        for(int j = a[i]; j <= w; j++){
            dp[i][j] = max(dp[i - 1][j], dp[i][j - a[i]] + v[i]);
        }
    }
    return dp[n][w];
}
int main(){
    int n, w;
    cin >> n >> w;
    for(int i = 1; i <= n; i++) cin >> a[i] >> v[i];
    cout << bag01(n, w) << endl;
    for(int i = 0;i < 2005; i++)
        fill(dp[i], dp[i] + 2005, 0);
    cout << bagfull(n, w) << endl;
}


一维数组版

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

using namespace std;

int a[2005]; // 重量
int v[2005]; // 价值
int dp[2005]; // 一维状态数组

// 0/1 背包：逆序遍历
int bag01(int n, int w) {
    fill(dp, dp + w + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = w; j >= a[i]; j--) { // 必须从后往前
            dp[j] = max(dp[j], dp[j - a[i]] + v[i]);
        }
    }
    return dp[w];
}

// 完全背包：正序遍历
int bagfull(int n, int w) {
    fill(dp, dp + w + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= w; j++) { // 必须从前往后
            dp[j] = max(dp[j], dp[j - a[i]] + v[i]);
        }
    }
    return dp[w];
}

int main() {
    int n, w;
    if (!(cin >> n >> w)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i] >> v[i];

    cout << "0/1 Knapsack: " << bag01(n, w) << endl;
    cout << "Complete Knapsack: " << bagfull(n, w) << endl;

    return 0;
}

01背包问题，dp[w]版本

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

using namespace std;



int main(){
    long long n, V;
    cin >> n >> V;
    vector<long long> v(n + 1);
    vector<int>  w(n + 1);
    int wsum = 0;
    for(int i = 1; i <= n; i++){
        cin >> v[i] >> w[i];
        wsum += w[i];
    }
    long long INF = (long long)9e18;
    vector<long long> dp(wsum + 1, INF);
    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        for(long long j = wsum; j >= w[i]; j--){
            if(dp[j - w[i]] != INF){
                dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
            }
        }
    }
    long long ans = 0;
    for(long long val = 0; val <= wsum; val ++){
        if(dp[val] <= V) ans = max(ans, val);
    }
    cout << ans;
}


最长不上升子序列/导弹拦截

O(nlgn)

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

using namespace std;

int main(){
    vector<int> a;
    int x;
    while((cin >> x)){
        a.push_back(x);
    }

    int n = a.size();

    vector<int> d1, d2;
    for(int i = 0; i < n; i++){
        if(d1.empty() || d1.back() >= a[i]){
            d1.push_back(a[i]);
        }else{
            auto it = upper_bound(d1.begin(), d1.end(), a[i], greater<int>());
            *it = a[i];
        }

        if (d2.empty() || d2.back() < a[i]) {
            d2.push_back(a[i]);
        } else {
            auto it = lower_bound(d2.begin(), d2.end(), a[i]);
            *it = a[i];
        }
    }
    cout << d1.size() << endl;
    cout << d2.size() << endl;

    return 0;
}

最长等差序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int longestArithSeqLength(vector<int>& nums) {
	int n = nums.size();
	if(n <= 2) return n;
	vector<vector<int>> dp(n, vector<int>(1001, 1));

	int maxlen = 2;
	for(int i = 1; i < n; i++){
		for(int j = 0; j < i; j++){
			int diff = nums[i] - nums[j] + 500;

			dp[i][diff] = dp[j][diff] + 1;
			maxlen = max(maxlen, dp[i][diff]);
		}
	}

	return maxlen;
}

最长公共子序列

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> b(n + 1);
    vector<int> dp(n + 1, 0);

    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];

    for(int i = 1; i <= n; i++){
        int pre = 0;
        for(int j = 1; j <= n; j++){
            int tmp = dp[j];
            if(a[i] == b[j])
                dp[j] = pre + 1;
            else{
                dp[j] = max(dp[j], dp[j - 1]);
            }
            pre = tmp;
        }
    }
    cout << dp[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
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

using namespace std;

int dp[2005][2005];
int main(){
    string a, b;
    cin >> a >> b;
    int lena = a.size();
    int lenb = b.size();

    for(int j = 0; j <= lenb; j++){
        dp[0][j] = j;
    }
    for(int i = 0; i <= lena; i++){
        dp[i][0] = i;
    }

    for(int i = 1; i <= lena; i++){
        for(int j = 1; j <= lenb; j++){
            if(a[i - 1] == b[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            }else
            dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1});
        }
    }
    
    cout << dp[lena][lenb];
    return 0;
}

区间动态规划

回文子串

回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。

比如 Ab3bd 插入 2 个字符后可以变成回文词 dAb3bAd 或 Adb3bdA，但是插入少于 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
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

int main(){
    string ss;
    cin >> ss;
    string s = '$' + ss;
    int n = ss.size();
    vector<vector<int>> dp(n + 1, vector<int>(n+1,0));
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n - i; j++){
            int k = i + j;
            if(s[j] == s[k]){
                dp[j][k] = dp[j + 1][k - 1];
            }else{
                dp[j][k] = min(dp[j + 1][k], dp[j][k - 1]) + 1;
            }
        }
    }
    cout << dp[1][n];
}

石子合并

题目描述

设有 N(N≤300) 堆石子排成一排，其编号为 1,2,3,⋯,N。每堆石子有一定的质量 mi​ (mi​≤1000)。现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

输入格式

第一行，一个整数 N。

第二行，N 个整数 mi​。

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

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> m(N + 1, 0);
    vector<int> pre(N + 1, 0);
    for(int i = 1; i <= N; i++){
        cin >> m[i];
        pre[i] = pre[i - 1] + m[i];
    } 

    vector<vector<int>> dp(N + 1, vector<int>(N + 1, 100000000));

    for(int i = 1; i <= N; i++) dp[i][i] = 0;
    for(int k = 2; k <= N; k++){
        for(int i = 1 ; i <= N - k + 1; i++){
            int j = i + k - 1;
            for(int l = i; l < j; l++){
                dp[i][j] = min(dp[i][j], dp[i][l] + dp[l + 1][j] + pre[j] - pre[i - 1]);
            }
        }
    }
    cout << dp[1][N];
}

zuma问题/回文子串数

Genos 最近在他的手机上下载了祖玛游戏。在祖玛游戏里，存在 n 个一行的宝石，第 i 个宝石的颜色是 Ci​。这个游戏的目标是尽快的消灭一行中所有的宝石。

在一秒钟，Genos 能很快的挑选出这些有颜色的宝石中的一个回文的、连续的子串，并将这个子串移除。每当一个子串被删除后，剩余的宝石将连接在一起，形成一个新的行列。

你的任务是：求出把整个宝石串都移除的最短时间。

输入格式

第一行包含一个整数 n(1≤n≤500)，表示宝石串的长度。第二行包含 n 个被空格分开的整数，第 i(1≤i≤n) 个表示这行中第 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
38
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n + 1, 0);
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 233333333));

    
    vector<int> sum(n + 1, 0);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    for(int i = 1; i <= n; i++) 
        dp[i][i] = 1;

    for (int i=1;i<n;i++) dp[i][i+1]=1+(a[i]!=a[i+1]); 

    for(int len = 3; len <= n; len++){
        for(int i = 1; i <= n - len + 1; i ++){
            int j = i + len - 1;
            if(a[i] == a[j]){
                dp[i][j] = dp[i + 1][j - 1];
            }else{
                for(int k = i; k < j; k++){
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
                }
            }
        }
    }
    cout << dp[1][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
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int happy[6005];
int hasParent[6006];
int dp[6005][2];
vector<int> children[6005];
void dfs(int u){
    dp[u][1] = happy[u];
    dp[u][0] = 0;
    for(int v: children[u]){
        dfs(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int N;
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> happy[i];

    int L, K;
    
    while(cin >> L >> K && (K || L)){
        children[K].push_back(L);
        hasParent[L] = 1; 
    }
    int root = 1;
    for(int i = 1; i <= N; i++){
        if(!hasParent[i]){
            root = i;
            break;
        }
    }
    dfs(root);
    cout << max(dp[root][0], dp[root][1]) << endl;
    return 0;
}

背包问题

二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int bag01(int n, int w){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= w; j++){
            if(j - a[i] >= 0)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + v[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[n][w];
}

int bagfull(int n, int w){
    for(int i = 1; i <= n; i++){
        for(int j = a[i]; j <= w; j++){
            dp[i][j] = max(dp[i - 1][j], dp[i][j - a[i]] + v[i]);
        }
    }
    return dp[n][w];
}

一维数组

1
2
3
4
5
6
7
8
9
10
int bag01(int n, int w) {
    // 假设 dp 已经初始化为 0
    for (int i = 1; i <= n; i++) {
        // 必须从大到小遍历
        for (int j = w; j >= a[i]; j--) {
            dp[j] = max(dp[j], dp[j - a[i]] + v[i]);
        }
    }
    return dp[w];
}
1
2
3
4
5
6
7
8
9
10
int bagfull(int n, int w) {
    // 假设 dp 已经初始化为 0
    for (int i = 1; i <= n; i++) {
        // 必须从小到大遍历
        for (int j = a[i]; j <= w; j++) {
            dp[j] = max(dp[j], dp[j - a[i]] + v[i]);
        }
    }
    return dp[w];
}

分组背包

物品被分成若干组，每组中的物品只能选择一个。也就是说，从每组物品中，你只能选择一个或者不选，但不能选择多个

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 <algorithm>  
using namespace std;  
typedef long long ll;  
const int MAX = 1005;  
struct {  
    int cnt;  
    ll ID[MAX];  
} group[MAX]; //用一个结构体来存储每一组的物品编号  
ll dp[MAX];     // 最大价值  
ll val[MAX];    // 每个物品的价值  
ll weight[MAX]; // 每个物品的重量  
  
ll group_bag(int cap, int max_group);  
  
int main() {  
    int n, W;  
    cin >> W >> n;  //  n表示物品数量，W表示背包容量  
    int a, b, k, max_group = 0;  
    for (int i = 1; i <= n; i++) {  
        cin >> a >> b >> k; // a重量  b价值  k物品所在的组号  
        weight[i] = a;  
        val[i] = b;  
        group[k].ID[group[k].cnt++] = i;  
        max_group = max(max_group, k);  
    }  
    cout << group_bag(W, max_group);  
    return 0;  
}  
  
ll group_bag(int W, int max_group) {  
    for (int i = 0; i <= max_group; i++) // 第一层循环，遍历所有组  
        for (ll j = W; j >= 0; j--) // 第二层循环，从背包容量W到0倒序遍历  
            for (int k = 0; k < group[i].cnt; k++) // 第三层循环，遍历当前组内的所有物品  
                if (j >= weight[group[i].ID[k]]) // 如果当前物品可以放入背包  
                    // 更新dp数组，选择放入或不放入当前物品，取最大值  
                    dp[j] = max(dp[j],dp[j - weight[group[i].ID[k]]] + val[group[i].ID[k]]);  
    return dp[W];  
}

多重背包

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<bits/stdc++.h>  
using namespace std;  
const int MAXN=1e5+10;  
int n,W;  
int v[MAXN],w[MAXN];  
int f[MAXN];  
int main(){  
    cin >> n >> W;  // 物品个数n和最大重量W    
	int cnt = 0;    // 记录二进制合成后的物体数
	for(int i=1,a,b,s; i<=n; i++)   {  
        cin>> a >> b >> s;   // 单个价值a 单个重量b 数量s
		int k = 1;  
        while(k <= s){ // 将每个物品都按照二进制合成    
			v[++cnt] = k*a;  
            w[cnt] = k*b;  
            s -= k;  
            k *= 2;  
        }  
        if(s){  
            v[++cnt] = s*a;  
            w[cnt] = s*b;  
        }  
    }  
  
    for(int i=1; i<=cnt; i++) // 01背包     
		for(int j=W; j>=v[i]; j--)  
            f[j] = max(f[j], f[j-v[i]]+w[i]);  
    cout << f[W];  
    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>
#include<algorithm>
#include<vector>
using namespace std;
struct course{
    int a;
    int b;
};

bool cmp(course x, course y){
    if(x.b < y.b) return true;
    else if(x.b == y.b) return x.a < y.a;
    return false;
}
int main(){
    int n;
    cin >> n;
    vector<course> c;
    int a, b;
    for(int i = 0; i < n; i++){
        cin >> a >> b;
        c.push_back({a,b});
    }
    sort(c.begin(), c.end(), cmp);

    int time_now = c[0].b;
    int all = 1;
    for(int i = 1; i < n; i++){
        if(c[i].a >= time_now){
            all += 1;
            time_now = c[i].b;
        }
    }
    cout << all;
}

哈夫曼编码/解码

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
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<string>

using namespace std;

struct Node{
    char data;
    int freq;
    Node *left, *right;
};

struct cmp {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};
string encode(string text, map<char, string>& huffmanCodes){
    string encodedStr = "";
    for(char ch : text){
        encodedStr += huffmanCodes[ch];
    }
    return encodedStr;
}

string decode(Node *root, string encodedStr) {
    string decodedStr = "";
    Node* curr = root; // 从根节点开始
    
    for (char bit : encodedStr) {
        // 根据 bit 移动 curr 指针，而不是 root->left/right
        if (bit == '0') {
            curr = curr->left;
        } else {
            curr = curr->right;
        }

        // 如果到达叶子节点，说明找到了一个字符
        if (!curr->left && !curr->right) {
            decodedStr += curr->data;
            curr = root; // 重置指针回到根节点，准备找下一个字符
        }
    }
    return decodedStr;
}
void generateCodes(Node *root, string code, map<char, string> &huffmanCodes){
    if(!root) return;

    if(root->data != '$'){
        huffmanCodes[root->data] = code; 
    }

    generateCodes(root->left, code + "0", huffmanCodes);
    generateCodes(root->right, code + "1", huffmanCodes);
}

void buildHuffmanTree(string text){
    map<char, int> freq;
    for(char &ch: text){
        freq[ch]++;
    }

    priority_queue<Node*, vector<Node*>, cmp> pq;

    for(auto &pair : freq){
        pq.push(new Node({pair.first, pair.second, nullptr, nullptr}));
    }

    while(pq.size() > 1){
        Node *left = pq.top(); pq.pop();
        Node *right = pq.top(); pq.pop();

        Node *newNode = new Node({'$', left->freq + right->freq, nullptr, nullptr});
        
        newNode->left = left;
        newNode->right = right;

        pq.push(newNode);
    }

    Node* root = pq.top();

    map<char, string> huffmanCodes;
    generateCodes(root, "", huffmanCodes);
    cout << "Huffman Codes:" << endl;
    for (auto const& [ch, code] : huffmanCodes) {
        cout << ch << ": " << code << endl;
    }
    string encoded = encode(text, huffmanCodes);
    cout << "\nEncoded String: " << encoded << endl;
    cout << "Decoded String: " << decode(root, encoded) << endl;

}

int main(){
    string s;
    cin >> s;
    buildHuffmanTree(s);

}


bfs dfs

$O(V+E)$

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<algorithm>
#include<vector>
#include<queue>
using namespace std;

void DFSUtil(const vector<vector<int>> &adj, int u, vector<bool> &visited){
    visited[u] = true;
    cout << u << ' ';
    for(int v : adj[u]){
        if(!visited[v]){
            DFSUtil(adj, v, visited);
        }
    }
    
}
void dfs(const vector<vector<int>> &adj, int start){
    int V = adj.size();
    vector<bool> visited(V, false);

    DFSUtil(adj, start, visited);
    cout << endl;
}
void bfs(const vector<vector<int>> &adj, int start){
    int V = adj.size();
    vector<bool> visited(V, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        int u = q.front();
        q.pop();

        cout << u << ' ';
        for(int v : adj[u]){
            if(!visited[v]){
                visited[v] = true;
                q.push(v);
            }
        }
    }
    cout << endl;
}

int main(){
    int n, m, u, v;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        adj[u].push_back(v);
    }
    for(int i = 1; i <= n; i ++)
        sort(adj[i].begin(), adj[i].end());
    dfs(adj, 1);
    bfs(adj, 1);

}

Bellman-Ford

$O(VE) / O(kE)$ 可处理负权边

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

using namespace std;

const int INF = 1e9;

// 使用邻接表重写的 Bellman-Ford
pair<vector<int>, bool> bellman_ford(int n, const vector<vector<pair<int, int>>>& adj, int s) {
    vector<int> dist(n + 1, INF);
    dist[s] = 0;

    // 进行 n-1 次松弛
    for (int i = 1; i <= n - 1; i++) {
        bool updated = false;
        // 遍历所有顶点 u
        for (int u = 1; u <= n; u++) {
            if (dist[u] == INF) continue;
            // 遍历 u 的所有出边 {v, w}
            for (auto& edge : adj[u]) {
                int v = edge.first;
                int w = edge.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
        }
        if (!updated) break; // 优化：如果没有更新则提前退出
    }

    // 第 n 次遍历检测负权回路
    for (int u = 1; u <= n; u++) {
        if (dist[u] == INF) continue;
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                return {dist, true}; // 依然能松弛，说明有负环
            }
        }
    }

    return {dist, false};
}

int main() {
    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;

    // adj[u] 存储 {v, w}
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    auto [dist, hasNegativeCycle] = bellman_ford(n, adj, s);

    if (hasNegativeCycle) {
        cout << "存在负权回路\n";
    } else {
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) cout << "INF ";
            else cout << dist[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

拓扑排序+松弛求最短路径

$O(V + E)$ 有向无环图

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<algorithm>
#include<vector>
#include<queue>
using namespace std;
int indegree[100005];
int main(){
    int n, m, u, v, w;
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n + 1);
    for(int i = 1; i <= m; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        indegree[v]++;
    }
    
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(indegree[i] == 0){
            q.push(i);
        }
    }
    
    
    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto &e : adj[u]) {
            indegree[e.first]--;
            if (indegree[e.first] == 0) q.push(e.first);
        }
    }

    
    for (int i = 0; i < (int)topo.size(); i++) {
        cout << topo[i] << ' ';
    }
    cout << endl;
    
    vector<long long> dist(n + 1, ((long long)1 << 60));
    dist[1] = 0;

    for (int u : topo) {
        if (dist[u] == ((long long)1 << 60)) continue;
        for (auto &e : adj[u]) {
            int v = e.first;
            int w = e.second;
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] == ((long long)1 << 60)) cout << -1;
        else cout << dist[i];
        if (i != n) cout << ' ';
    }

}

floyd算法

path（存的不是前序节点）
$O(V^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
vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));
vector<vector<int>> path(n + 1, vector<int>(n + 1, -1));

for(int i = 1; i <= n; i++){
	dist[i][i] = 0;
	path[i][i] = i;
}

/*输入*/

for(int k = 1; k <= n; k++){ //外层循环表示中间经过哪个点（必须放在最外面
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(dist[i][k] + dist[k][j] < dist[i][j]){
				dist[i][j] = dist[i][k] + dist[k][j];
				path[i][j] = path[i][k];
			}
		}
	}
}

检测负环
bool hasNegativeCycle = false;
for (int i = 1; i <= n; ++i) {
	if (dist[i][i] < 0) { // 如果到自己的距离变成了负数，说明存在负环
		hasNegativeCycle = true;
		break;
	}
}
void printPath(int i, int j) {
    if (i == j) {
        cout << i << " ";
        return;
    }
    if (path[i][j] == -1) { // 没有路径
        cout << "无路径";
        return;
    }
    cout << i << " ";
    printPath(path[i][j], j); // 继续往下走
}

dj算法求最短路

邻接矩阵版

$O(V^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
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<int>> adj(n + 1, vector<int>(n + 1, 1e9));
    vector<int> dist(n + 1, 1e9);
    vector<int> vis(n + 1, 0);
    vector<int> pre(n + 1, -1);

    int u, v, w;
    for(int i = 0; i < m; i++){
        cin >> u >> v >> w;
        adj[u][v] = adj[v][u] = w;
    }

    dist[s] = 0;

    for(int i = 1; i <= n; i++){
        int u = -1;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && (u == -1 || dist[j] < dist[u])){
                u = j;
            }
        }
        if(u == -1) break;
        vis[u] = 1;

        for(int v = 1; v <= n; v++){
            if(dist[u] + adj[u][v] < dist[v]){
                dist[v] = dist[u] + adj[u][v];
                pre[v] = u;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(dist[i] == 1e9) cout << "INF ";
        else cout << dist[i] << " ";
    }
    
}

邻接表

$O(E \log 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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

int main(){
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<pair<int,int>>> adj(n + 1);
    vector<int> dist(n + 1, 1e9);
    vector<int> pre(n + 1, -1);
    int u, v, w;
    for(int i = 0; i < m; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[s] = 0;

    pq.push({0, s});

    while(!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();

        if(d > dist[u]) continue;

        for(auto &edge : adj[u]){
            int v = edge.first;
            int w = edge.second;

            if(dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                pre[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    for(int i = 1; i <= n; i++){
        cout << dist[i] << ' ';
    }
}

prim最小生成树

$O(E \log 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
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;

    // 邻接表：adj[u] 存储 {v, weight}
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // dist[i] 表示节点 i 到当前生成树的最短距离
    vector<int> dist(n + 1, INF);
    vector<bool> visited(n + 1, false);
    
    // 优先队列：存储 {weight, node_index}
    // 使用 greater 会让 pair 按照 weight 从小到大弹出
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    int total_weight = 0; // 最小生成树总权重
    int count = 0;        // 已加入生成树的节点数量

    // 从 1 号点开始（假设点编号为 1 ~ n）
    dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        // 取出当前距离生成树最近的点
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // 如果该点已经加入过生成树，直接跳过
        if (visited[u]) continue;

        // 标记加入生成树
        visited[u] = true;
        total_weight += d;
        count++;

        // 遍历 u 的所有邻居 v
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            // 如果 v 未在树中，且通过 u 连接 v 的边权更小
            if (!visited[v] && weight < dist[v]) {
                dist[v] = weight;
                pq.push({dist[v], v});
            }
        }
    }

    // 连通性检查：如果加入的点数等于总点数，说明连通
    if (count == n) {
        cout << total_weight << endl;
    } else {
        cout << "orz" << endl;
    }

    return 0;
}

dinic算最大流/最大割

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

const int N = 205, INF = 1e15;

struct edge {
    int to;
    int cap;   // 残余容量
    int rev;   // 在对方 vector 中的下标
    bool is_real; // 是否是原图中的边
};

vector<edge> G[N];
int dep[N], cur[N];
int n, m, S, T;

void add_edge(int u, int v, int w) {
    G[u].push_back({v, w, (int)G[v].size(), true});
    G[v].push_back({u, 0, (int)G[u].size() - 1, false});
}

bool bfs() {
    memset(dep, -1, sizeof dep);
    dep[S] = 0;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto &e : G[u]) {
            if (e.cap > 0 && dep[e.to] == -1) {
                dep[e.to] = dep[u] + 1;
                q.push(e.to);
            }
        }
    }
    return dep[T] != -1;
}

int dfs(int u, int limit) {
    if (u == T || limit == 0) return limit;
    for (int &i = cur[u]; i < G[u].size(); i++) {
        edge &e = G[u][i];
        if (dep[e.to] == dep[u] + 1 && e.cap > 0) {
            int d = dfs(e.to, min(limit, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int dinic() {
    int flow = 0;
    while (bfs()) {
        memset(cur, 0, sizeof cur);
        while (int d = dfs(S, INF)) {
            flow += d;
        }
    }
    return flow;
}

void solve() {
    if (!(cin >> n >> m >> S >> T)) return;
    for (int i = 1; i <= n; i++) G[i].clear();

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u == v) continue; 
        add_edge(u, v, w);
    }

    // 1. 计算最大流
    int max_flow = dinic();
    cout << max_flow << endl;

    // // 2. 遍历所有边，寻找割边
    // // 注意：此时最后的 bfs 已经确定了哪些点属于 S 集合 (dep != -1)
    // for (int u = 1; u <= n; u++) {
    //     if (dep[u] != -1) { // 如果起点在 S 集合
    //         for (auto &e : G[u]) {
    //             // 如果是原边、终点在 T 集合、且已经流满
    //             if (e.is_real && dep[e.to] == -1 && e.cap == 0) {
    //                 cout << u << " -> " << e.to << endl;
    //             }
    //         }
    //     }
    // }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    if (!(cin >> t)) return 0;
    while (t--) {
        solve();
    }
    return 0;
}

最大二分匹配

dinic找最大二分匹配

时间复杂度（一般图）：$O(V^2 E)$
时间复杂度（二分图/单位容量网络）：$O(E\sqrt{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
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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 10010, M = 200010, INF = 1e15;

struct edge {
    int ed, len, id;
};

vector<edge> e[N];
int n, m, S, T;
int dep[N], cur[N];

bool bfs() {
    memset(dep, -1, sizeof dep);
    queue<int> q;
    q.push(S);
    dep[S] = 0;
    while (!q.empty()) {
        int t = q.front(); q.pop();
        for (int i = 0; i < e[t].size(); i++) {
            int ed = e[t][i].ed;
            if (dep[ed] == -1 && e[t][i].len) {
                dep[ed] = dep[t] + 1;
                q.push(ed);
            }
        }
    }
    memset(cur, 0, sizeof(cur));
    return (dep[T] != -1);
}

int dfs(int st, int limit) {
    if (st == T) return limit;
    for (int i = cur[st]; i < e[st].size(); i++) {
        cur[st] = i;
        int ed = e[st][i].ed;
        if (dep[ed] == dep[st] + 1 && e[st][i].len) {
            int t = dfs(ed, min(e[st][i].len, limit));
            if (t) {
                e[st][i].len -= t;
                e[ed][e[st][i].id].len += t;
                return t;
            } else dep[ed] = -1;
        }
    }
    return 0;
}

int dinic() {
    int r = 0, flow;
    while (bfs()) while (flow = dfs(S, INF)) r += flow;
    return r;
}

// 辅助加边函数，保持逻辑整洁
void add_edge(int u, int v, int cap) {
    int ui = e[u].size();
    int vi = e[v].size();
    e[u].push_back({v, cap, vi});
    e[v].push_back({u, 0, ui});
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int nl, nr, m_edges; // 左侧点数, 右侧点数, 边数
    while (cin >> nl >> nr >> m_edges) {
        // 清空
        for (int i = 0; i <= nl + nr + 2; ++i) e[i].clear();
        
        // 定义源点和汇点
        S = 0, T = nl + nr + 1;

        // 1. 源点 -> 左侧点 (1..nl)
        for (int i = 1; i <= nl; i++) add_edge(S, i, 1);

        // 2. 右侧点 (nl+1..nl+nr) -> 汇点
        for (int i = 1; i <= nr; i++) add_edge(nl + i, T, 1);

        // 3. 原图中的边
        while (m_edges--) {
            int u, v;
            cin >> u >> v;
            if (u > nl || v > nr) continue; // 鲁棒性检查
            add_edge(u, nl + v, 1);
        }

        cout << dinic() << '\n';
    }
    return 0;
}

匈牙利算法

$O(V \cdot E)$

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

const int MAXN = 405; 

int n;
long long a[MAXN], p_req[MAXN];
long long b[MAXN], q_req[MAXN];

vector<int> G[MAXN];   // G[i]: Toby i (1..n) 可匹配的墨鱼索引（1..n）
int matchR[MAXN];     // matchR[j] = 哪个 Toby 匹配了墨鱼 j（0 表示空）
bool seen[MAXN];      // 访问标记（用于每次 dfs）

bool dfs(int u){
    for (int v : G[u]) {
        if (seen[v]) continue;
        seen[v] = true;
        if (matchR[v] == 0 || dfs(matchR[v])) {
            matchR[v] = u;
            return true;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;

    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> p_req[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    for (int i = 1; i <= n; ++i) cin >> q_req[i];

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (b[j] >= p_req[i] && a[i] >= q_req[j]) {
                G[i].push_back(j);
            }
        }
    }

    int result = 0;

    for (int u = 1; u <= n; ++u) {
        memset(seen, 0, sizeof(seen));
        if (dfs(u)) ++result;
    }

    cout << result << "\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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <algorithm>
using namespace std;

struct Point {
    long long x, y;
};

struct Segment {
    Point p1, p2;
};

long long cross(Point &p1, Point &p2, Point &p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - 
           (p2.y - p1.y) * (p3.x - p1.x);
}

int sign(long long x) {
    return (x > 0) - (x < 0);
}

bool onSegment(Point &p1, Point &p2, Point &p3) {
    return (p3.x >= min(p1.x, p2.x)) && (p3.x <= max(p1.x, p2.x)) &&
           (p3.y >= min(p1.y, p2.y)) && (p3.y <= max(p1.y, p2.y));
}

bool intersect(Segment &s1, Segment &s2) {
    Point A = s1.p1, B = s1.p2;
    Point C = s2.p1, D = s2.p2;

    long long c1 = cross(A, B, C);
    long long c2 = cross(A, B, D);
    long long c3 = cross(C, D, A);
    long long c4 = cross(C, D, B);

    int s1_sign = sign(c1);
    int s2_sign = sign(c2);
    int s3_sign = sign(c3);
    int s4_sign = sign(c4);

    if (s1_sign * s2_sign < 0 && s3_sign * s4_sign < 0)
        return true;

    if (c1 == 0 && onSegment(A, B, C)) return true;
    if (c2 == 0 && onSegment(A, B, D)) return true;
    if (c3 == 0 && onSegment(C, D, A)) return true;
    if (c4 == 0 && onSegment(C, D, B)) return true;

    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        Segment s1 = {{x1, y1}, {x2, y2}};
        cin >> x1 >> y1 >> x2 >> y2;
        Segment s2 = {{x1, y1}, {x2, y2}};
        cout << (intersect(s1, s2) ? "Yes" : "No") << '\n';
    }
}

凸包

Graham:$O(nlgn)$ ,另外一种Jarvis$O(nh)$（h为凸包上顶点的个数）

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

using namespace std;

struct Point {
    int x, y;
};

int cross(const Point &p1, const Point &p2, const Point &p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - 
           (p2.y - p1.y) * (p3.x - p1.x);//叉积
}

Point base;

bool cmp(const Point &a, const Point &b){
    int c = cross(base, a, b);
    if(c == 0){
        int da = (a.x - base.x)*(a.x - base.x) + (a.y - base.y)*(a.y - base.y);
        int db = (b.x - base.x)*(b.x - base.x) + (b.y - base.y)*(b.y - base.y);
        return da < db;
    }
    return c > 0;//逆时针排序
}

vector<Point> grahamScan(vector<Point> &points){
    int n = points.size();
    if(n <= 1) return points;

    int idx = 0;
    for(int i = 1; i < n; i++){
        if(points[i].y < points[idx].y || (points[i].y == points[idx].y && points[i].x < points[idx].x)){
            idx = i;
        }
    }
    swap(points[0], points[idx]);

    base = points[0];

    sort(points.begin() + 1, points.end(), cmp);
    vector<Point> hull;

    hull.push_back(points[0]);
    hull.push_back(points[1]);

    for(int i = 2; i < n; i++){
        while(hull.size() > 1 && cross(hull[hull.size() - 2], hull.back(), points[i]) <= 0){
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    return hull;
}

FFT

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<iostream>
#include<complex>
#include<vector>
#include<cmath>

using namespace std;

typedef complex<double> Complex;
const double pi = acos(-1.0);

//递归代码

vector<Complex> recursive_fft(const vector<Complex>& a, bool invert){ //true逆，false顺
    int n = a.size();
    if(n == 1) return a;

    Complex wn(cos(2 * pi / n * (invert == true ? -1 : 1)), sin(2 * pi / n * (invert == true ? -1 : 1)));
    
    Complex w(1, 0);

    vector<Complex> a0(n / 2), a1(n / 2);

    for(int i = 0; i < n / 2; i++){
        a0[i] = a[2 * i];
        a1[i] = a[2 * i + 1];
    }

    vector<Complex> y0 = recursive_fft(a0, invert);
    vector<Complex> y1 = recursive_fft(a1, invert);
    vector<Complex> y(n);

    for(int k = 0; k < n / 2; k++){
        Complex u = y0[k];
        Complex t = w * y1[k];
        y[k] = u + t;
        y[k + n / 2] = u - t;
        w = w * wn;
    }

    return y;
}
vector<Complex> recursive_fft_whole(const vector<Complex>& a, bool invert){
    vector<Complex> y = recursive_fft(a, invert);
    int n = y.size();
    if(invert == true){
        for(int i = 0; i < n; i++){
            y[i] /= n;
        }
    }
    return y;
}

//递归代码
unsigned int rev_x(unsigned int k, int bit_len){
    unsigned int y = 0;
    unsigned int bit;
    for(int i = 0; i < bit_len; i++){
        bit =  (k >> i) & 1;
        y |= (bit << (bit_len - 1 - i));
    }
    return y;
}

vector<Complex> bit_reverse_copy(const vector<Complex>& a){
    int n = a.size();

    int log_n = 0;
    while((1 << log_n) < n) log_n++;

    vector<Complex> A(n);

    for(int k = 0; k < n; k++){
        int reversed_k = rev_x(k, log_n);
        A[k] = a[reversed_k];
    }
    return A;
}
vector<Complex> iterative_fft(vector<Complex> &a, bool invert){
    vector<Complex> A = bit_reverse_copy(a);

    int n = A.size();
    int log_n = 0;
    while((1 << log_n) < n) log_n++;

    for(int s = 1; s <= log_n; s++){
        int m = 1 << s;
        double ang = 2 * pi / m * ((invert == true) ? -1 : 1);
        Complex wm(cos(ang), sin(ang));

        for(int k = 0; k < n; k+=m){
            Complex w(1.0, 0.0);
            for(int j = 0; j < m / 2; j++){
                Complex t = w * A[k + j + m / 2];

                Complex u = A[k + j];

                A[k + j] = u + t;

                A[k + j + m / 2] = u - t;

                w = w * wm;
            }
        }
    }
    if (invert) {
        for (int i = 0; i < n; i++) {
            A[i] /= n;
        }
    }
    return A;
}


int main(){

    //乘法要扩大到大于等于n + m - 1的2的次幂

    vector<Complex> a = {0, 1, 2 ,3 , 5};
    int original_n = a.size();
    int n = 1;
    while (n < a.size()) n <<= 1; // 对于 5，n 会变成 8

    // 3. 补零 (resize 会自动用 0 填充新增的位置)
    a.resize(n); 

    //vector<Complex> y = recursive_fft_whole(a, false);
    vector<Complex> y = iterative_fft(a, false);
    
    for (int i = 0; i < y.size(); i++) {
        // 考虑到浮点误差，输出时稍微处理一下
        double real = abs(y[i].real()) < 1e-10 ? 0 : y[i].real();
        double imag = abs(y[i].imag()) < 1e-10 ? 0 : y[i].imag();
        cout << "y[" << i << "] = " << real << " + " << imag << "i" << endl;
    }
}

多项式相乘

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>
#include<complex>
#include<vector>
#include<cmath>

using namespace std;

typedef complex<double> Complex;
const double pi = acos(-1.0);

//递归代码

//这些没用到
%% vector<Complex> recursive_fft(const vector<Complex>& a, bool invert){ //true逆，false顺
    int n = a.size();
    if(n == 1) return a;

    Complex wn(cos(2 * pi / n * (invert == true ? -1 : 1)), sin(2 * pi / n * (invert == true ? -1 : 1)));
    
    Complex w(1, 0);

    vector<Complex> a0(n / 2), a1(n / 2);

    for(int i = 0; i < n / 2; i++){
        a0[i] = a[2 * i];
        a1[i] = a[2 * i + 1];
    }

    vector<Complex> y0 = recursive_fft(a0, invert);
    vector<Complex> y1 = recursive_fft(a1, invert);
    vector<Complex> y(n);

    for(int k = 0; k < n / 2; k++){
        Complex u = y0[k];
        Complex t = w * y1[k];
        y[k] = u + t;
        y[k + n / 2] = u - t;
        w = w * wn;
    }

    return y;
}
vector<Complex> recursive_fft_whole(const vector<Complex>& a, bool invert){
    vector<Complex> y = recursive_fft(a, invert);
    int n = y.size();
    if(invert == true){
        for(int i = 0; i < n; i++){
            y[i] /= n;
        }
    }
    return y;
} %%

//递归代码
unsigned int rev_x(unsigned int k, int bit_len){
    unsigned int y = 0;
    unsigned int bit;
    for(int i = 0; i < bit_len; i++){
        bit =  (k >> i) & 1;
        y |= (bit << (bit_len - 1 - i));
    }
    return y;
}

vector<Complex> bit_reverse_copy(const vector<Complex>& a){
    int n = a.size();

    int log_n = 0;
    while((1 << log_n) < n) log_n++;

    vector<Complex> A(n);

    for(int k = 0; k < n; k++){
        int reversed_k = rev_x(k, log_n);
        A[k] = a[reversed_k];
    }
    return A;
}
vector<Complex> iterative_fft(vector<Complex> &a, bool invert){
    vector<Complex> A = bit_reverse_copy(a);

    int n = A.size();
    int log_n = 0;
    while((1 << log_n) < n) log_n++;

    for(int s = 1; s <= log_n; s++){
        int m = 1 << s;
        double ang = 2 * pi / m * ((invert == true) ? -1 : 1);
        Complex wm(cos(ang), sin(ang));

        for(int k = 0; k < n; k+=m){
            Complex w(1.0, 0.0);
            for(int j = 0; j < m / 2; j++){
                Complex t = w * A[k + j + m / 2];

                Complex u = A[k + j];

                A[k + j] = u + t;

                A[k + j + m / 2] = u - t;

                w = w * wm;
            }
        }
    }
    if (invert) {
        for (int i = 0; i < n; i++) {
            A[i] /= n;
        }
    }
    return A;
}

vector<Complex> multiply(const vector<Complex>&a, const vector<Complex>& b){
    int n = a.size();
    vector<Complex> res(n);

    for(int i = 0; i < n; i++){
        res[i] = a[i] * b[i];
    }
    return res;
}

int main(){
    vector<Complex> a = {9, 1, 2, 3};
    vector<Complex> b = {2, 3, 4};

    int origin_n = a.size() + b.size() - 1;

    int n = 1;
    while(n < origin_n) n <<= 1;
    a.resize(n);
    b.resize(n);


    vector<Complex> u = iterative_fft(a, false);
    vector<Complex> v = iterative_fft(b, false);

    vector<Complex> res = multiply(u, v);

    res = iterative_fft(res, true);

        for (int i = 0; i < origin_n; i++) {
        // 考虑到浮点误差，输出时稍微处理一下
        double real = abs(res[i].real()) < 1e-10 ? 0 : res[i].real();
        double imag = abs(res[i].imag()) < 1e-10 ? 0 : res[i].imag();
        cout << "y[" << i << "] = " << real << " + " << imag << "i" << endl;
    }
}

拓展欧几里得

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

using namespace std;

int Exgcd(int a, int b, int* x, int *y){
    if(b == 0){
        *x = 1;
        *y = 0;
        return a;
    }else{
        int xx, yy;
        int d = Exgcd(b, a % b, &xx, &yy);

        *x = yy;
        *y = xx - (a / b) * yy;
        return d;
    }
    
}

int main(){
    int a = 15;
    int b = 21;
    int c = 0;
    int cc = 0;
    int* x = &c;
    int* y = &cc;

    int d = Exgcd(a, b, x, y);
    cout << d << ' ' << *x << ' ' << *y;
}

平面最近点对

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<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct{
    double x;
    double y;
}point;

point p[500005],temp[500005],buf[500005];


double dist(point a, point b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); 
}

int cmp_x(const void *a, const void *b){
    point *p1 = (point *)a;
    point *p2 = (point *)b;
    if(p1 -> x > p2 -> x)
        return 1;
    return -1;
}

double solve(int l, int r){
    if(r - l <= 2){
        double min = 1e7;
        for(int i = l; i <= r; i++){
            for(int j = i + 1; j <= r; j++){
                if(dist(p[i], p[j]) < min)
                    min = dist(p[i], p[j]);
            }
        }
        for(int i = l + 1; i <= r; i++){
            point key = p[i];
            int j = i - 1;
            while(j >= l && p[j].y > key.y){
                p[j + 1] = p[j];
                j--;
            }
            p[j + 1] = key;
        }
        return min;
    }
    //最短距离和插入排序
    
    int mid = (l + r) / 2;
    double midx = p[mid].x;
    double d = fmin(solve(l, mid), solve(mid + 1, r));
    
    int i = l,j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(p[i].y <= p[j].y) temp[k++] = p[i++];
        else temp[k++] = p[j++];
    }
    while(i <= mid) temp[k++] = p[i++];
    while(j <= r) temp[k++] = p[j++];

    for (i = l; i <= r; i++) p[i] = temp[i];

    int sz = 0;
    for(int i = l; i <= r; i++){
        if(fabs(p[i].x - midx) < d){
            buf[sz++] = p[i];
        }
    }

    for(int i = 0; i < sz; i++){
        for(j = i + 1; j <= i + 7 && j < sz; j++){
            double t = dist(buf[i], buf[j]);
            if(t < d) d = t;
        }
    }
    return d;
}
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    qsort(p, n, sizeof(p[0]), cmp_x);

    double ans = solve(0 ,n - 1);
    printf("%.4f", ans);
    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
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
#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 1. 预处理 next 数组
// next[i] 表示 P[0...i] 中最长的相同真前后缀的长度
vector<int> computeNext(const string& P) {
    int m = P.length();
    vector<int> next(m);
    next[0] = 0; // 第一个字符没有真前后缀
    
    for (int i = 1, j = 0; i < m; i++) {
        // 如果不匹配，j 回退到前一个可能匹配的位置
        while (j > 0 && P[i] != P[j]) {
            j = next[j - 1];
        }
        // 如果匹配，j 推进
        if (P[i] == P[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

// 2. KMP 匹配过程
void KMP(const string& T, const string& P) {
    int n = T.length();
    int m = P.length();
    if (m == 0) return;

    vector<int> next = computeNext(P);

    for (int i = 0, j = 0; i < n; i++) {
        // 文本 T[i] 与 模式串 P[j] 匹配失败
        while (j > 0 && T[i] != P[j]) {
            j = next[j - 1]; // 关键：利用 next 数组快速跳过
        }
        
        if (T[i] == P[j]) {
            j++;
        }

        // 找到一个完整匹配
        if (j == m) {
            cout << "在位移 " << i - m + 1 << " 处找到匹配" << endl;
            j = next[j - 1]; // 继续寻找下一个可能的匹配
        }
    }
}

PA算法字符串找子串

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
#include <iostream>
#include <vector>
#include <string>

using namespace std;

/**
 * 优化后的 PA 算法构建函数
 * 复杂度：O(m * alphabetSize)
 */
vector<vector<int>> computeTransitionTableFast(const string& P) {
    int m = P.length();
    int alphabetSize = 256; // 支持标准 ASCII
    
    // 初始化转移表，所有状态初始化为 0
    vector<vector<int>> delta(m + 1, vector<int>(alphabetSize, 0));

    // 基础情况：在状态 0 时，只有遇到模式串的第一个字符才能跳到状态 1
    if (m > 0) {
        delta[0][(unsigned char)P[0]] = 1;
    }

    int restartState = 0; // 影子状态（类似 KMP 中的跳转位置）

    // 从状态 1 开始填充矩阵
    for (int q = 1; q < m; q++) {
        // 1. 复制影子状态的所有转移路径
        // 因为“当前部分匹配”失败后的回退逻辑与“影子状态”是一致的
        for (int a = 0; a < alphabetSize; a++) {
            delta[q][a] = delta[restartState][a];
        }

        // 2. 覆盖“匹配成功”的路径，使其向下一个状态推进
        delta[q][(unsigned char)P[q]] = q + 1;

        // 3. 更新影子状态：模拟把当前字符 P[q] 输入自动机会跳到哪
        // 这为下一个状态 q+1 的“失败回退”做好了准备
        restartState = delta[restartState][(unsigned char)P[q]];
    }

    // 最后一个状态（完全匹配状态）的转移逻辑
    // 当找到完整匹配后，自动机应根据当前输入跳转到“下一个可能的匹配起点”
    for (int a = 0; a < alphabetSize; a++) {
        delta[m][a] = delta[restartState][a];
    }

    return delta;
}

/**
 * 匹配查找函数
 * 复杂度：O(n)
 */
void search(const string& T, const string& P) {
    int n = T.length();
    int m = P.length();
    if (m == 0) return;

    // 1. 构建优化后的表
    vector<vector<int>> delta = computeTransitionTableFast(P);

    // 2. 扫描文本
    int q = 0;
    for (int i = 0; i < n; i++) {
        q = delta[q][(unsigned char)T[i]];
        if (q == m) {
            cout << "find,index: " << i - m + 1 << endl;
        }
    }
}

int main() {
    string text = "abacababacaababacaababacaababaca";
    string pattern = "ababaca";

    cout << "text: " << text << endl;
    cout << "pattern: " << pattern << endl;
    search(text, pattern);

    return 0;
}

24级考试题（回忆版

第一道诚信题

第二道选择题
有一个算时间复杂度，$T(n)=T(\frac{n}{2})+T(\frac{n}{4})+n$
有一个问KMP预处理过程和查找过程各自的时间复杂度
有一个问是不是BFS能求出所有权值为1的图的最短路径，但是DFS不能求出权值任意的点的最短路径
有一个问graham算法中以下代码片段的时间复杂度

1
2
3
4
5
6
7
for(int i = 2; i < n; i++){
	while(hull.size() > 1 && cross(hull[hull.size() - 2], hull.back(), points[i]) <= 0){
		hull.pop_back();
	}
	hull.push_back(points[i]);
}
return hull;

可能还有但是忘了

第三题是KMP板子，一模一样（再次强调板子正确的重要性

第四题是输入T个n个节点m条边的无向图，判断它是不是树（n个点，n-1条边并且联通）

第五题是贪心（n个人，输入每个人无奖、获A奖、获B奖的快乐值，你只有一个A奖和一个B奖，问总快乐值最大是多少

第六题是kfc逆序对（和上面板子的K重逆序对几乎一模一样,只需要把(long long)a[i] > (long long)kk * a[j]改成题干给的条件就行了

第七题是逆天凸包题，给n个点，求出这群点的凸包，再把凸包上的点去掉，通过若干次这样的操作 问多少次才会把所有的点都去掉，最后一次去掉了多少个点，并且输出最后一次去掉的点的坐标（按照题目输入的顺序）（这破题我敲了四十分钟怒拿0分

第八题是动态规划，忘了，反正不会做，直接输出No可以混0.3分

第九题是最短路径。给n个点，m条边，每条边有自己的权值和一个快乐值，你可以让任意一条路径上快乐值最大的一条边的权值变成0，问最短路径的总权值是多少。

第十题没看，据说是FFT

  • Title: 算法板子+期末考试题（回忆版
  • Author: Connor
  • Created at : 2026-01-25 00:04:07
  • Updated at : 2026-01-27 02:15:15
  • Link: https://redefine.ohevan.com/2026/01/25/Algorithm/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
算法板子+期末考试题（回忆版
  1. 说在前面
    1. 一些常识知识：
      1. 领域核心人物 ：
      2. 一些特殊时间复杂度：
  2. P、NP、NPC、NPH
    1. 1. 复杂性等级 (Complexity Classes)
    2. 2. 归约 (Reduction) 的逻辑
  3. 二、 关键人物与标志性事件
  4. 三、 经典例子与对比总结
    1. 1. P 类问题（看到它们就选“容易”、“多项式时间可解”）
    2. 2. NP-Complete / NP-Hard 问题（看到它们选“目前难解”、“NPC”）
    3. 3. 特殊案例：大数分解 (Integer Factorization)
  5. 四、 考试易错命题点拨
  6. c++
    1. 配置dev
    2. 字符串
    3. 字符串split
    4. 字符串去前后空格
    5. 二分查找
      1. C
      2. C++
    6. string和char*
  7. 快速幂
  8. 插入排序
  9. 归并排序
    1. 计算逆序数
    2. k重逆序对
  10. 寻找第k大的数和快速排序
  11. moore庄园投票
  12. 卡特兰数
  13. 高精度乘法
    1. $O(n^2)$
    2. $O(nlgn)$
  14. 矩阵链
  15. 钢管切割
  16. 流水线调度
  17. OBST最优二叉搜索树
    1. 有查找失败概率的OBST
    2. 无查找失败概率的OBST
  18. 01/完全背包问题
    1. 二维数组版
    2. 一维数组版
    3. 01背包问题，dp[w]版本
  19. 最长不上升子序列/导弹拦截
  20. 最长等差序列
  21. 最长公共子序列
  22. 编辑距离
  23. 区间动态规划
    1. 回文子串
    2. 石子合并
      1. 题目描述
      2. 输入格式
    3. zuma问题/回文子串数
      1. 输入格式
      2. 输出格式
  24. 树形动态规划
    1. 没有上司的舞会
  25. 背包问题
    1. 二维数组
    2. 一维数组
    3. 分组背包
    4. 多重背包
  26. 贪心，最多能上多少节课
  27. 哈夫曼编码/解码
  28. bfs dfs
  29. Bellman-Ford
  30. 拓扑排序+松弛求最短路径
  31. floyd算法
  32. dj算法求最短路
    1. 邻接矩阵版
    2. 邻接表
  33. prim最小生成树
  34. dinic算最大流/最大割
  35. 最大二分匹配
    1. dinic找最大二分匹配
    2. 匈牙利算法
  36. 计算几何，叉积，相交
  37. 凸包
  38. FFT
  39. 多项式相乘
  40. 拓展欧几里得
  41. 平面最近点对
  42. KMP
  43. PA算法字符串找子串
  44. 24级考试题（回忆版