算法学习笔记

前言

此笔记大致按照AcWing - 算法基础课顺序整理，各算法中的链接绝大部分为我真实在b站学完的网课，还包含部分CSDN和OI维基百科中的内容，希望对你有所帮助。

排序算法

https://blog.csdn.net/2301_80215560/article/details/136604635?sharetype=blog&shareId=136604635&sharerefer=APP&sharesource=2401_87034440&sharefrom=link

左程云 https://b23.tv/biO1uQB

https://github.com/algorithmzuo/algorithm-journey

004 021 023 025 028 029

冒泡排序

相邻两个元素的值进行两两比较，若发现前一个数大于后一个数则交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void BubbleSort(int* a, int n)
{
	int end = n - 1;//不能是n，不然会越界
	while(end)
	{
		bool exchange = false;//优化，比较之后没有交换，说明已经排好了，就break循环
		for (int i = 0; i < end; i++)
		{
			if (a[i] < a[i + 1])
			{
				swap(&a[i], &a[i + 1]);//交换
				exchange++;
			}
		}
		if (exchange == false) break;
		end--;
	}
}

归并排序

左程云021、022 https://b23.tv/biO1uQB

拆分原数组，分别排序，再 merge 归并。归并排序是一种稳定的排序算法，时间复杂度为 O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge(vector<int>& nums, int l, int m, int r) {
    vector<int> L(m - l + 1), R(r - m);
    for (int i = 0; i < L.size(); ++i) L[i] = nums[l + i];
    for (int j = 0; j < R.size(); ++j) R[j] = nums[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < L.size() && j < R.size())
        nums[k++] = L[i] <= R[j] ? L[i++] : R[j++];
    while (i < L.size()) nums[k++] = L[i++];
    while (j < R.size()) nums[k++] = R[j++];
}
void mergeSort(vector<int>& nums, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(nums, l, m);
        mergeSort(nums, m + 1, r);
        merge(nums, l, m, r);
    }
}

桶排序、基数排序、计数排序

左程云028

这三种排序算法都不基于比较，对数据特征有要求。计数排序适用于已知数值范围的场景；基数排序通常要求处理十进制非负整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
思路：大问题化小
桶排序(Bucket sort)或所谓的箱排序，是一种分块的排序算法，工作的原理是将数组分到有限数量的桶里，
每个桶的大小都相等。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
把待排序序列（数组）中的数据根据函数映射方法分配到若干个桶中，
在分别对各个桶进行排序，最后依次按顺序取出桶中的数据。
适用于数据分配均匀，数据比较大，相对集中的情况。
void bucketSort(vector<double>& arr) {
    int n = arr.size();
    vector<vector<double>> buckets(n);
    for (double num : arr) {
        int idx = n * num;
        buckets[idx].push_back(num);
    }
    for (auto& bucket : buckets) sort(bucket.begin(), bucket.end());
    int idx = 0;
    for (auto& bucket : buckets)
        for (double num : bucket) arr[idx++] = num;
}
1
2
3
4
5
//计数排序 一种特殊的排序，没有比较
例（仅有0-10）
0 1 2 3 4 5 6 7 8 9 10
以数组的下标当做数值，有这个数的时候a[i]++; 
局限：适用于整数。数要求集中（否则空间的浪费大）

基数排序(一般要求为十进制非负整数)

左程云028

https://www.bilibili.com/video/BV1Lh4y1c7Aw?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

判断最大的位数是几位，对每一位进行桶排序。

从个位开始，数组按个位数字大小入桶，然后从0-9倒出，此后十位百位同上循环，最终结果即有序。从低位开始作用为保留低位大小关系。

技巧1 前缀分区做桶排列

统计每个数字出现次数后做前缀和得到数组(x)，则从右向左遍历原数组时，该数字在保留相对次序情况下应该出现在x数组对应的数字-1的位置，做完此操作后x数组对应数字–。

故该技巧可以用于基数排序时对每一位数字进行排序任务。

技巧2 怎么得到每一位

用一个变量offset初始化为1，所求数字n。(n/offset)%10该位数操作玩后offset*=10依次得到每一位数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
最终code
    // 理解的时候可以假设BASE = 10
		for (int offset = 1; bits > 0; offset *= BASE, bits--) {
			Arrays.fill(cnts, 0);
			for (int i = 0; i < n; i++) {
				// 数字提取某一位的技巧
				cnts[(arr[i] / offset) % BASE]++;
			}
			for (int i = 1; i < BASE; i++) {
				cnts[i] = cnts[i] + cnts[i - 1];
			}
			for (int i = n - 1; i >= 0; i--) {
				// 前缀数量分区的技巧
				// 数字提取某一位的技巧
				help[--cnts[(arr[i] / offset) % BASE]] = arr[i];
			}
			for (int i = 0; i < n; i++) {
				arr[i] = help[i];
			}
		}

二分

二分查找

左程云006 https://b23.tv/biO1uQB

l、r 为区间左右端点，比较值为 target t（寻找 t）。需保证数组有序，若 ＞（m 为区间中点），则向右二分；若 ＜，则向左二分。当 l≥r 时结束，时间复杂度 O(logn)。

1
2
3
4
5
6
7
8
9
10
int binarySearch(const vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (nums[m] == target) return m;
        else if (nums[m] < target) l = m + 1;
        else r = m - 1;
    }
    return -1;
}

二分答案

左程云051 https://b23.tv/biO1uQB

一只会code的小金鱼 https://b23.tv/vFaRbc9

写函数f，f函数作用为得到一个过程的答案，二分从最极限的最大可能到最小可能答案。我们则可以同f判断能否达到题目的需求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool f(int x, int n, const vector<int>& a, const vector<int>& b) {
    int sum = 0;
    for (int i = 0; i < a.size(); ++i) sum += x / b[i] * a[i];
    return sum >= n;
}
int binaryAnswer(int n, const vector<int>& a, const vector<int>& b) {
    int l = 0, r = 1e9, ans = -1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (f(m, n, a, b)) { ans = m; r = m - 1; }
        else l = m + 1;
    }
    return ans;
}
例

n台打印机，每台打印机的效率分别是a张b秒。

问打印到第n张纸是多少秒

设打印第n张纸x秒

f函数可以求出x秒时具体可以打印多少张纸

x/b*a和n张比，够了记答案往左二分，不够则不记答案往右二分，最大给1e9

高精度

（用数组模拟 列竖式计算）

麦克老师讲算法 高精度算法全套 https://b23.tv/sArWoTg

高精度计算 - OI Wiki

高精度加法

处理两个大整数相加，用数组存储每一位，模拟进位操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
string add(string num1, string num2) {
    string res;
    int carry = 0, i = num1.size() - 1, j = num2.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += num1[i--] - '0';
        if (j >= 0) sum += num2[j--] - '0';
        res.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

高精度减法

处理两个大整数相减，用数组存储每一位，模拟借位操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string subtract(string num1, string num2) {
    if (num1 < num2) return "-" + subtract(num2, num1);
    string res;
    int borrow = 0, i = num1.size() - 1, j = num2.size() - 1;
    while (i >= 0) {
        int diff = (num1[i] - '0') - borrow;
        if (j >= 0) diff -= (num2[j] - '0');
        if (diff < 0) { diff += 10; borrow = 1; }
        else borrow = 0;
        res.push_back(diff + '0');
        i--; j--;
    }
    // 移除前导零
    while (res.size() > 1 && res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

前缀和与差分

https://blog.csdn.net/weixin_45629285/article/details/111146240?sharetype=blog&shareId=111146240&sharerefer=APP&sharesource=2401_87034440&sharefrom=link

前缀和 & 差分 - OI Wiki

一维前缀和

作用，可以快速求出区间l 到 r之间数之和。

只需要执行 sum[r] - sum[l - 1]。输出原序列中从第l个数到第r个数的和的时间复杂度变成了O(1)。

1
2
3
4
5
6
7
8
9
10
11
vector<int> prefixSum(const vector<int>& nums) {
    int n = nums.size();
    vector<int> sum(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + nums[i - 1];
    return sum;
}
// 查询区间[l,r]的和
int query(const vector<int>& sum, int l, int r) {
    return sum[r + 1] - sum[l];
}

二维前缀和

二维前缀和预处理公式

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

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

1
2
3
4
5
6
7
8
9
10
11
12
vector<vector<int>> prefixSum2D(const vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> s(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + matrix[i - 1][j - 1];
    return s;
}
// 查询子矩阵(x1,y1)-(x2,y2)的和
int query2D(const vector<vector<int>>& s, int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

一维差分

结论：给a数组中的[ l, r] 区间中的每一个数都加上c,

只需对差分数组b做 b[l] + = c, b[r+1] - = c 。

构造差分数组，差分为前缀和的逆运算。可以做到快速为数组中的每个值进行加减运算。

二维差分

(思路同一维)

构造方法，结论：

1
b[i][j] = a[i][j] − a[i − 1][j] − a[i][j − 1] + a[i − 1 ][j − 1]

双指针算法

左程云050 https://b23.tv/biO1uQB

1有的双指针知识单纯用到两个指针

2有的则包含单调性（贪心）方面的思考与分析

常见类型：1）同向双指针 2）快慢双指针 3）从两端向中间的双指针

位运算

左程云003 031 033 https://b23.tv/biO1uQB

直接操作二进制位，用于高效计算。

1
2
3
4
5
6
7
8
9
10
bool isOdd(int n) { return n & 1; } // 判断奇偶
int lowbit(int n) { return n & -n; } // 获取最低位1
int countOnes(int n) { // 计算二进制中1的个数
    int cnt = 0;
    while (n) {
        n &= n - 1; // 清除最低位1
        cnt++;
    }
    return cnt;
}

位图

左程云032 https://b23.tv/biO1uQB

用bit组成数组存放值，用bit01代表存在与否，取存用位运算。

限制 必须连续范围，不能过大。

优点 极大的节省空间

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
class Bitset {
private:
    vector<int> set;
public:
    Bitset(int n) {
        set.resize((n + 31) / 32, 0);
    }
    void add(int num) {
        int index = num / 32;
        int bitPos = num % 32;
        set[index] |= (1 << bitPos);
    }
    void remove(int num) {
        int index = num / 32;
        int bitPos = num % 32;
        set[index] &= ~(1 << bitPos);
    }
    void reverse(int num) {
        int index = num / 32;
        int bitPos = num % 32;
        set[index] ^= (1 << bitPos);
    }
    bool contains(int num) {
        int index = num / 32;
        int bitPos = num % 32;
        return ((set[index] >> bitPos) & 1) == 1;
    }
};

离散化

左程云048

【算法讲解048【必备】二维前缀和、二维差分、离散化技巧】

https://www.bilibili.com/video/BV1Wz4y1K74C?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

将无限或大范围的数值映射到有限、连续的整数区间，保留相对大小关系，用于优化数据范围过大的问题（如坐标压缩、频率统计）。

1
2
3
4
5
6
7
8
9
10
11
12
// 离散化单个值x（tmp为排序去重后的数组）
int idx = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
lower_bound 返回第一个≥当前值的位置，保证相同值映射到同一下标
    
vector<int> discretize(vector<int>& nums) {
    vector<int> tmp = nums;
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    for (auto& x : nums)
        x = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
    return nums;
}

区间合并

合并重叠区间，先按左端点排序，再遍历合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);
    for (auto& interval : intervals) {
        if (interval[0] <= merged.back()[1])
            merged.back()[1] = max(merged.back()[1], interval[1]);
        else
            merged.push_back(interval);
    }
    return merged;
}

数据结构

【【强烈推荐】深入浅出数据结构 - 顶尖程序员图文讲解 - UP主翻译校对 (已完结)】

https://www.bilibili.com/video/BV1Fv4y1f7T1?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

邻接矩阵

存储特点：

使用二维数组 g[i][j] 表示顶点 i 到 j 的连接关系

无向图的矩阵是对称的，有向图可能不对称

矩阵中 1 表示有边，0 或 ∞ 表示无边（带权图存储权重值）

优点：

  1. 实现简单，支持快速查询任意两顶点间是否有边（O (1)）
  2. 便于计算每个顶点的度（行 / 列和）
  3. 适合稠密图（边数接近顶点数平方）

缺点：

  1. 空间复杂度高（O (V²)），存储稀疏图时浪费大量空间（V：顶点vertex E：边edge）
  2. 添加 / 删除顶点需重新调整矩阵大小，效率低
  3. 统计边的总数需要遍历整个矩阵（O (V²)）

链表与邻接表

优点：

  1. 空间效率高（O (V+E)），适合稀疏图（边数远小于顶点数平方）
  2. 便于添加 / 删除顶点和边
  3. 遍历所有边的时间复杂度为 O (E)

缺点：

  1. 判断两顶点间是否有边效率较低（O (degree (v))）
  2. 计算顶点的度需遍历对应链表（O (degree (v))）
  3. 不适合频繁查询任意两顶点间的关系

栈与队列

最小栈（O (1) 获取最小值）

左程云015

https://www.bilibili.com/video/BV15X4y177cM?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

维护一个最小栈minval包含getmin功能 若入栈元素x小于等于最小栈的栈顶则x入最小栈

minVal.empty() || x <= minVal.top()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MinStack {
    stack<int> data, minVal;
public:
    void push(int x) {
        data.push(x);
        if (minVal.empty() || x <= minVal.top())
            minVal.push(x);
    }
    void pop() {
        if (data.top() == minVal.top())
            minVal.pop();
        data.pop();
    }
    int getMin() { return minVal.top(); }
};
单调栈（下一个更大元素）

实现原理：以单调递增栈为例，当新元素入栈时，会将栈中所有比它大的元素弹出，直到栈为空或者栈顶元素小于等于新元素，然后将新元素入栈。单调递减栈则相反。

遍历每个元素时，将当前元素与栈顶元素比较：

若当前元素小于等于栈顶元素 → 直接入栈，保持栈的递增性

若当前元素大于栈顶元素 → 触发以下操作：

  1. 弹出栈顶元素，并记录当前元素为其「下一个更大值」
  2. 持续弹出新的栈顶元素，直到当前元素 ≤ 栈顶
  3. 当前元素入栈，恢复栈的递增顺序

这个过程中，每个元素被弹出时，其「下一个更大值」即为触发弹出的当前元素。遍历结束后，栈内剩余元素的「下一个更大值」均为默认值（如 - 1 或无穷大）。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            res[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}
单调队列（滑动窗口最大值）

实现原理：通常用双端队列来实现。以单调递增队列为例，当新元素要入队时，从队尾开始比较，如果队尾元素大于新元素，则将队尾元素出队，直到队尾元素小于等于新元素或者队列为空，然后将新元素从队尾入队。在进行出队操作时，如果队首元素超出了当前考虑的范围，则将队首元素出队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> dq;
    for (int i = 0; i < nums.size(); ++i) {
        // 移除队尾较小元素
        while (!dq.empty() && nums[i] >= nums[dq.back()])
            dq.pop_back();
        dq.push_back(i);
        // 移除窗口外元素
        if (dq.front() <= i - k)
            dq.pop_front();
        if (i >= k - 1)
            res.push_back(nums[dq.front()]);
    }
    return res;
}

KMP 算法以及find()字符串匹配

左程云100 、101 https://b23.tv/biO1uQB

核心思想：利用已经匹配过的部分信息，避免不必要的字符比较，从而提高匹配效率。

通过预处理模式串的 next 数组，记录模式串中每个位置之前最长的相同前缀和后缀长度。

Next 数组含义： next[i] 表示模式串 pattern[0..i] 的最长公共前后缀长度。 例如：pattern = "ababc"，其 next 数组为 [0, 0, 1, 2, 0]。

匹配过程优化： 当主串 S[i] 与模式串 P[j] 不匹配时，直接将 j 回退到 next[j-1]，而主串指针 i 不回退。

总结：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
53
54
55
56
57
58
59
60
61
int main() {
    string str = "hello world, world!";
    string substr = "world";
    string charset = "aeiou";
    string digits = "0123456789";
    // 1. 基本查找：find() 和 rfind()
    size_t pos1 = str.find(substr);            // 正向查找子串，返回6
    size_t pos2 = str.find(substr, 7);         // 从位置7开始查找，返回13
    size_t pos3 = str.rfind(substr);           // 反向查找子串，返回13
    size_t pos4 = str.find('o');               // 查找字符，返回4
    size_t pos5 = str.find('o', 5);            // 从位置5开始查找字符，返回7

    // 2. 查找任意字符：find_first_of() 和 find_last_of()
    size_t pos6 = str.find_first_of(charset);  // 查找首个元音字母，返回1('e')
    size_t pos7 = str.find_last_of(charset);   // 查找最后一个元音字母，返回11('o')

    // 3. 查找非指定字符：find_first_not_of() 和 find_last_not_of()
    string spaces = "   abc   ";
    size_t pos8 = spaces.find_first_not_of(' '); // 查找首个非空格字符，返回3('a')
    size_t pos9 = spaces.find_last_not_of(' ');  // 查找最后一个非空格字符，返回5('c')

    // 4. 遍历所有匹配位置
    cout << "所有 'world' 的位置：";
    size_t currentPos = 0;
    while ((currentPos = str.find(substr, currentPos)) != string::npos) {
        cout << currentPos << " ";
        currentPos += substr.length(); // 跳过已匹配的部分
    }
    cout << endl; // 输出: 6 13

    // 5. 检查字符串是否包含子串
    bool hasWorld = (str.find(substr) != string::npos); // true

    // 6. 处理未找到的情况
    size_t notFound = str.find("xyz");
    if (notFound == string::npos) {
        cout << "'xyz' 未找到" << endl;
    }

    // 7. 特殊情况：空字符串查找
    size_t emptyPos = str.find(""); // 始终返回0（空字符串被视为存在于字符串开头）

    // 8. 查找首个非数字字符
    string numStr = "123.45";
    size_t dotPos = numStr.find_first_not_of(digits); // 返回3('.')

    // 输出所有结果
    cout << "pos1: " << pos1 << endl; // 6
    cout << "pos2: " << pos2 << endl; // 13
    cout << "pos3: " << pos3 << endl; // 13
    cout << "pos4: " << pos4 << endl; // 4
    cout << "pos5: " << pos5 << endl; // 7
    cout << "pos6: " << pos6 << endl; // 1
    cout << "pos7: " << pos7 << endl; // 11
    cout << "pos8: " << pos8 << endl; // 3
    cout << "pos9: " << pos9 << endl; // 5
    cout << "hasWorld: " << (hasWorld ? "true" : "false") << endl; // true
    cout << "dotPos: " << dotPos << endl; // 3

    return 0;
}

Trie 树（字典树）

左程云044 045 https://b23.tv/biO1uQB

Trie 树通过共享字符串前缀存储多组单词，使查询效率仅取决于字符串长度，适合高频前缀匹配场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct TrieNode {
    vector<TrieNode*> children;  // 子节点数组（假设仅包含小写字母）
    bool isEndOfWord;            // 标记是否为单词结尾
    
    TrieNode() : children(26, nullptr), isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() { root = new TrieNode(); }
    
    // 插入字符串
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEndOfWord = true;  // 标记单词结尾
    }
    
    // 查找字符串
    bool search(string word) {
        TrieNode* node = searchPrefix(word);
        return node != nullptr && node->isEndOfWord;
    }
    
    // 查找前缀
    bool startsWith(string prefix) {
        return searchPrefix(prefix) != nullptr;
    }

private:
    // 辅助函数：查找前缀路径
    TrieNode* searchPrefix(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return nullptr;
            node = node->children[idx];
        }
        return node;
    }
};

并查集（合并查询集合）

蓝不过海呀

https://www.bilibili.com/video/BV1zZRSYUEWV?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

麦克老师讲算法

https://www.bilibili.com/video/BV1jv411a7LK?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

合并 查询 集合

用数组 保存每个节点的父亲

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 p[MAXN];
void Initial(int n){
    for(int i=0; i<n; i++) {
        p[i]=-1;
    }
}
void Union(int x,int y){
    int rootx = Find(x);
    int rooty = Find(y);
    if(rootx!=rooty){//按大小合并
        if(p[rootx]<p[rooty]){
            p[rooty]=rootx;
        } else if(p[rootx]>p[rooty]){
            p[rootx]=rooty;
        } else {
            p[rootx]=rooty;
            p[rooty]--;
        }
    }
    if(rootx!=rooty){//按照高度合并
        if(p[rootx]<p[rooty]){
            p[rootx]+=p[rooty];
            p[rooty]=rootx;
        }else{
            p[rooty]+=p[rootx];
            p[rootx]=rooty;
        }
    }
}
int Find(int x){
    if(p[x]<0)
        return x;
    else
        return Find(p[x]);
}

堆（优先队列）

高效维护和获取极值（最大值或最小值），并支持快速插入、删除操作。一般使用stl库中函数

1
2
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

Hash 表（两数之和）

左程云026 https://b23.tv/biO1uQB

作用为快速查找 / 统计

https://www.bilibili.com/video/BV13m4y1p7VB?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

只用存元素 unordered_set 需要存元素 + 额外信息 unordered_map

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
unordered_map<int, int> mp;
/*去重 / 判重	unordered_set	自动去重，仅需检查元素存在性（如判断数组是否有重复元素）。
统计频率 / 映射关系	unordered_map	需要存储键值对（如统计字符出现次数、记录节点距离）。
缓存中间结果	unordered_map	需要同时存储输入和计算结果（如记忆化搜索）。
快速查找补数 / 配对	unordered_map	需要键值对关联（如两数之和问题，需快速查找目标值的补数）。*/
struct Point { int x, y; };
struct PH { size_t operator()(const Point& p) const {
    return p.x ^ p.y; // 简化哈希函数
}};

int main() {
    // 基础用法
    unordered_set<int> s = {1,2,3};
    s.insert(4);        // 插入
    s.erase(2);         // 删除
    bool exists = s.count(3); // 存在检查
    auto it = s.find(1); // 迭代器查找

    // 自定义类型
    unordered_set<Point, PH> points;
    points.insert({1,2});

    // 遍历
    for (auto& e : s) { /* 使用e */ }
}

搜索与图论

DFS 与 BFS

DFS（深度优先搜索）

一只会code的小金鱼 https://b23.tv/vFaRbc9

排列，指数级 深入探索分支至无法继续，然后回溯后探索其他分支。核心在于递归

DFS适合此类题目：给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。

1
2
3
4
5
6
void dfs(vector<vector<int>>& adj, int u, vector<bool>& visited) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v])
            dfs(adj, v, visited);
}
BFS（广度优先搜索）

**左程云062 ** https://b23.tv/biO1uQB

一只会code的小金鱼 https://b23.tv/vFaRbc9

队列，逐层扩散，扩散几层最短路就是多少，可以单点弹出，整层弹出。标记状态数组，剪枝。

使用要求：任意两相邻节点距离等同(边权相同)。

二段性：一边全符合，另一边全不符合，且队列内最多两种状态。x和x+1。

bfs队列具有的性质：单调性 单调增减

多源bfs

提前把源头存入队列(有个虚拟的源点连接多个边权为0的点(多个源头))。

01bfs

双端队列 队头入队or队尾入队

双向bfs

左程云063

维护两个队列，需要知道起点和终点位置，从起点和终点同时开始bfs，维护状态数组记录两个bfs到的状态，若碰上则证明可以从起点到终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> bfs(vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

拓扑排序（有向无环图）

拓扑排序是对 ** 有向无环图（DAG）** 的顶点进行排序的算法，使得对于每条有向边 (u→v)，顶点 u 在排序中均出现在 v 之前，常用 Kahn 算法（入度队列）或 DFS 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> topologicalSort(vector<vector<int>>& adj, int n) {
    vector<int> inDegree(n, 0);
    for (auto& edges : adj)
        for (int v : edges)
            inDegree[v]++;
    queue<int> q;
    for (int i = 0; i < n; ++i)
        if (inDegree[i] == 0)
            q.push(i);
    vector<int> res;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res.push_back(u);
        for (int v : adj[u])
            if (--inDegree[v] == 0)
                q.push(v);
    }
    return res.size() == n ? res : vector<int>();
}

最短路

左程云064

https://www.bilibili.com/video/BV1Cm4y1g77W?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

Dijkstra 算法（单源最短路径）
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
typedef pair<int, int> PII; // {距离, 节点编号}
// 输入：邻接表graph，源点src，输出：源点到各点的最短距离数组dist
vector<int> dijkstra(vector<vector<PII>>& graph, int src) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX); // 初始化距离为无穷大
    dist[src] = 0; // 源点到自身距离为0
    // 最小堆（优先队列）
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, src}); // {距离, 节点}
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        
        // 跳过已处理的节点（避免重复计算）
        if (d > dist[u]) continue;
        
        // 遍历所有邻接边
        for (auto [v, w] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}
int main() {
    int n = 5; // 节点数
    vector<vector<PII>> graph(n); // 邻接表
    // 添加边 (u->v 权重为w)
    graph[0].push_back({1, 2}); // 0->1 权重2
    graph[0].push_back({2, 4}); // 0->2 权重4
    graph[1].push_back({2, 1}); // 1->2 权重1
    graph[1].push_back({3, 7}); // 1->3 权重7
    graph[2].push_back({3, 3}); // 2->3 权重3
    graph[3].push_back({4, 2}); // 3->4 权重2
    vector<int> dist = dijkstra(graph, 0);
    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << "从节点0到节点" << i << "的最短距离是: ";
        if (dist[i] == INT_MAX) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
    
    return 0;
}
a*算法

左程云065

https://www.bilibili.com/video/BV1t94y187zW?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

问从特定点到特定点的最短距离

与dijkstra算法distance数组相同，区别在小根堆的使用时加一个曼哈顿距离(估计一个长度，影响小根堆弹出顺序，致使运行时间缩短)

距离

距离 - OI Wiki

欧氏距离，一般也称作欧几里得距离，空间两点间的欧氏距离为：根号下a方+b方+c方

缺点：两个整点计算其欧氏距离时，往往答案是浮点型，会存在一定误差。

曼哈顿距离（Manhattan distance）

为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。可以表示为：|x1-x2|+|y1-y2|

[P5098 USACO04OPEN] Cave Cows 3 - 洛谷

切比雪夫距离

是向量空间中的一种度量，二个点之间的距离定义为其各坐标数值差的最大值。

二维中表示为：max(|x1-x2|,|y1-y2|)

如果将曼哈顿距离转换成切比雪夫距离

那么圆形的辐射范围变成了一个矩形，可以用O(n²)扫描线，扫描圆形辐射范围

Floyd 算法（多源最短路径）
1
2
3
4
5
6
7
void floyd(vector<vector<int>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

最小生成树

左程云061

https://www.bilibili.com/video/BV1sK4y1F7LH?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

包含Kruskal prim及其优化

数学知识

筛法 - OI Wiki

素数筛

思路 ：对于任意一个大于1 的正整数 ，那么它的 x倍就是合数（x>1）。利用这个结论，我们可以避免很多次不必要的检测。

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。

这种 线性筛法 也称为 Euler 筛法（欧拉筛法）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> pri;
bool not_prime[N];

void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      pri.push_back(i);
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        // i % pri_j == 0
        // 换言之，i 之前被 pri_j 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
        // pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

欧拉函数（φ(n)）

计算小于等于 n 且与 n 互质的数的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> pri;
bool not_prime[N];
int phi[N];
void pre(int n) {
  phi[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!not_prime[i]) {
      pri.push_back(i);
      phi[i] = i - 1;
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        phi[i * pri_j] = phi[i] * pri_j;
        break;
      }
      phi[i * pri_j] = phi[i] * phi[pri_j];
    }
  }
}

快速幂

左程云098

https://www.bilibili.com/video/BV13k4y1D7Dn?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

计算 a*b mod m

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

矩阵快速幂

返回mat^power % mod

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> matrix_pow(vector<vector<int>> mat, int power, int mod) {
int n = mat.size();

// 初始化单位矩阵

vector<vector<int>> res(n, vector<int>(n, 0));

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

while (power > 0) {

    if (power % 2 == 1) res = multiply(res, mat, mod);

    mat = multiply(mat, mat, mod);

    power /= 2;

}
return res;
}

最大公约数（GCD）

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

最小公倍数（LCM）

1
2
3
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

动态规划

左程云066——088

https://www.bilibili.com/video/BV1Ww41167Ac?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

一只会code的小金鱼

https://www.bilibili.com/video/BV1r84y1379W?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

给定一个问题，拆分为一个个子问题，直到子问题得到解决。保存子问题答案以减少重复计算。(记忆化搜索)再根据子问题答案反推，得到原问题解。

动态规划是递推的子集？

例题:跳台阶 一个楼梯n级台阶，每次走一或两级，问从0到n有多少种方案。

记忆化搜索(dfs+记录答案)想实现记忆化搜索，dfs的参数应该尽可能少，不应该传入不影响边界的参数。

剪枝则应该尽可能把能剪枝的参数传入保留

递归 递分解问题 自顶向下，归得到答案 自底向上。只进行归可不可以？从下逐层往上推

递推公式(dfs向下递归公式)

线性dp 例洛谷u224502

阿福是经验丰富大盗，要洗劫有N家店铺的一条街，每家店有现金。

已知同时洗劫相邻店铺报警系统会启动，阿福不想被抓，给定T组数据，每组数据先给店铺数N，再给N家店铺现金数，求每组数据下 阿福在不惊动警察时最多能得的现金数。

贪心算法

左程云089——094

https://www.bilibili.com/video/BV1be41167yw?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

湖北工业大学ACM集训队 2025寒假培训第四讲——贪心初步

https://www.bilibili.com/video/BV1KGcBeVEyW?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

活动安排问题

选择最多的不重叠活动。

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxActivities(vector<vector<int>>& activities) {
    sort(activities.begin(), activities.end(), [](auto& a, auto& b) {
        return a[1] < b[1];
    });
    int count = 1, lastEnd = activities[0][1];
    for (int i = 1; i < activities.size(); ++i) {
        if (activities[i][0] >= lastEnd) {
            count++;
            lastEnd = activities[i][1];
        }
    }
    return count;
}

哈夫曼编码（最小带权路径长度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Node {
    int freq;
    Node *left, *right;
    Node(int f) : freq(f), left(nullptr), right(nullptr) {}
};
struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};
int huffman(vector<int>& freq) {
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (int f : freq)
        pq.push(new Node(f));
    while (pq.size() > 1) {
        Node* a = pq.top(); pq.pop();
        Node* b = pq.top(); pq.pop();
        Node* parent = new Node(a->freq + b->freq);
        parent->left = a;
        parent->right = b;
        pq.push(parent);
    }
    return pq.top()->freq;
}

博弈类问题

左程云095

https://www.bilibili.com/video/BV1T5411i7Gg?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

简单博弈类问题情境下，每个局面仅存在两种可能：先手必胜（后手必败）和先手必败（后手必胜）状态

简称为 必胜态 必败态

巴什博弈（Bash Game）

简述：两人轮流从一堆物品中取物，每次至少取 1 个，最多取m个，取走最后一个物品者胜。

结论：若物品总数n能被m+1整除，则后手必胜；否则先手必胜。 （核心：先手可通过取n mod (m+1)个物品，使剩余数量为m+1的倍数，后续镜像后手操作即可获胜。）

尼姆博弈（Nim Game）

简述：两人轮流从多堆物品中选一堆，取走任意数量（至少 1 个），取走最后一个物品者胜。

结论：计算所有堆物品数量的异或和（XOR）。若异或和为 0，则后手必胜；否则先手必胜。 （核心：先手可通过操作使各堆数量异或和为 0，后续镜像后手操作即可获胜。）

斐波那契博弈（Fibonacci Game）

简述：一堆物品共n个，两人轮流取物，先手首次取 1 到n-1个，之后每次取物数量不超过对手上一次取物数量的 2 倍，取走最后一个物品者胜。

结论：若n是斐波那契数，则后手必胜；否则先手必胜。 （核心：斐波那契数构成必败态，非斐波那契数可分解为两个不连续的斐波那契数，先手通过取走较小数打破平衡。）

威佐夫博弈（Wythoff Game）

简述：两人轮流从两堆物品中取物，可从一堆取任意数量，或从两堆取相同数量，取走最后一个物品者胜。

结论：设两堆数量为(a, b)（a ≤ b），计算k = b - a。若a = ⌊k * (√5 + 1)/2⌋

（黄金分割数≈1.618），则后手必胜；否则先手必胜。

公平组合游戏 - OI Wiki

图游戏概念：每个博弈局面对应图中一个点，行动对应点到后继点的边，必败局面视为无后继节点的点

公平组合游戏（ICG）

  • 可抽象为有向无环图，符合图游戏规则

SG 函数

左程云096

https://www.bilibili.com/video/BV1N94y1T7Mb?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

  1. 定义

    通过 mex（最小非负未出现整数）计算

    必败点 SG 值 = 0

    非必败点 SG 值 = 所有后继节点 SG 值的 mex

  2. 判定

    SG≠0 → 必胜态

    SG=0 → 必败态

SG 定理（Bouton 定理）

总游戏 SG 值 = 各独立子游戏 SG 值的异或和，适用所有 ICG 游戏。

算法学习笔记

前言

此笔记大致按照AcWing - 算法基础课顺序整理，各算法中的链接绝大部分为我真实在b站学完的网课，还包含部分CSDN和OI维基百科中的内容，希望对你有所帮助。

排序算法

https://blog.csdn.net/2301_80215560/article/details/136604635?sharetype=blog&shareId=136604635&sharerefer=APP&sharesource=2401_87034440&sharefrom=link

左程云 https://b23.tv/biO1uQB

https://github.com/algorithmzuo/algorithm-journey

004 021 023 025 028 029

冒泡排序

相邻两个元素的值进行两两比较，若发现前一个数大于后一个数则交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void BubbleSort(int* a, int n)
{
	int end = n - 1;//不能是n，不然会越界
	while(end)
	{
		bool exchange = false;//优化，比较之后没有交换，说明已经排好了，就break循环
		for (int i = 0; i < end; i++)
		{
			if (a[i] < a[i + 1])
			{
				swap(&a[i], &a[i + 1]);//交换
				exchange++;
			}
		}
		if (exchange == false) break;
		end--;
	}
}

归并排序

左程云021、022 https://b23.tv/biO1uQB

拆分原数组，分别排序，再 merge 归并。归并排序是一种稳定的排序算法，时间复杂度为 O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge(vector<int>& nums, int l, int m, int r) {
    vector<int> L(m - l + 1), R(r - m);
    for (int i = 0; i < L.size(); ++i) L[i] = nums[l + i];
    for (int j = 0; j < R.size(); ++j) R[j] = nums[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < L.size() && j < R.size())
        nums[k++] = L[i] <= R[j] ? L[i++] : R[j++];
    while (i < L.size()) nums[k++] = L[i++];
    while (j < R.size()) nums[k++] = R[j++];
}
void mergeSort(vector<int>& nums, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(nums, l, m);
        mergeSort(nums, m + 1, r);
        merge(nums, l, m, r);
    }
}

桶排序、基数排序、计数排序

左程云028

这三种排序算法都不基于比较，对数据特征有要求。计数排序适用于已知数值范围的场景；基数排序通常要求处理十进制非负整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
思路：大问题化小
桶排序(Bucket sort)或所谓的箱排序，是一种分块的排序算法，工作的原理是将数组分到有限数量的桶里，
每个桶的大小都相等。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
把待排序序列（数组）中的数据根据函数映射方法分配到若干个桶中，
在分别对各个桶进行排序，最后依次按顺序取出桶中的数据。
适用于数据分配均匀，数据比较大，相对集中的情况。
void bucketSort(vector<double>& arr) {
    int n = arr.size();
    vector<vector<double>> buckets(n);
    for (double num : arr) {
        int idx = n * num;
        buckets[idx].push_back(num);
    }
    for (auto& bucket : buckets) sort(bucket.begin(), bucket.end());
    int idx = 0;
    for (auto& bucket : buckets)
        for (double num : bucket) arr[idx++] = num;
}
1
2
3
4
5
//计数排序 一种特殊的排序，没有比较
例（仅有0-10）
0 1 2 3 4 5 6 7 8 9 10
以数组的下标当做数值，有这个数的时候a[i]++; 
局限：适用于整数。数要求集中（否则空间的浪费大）

基数排序(一般要求为十进制非负整数)

左程云028

https://www.bilibili.com/video/BV1Lh4y1c7Aw?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

判断最大的位数是几位，对每一位进行桶排序。

从个位开始，数组按个位数字大小入桶，然后从0-9倒出，此后十位百位同上循环，最终结果即有序。从低位开始作用为保留低位大小关系。

技巧1 前缀分区做桶排列

统计每个数字出现次数后做前缀和得到数组(x)，则从右向左遍历原数组时，该数字在保留相对次序情况下应该出现在x数组对应的数字-1的位置，做完此操作后x数组对应数字–。

故该技巧可以用于基数排序时对每一位数字进行排序任务。

技巧2 怎么得到每一位

用一个变量offset初始化为1，所求数字n。(n/offset)%10该位数操作玩后offset*=10依次得到每一位数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
最终code
    // 理解的时候可以假设BASE = 10
		for (int offset = 1; bits > 0; offset *= BASE, bits--) {
			Arrays.fill(cnts, 0);
			for (int i = 0; i < n; i++) {
				// 数字提取某一位的技巧
				cnts[(arr[i] / offset) % BASE]++;
			}
			for (int i = 1; i < BASE; i++) {
				cnts[i] = cnts[i] + cnts[i - 1];
			}
			for (int i = n - 1; i >= 0; i--) {
				// 前缀数量分区的技巧
				// 数字提取某一位的技巧
				help[--cnts[(arr[i] / offset) % BASE]] = arr[i];
			}
			for (int i = 0; i < n; i++) {
				arr[i] = help[i];
			}
		}

二分

二分查找

左程云006 https://b23.tv/biO1uQB

l、r 为区间左右端点，比较值为 target t（寻找 t）。需保证数组有序，若 ＞（m 为区间中点），则向右二分；若 ＜，则向左二分。当 l≥r 时结束，时间复杂度 O(logn)。

1
2
3
4
5
6
7
8
9
10
int binarySearch(const vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (nums[m] == target) return m;
        else if (nums[m] < target) l = m + 1;
        else r = m - 1;
    }
    return -1;
}

二分答案

左程云051 https://b23.tv/biO1uQB

一只会code的小金鱼 https://b23.tv/vFaRbc9

写函数f，f函数作用为得到一个过程的答案，二分从最极限的最大可能到最小可能答案。我们则可以同f判断能否达到题目的需求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool f(int x, int n, const vector<int>& a, const vector<int>& b) {
    int sum = 0;
    for (int i = 0; i < a.size(); ++i) sum += x / b[i] * a[i];
    return sum >= n;
}
int binaryAnswer(int n, const vector<int>& a, const vector<int>& b) {
    int l = 0, r = 1e9, ans = -1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (f(m, n, a, b)) { ans = m; r = m - 1; }
        else l = m + 1;
    }
    return ans;
}
例

n台打印机，每台打印机的效率分别是a张b秒。

问打印到第n张纸是多少秒

设打印第n张纸x秒

f函数可以求出x秒时具体可以打印多少张纸

x/b*a和n张比，够了记答案往左二分，不够则不记答案往右二分，最大给1e9

高精度

（用数组模拟 列竖式计算）

麦克老师讲算法 高精度算法全套 https://b23.tv/sArWoTg

高精度计算 - OI Wiki

高精度加法

处理两个大整数相加，用数组存储每一位，模拟进位操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
string add(string num1, string num2) {
    string res;
    int carry = 0, i = num1.size() - 1, j = num2.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += num1[i--] - '0';
        if (j >= 0) sum += num2[j--] - '0';
        res.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

高精度减法

处理两个大整数相减，用数组存储每一位，模拟借位操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string subtract(string num1, string num2) {
    if (num1 < num2) return "-" + subtract(num2, num1);
    string res;
    int borrow = 0, i = num1.size() - 1, j = num2.size() - 1;
    while (i >= 0) {
        int diff = (num1[i] - '0') - borrow;
        if (j >= 0) diff -= (num2[j] - '0');
        if (diff < 0) { diff += 10; borrow = 1; }
        else borrow = 0;
        res.push_back(diff + '0');
        i--; j--;
    }
    // 移除前导零
    while (res.size() > 1 && res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

前缀和与差分

https://blog.csdn.net/weixin_45629285/article/details/111146240?sharetype=blog&shareId=111146240&sharerefer=APP&sharesource=2401_87034440&sharefrom=link

前缀和 & 差分 - OI Wiki

一维前缀和

作用，可以快速求出区间l 到 r之间数之和。

只需要执行 sum[r] - sum[l - 1]。输出原序列中从第l个数到第r个数的和的时间复杂度变成了O(1)。

1
2
3
4
5
6
7
8
9
10
11
vector<int> prefixSum(const vector<int>& nums) {
    int n = nums.size();
    vector<int> sum(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + nums[i - 1];
    return sum;
}
// 查询区间[l,r]的和
int query(const vector<int>& sum, int l, int r) {
    return sum[r + 1] - sum[l];
}

二维前缀和

二维前缀和预处理公式

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

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

1
2
3
4
5
6
7
8
9
10
11
12
vector<vector<int>> prefixSum2D(const vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> s(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + matrix[i - 1][j - 1];
    return s;
}
// 查询子矩阵(x1,y1)-(x2,y2)的和
int query2D(const vector<vector<int>>& s, int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

一维差分

结论：给a数组中的[ l, r] 区间中的每一个数都加上c,

只需对差分数组b做 b[l] + = c, b[r+1] - = c 。

构造差分数组，差分为前缀和的逆运算。可以做到快速为数组中的每个值进行加减运算。

二维差分

(思路同一维)

构造方法，结论：

1
b[i][j] = a[i][j] − a[i − 1][j] − a[i][j − 1] + a[i − 1 ][j − 1]

双指针算法

左程云050 https://b23.tv/biO1uQB

1有的双指针知识单纯用到两个指针

2有的则包含单调性（贪心）方面的思考与分析

常见类型：1）同向双指针 2）快慢双指针 3）从两端向中间的双指针

位运算

左程云003 031 033 https://b23.tv/biO1uQB

直接操作二进制位，用于高效计算。

1
2
3
4
5
6
7
8
9
10
bool isOdd(int n) { return n & 1; } // 判断奇偶
int lowbit(int n) { return n & -n; } // 获取最低位1
int countOnes(int n) { // 计算二进制中1的个数
    int cnt = 0;
    while (n) {
        n &= n - 1; // 清除最低位1
        cnt++;
    }
    return cnt;
}

位图

左程云032 https://b23.tv/biO1uQB

用bit组成数组存放值，用bit01代表存在与否，取存用位运算。

限制 必须连续范围，不能过大。

优点 极大的节省空间

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
class Bitset {
private:
    vector<int> set;
public:
    Bitset(int n) {
        set.resize((n + 31) / 32, 0);
    }
    void add(int num) {
        int index = num / 32;
        int bitPos = num % 32;
        set[index] |= (1 << bitPos);
    }
    void remove(int num) {
        int index = num / 32;
        int bitPos = num % 32;
        set[index] &= ~(1 << bitPos);
    }
    void reverse(int num) {
        int index = num / 32;
        int bitPos = num % 32;
        set[index] ^= (1 << bitPos);
    }
    bool contains(int num) {
        int index = num / 32;
        int bitPos = num % 32;
        return ((set[index] >> bitPos) & 1) == 1;
    }
};

离散化

左程云048

【算法讲解048【必备】二维前缀和、二维差分、离散化技巧】

https://www.bilibili.com/video/BV1Wz4y1K74C?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

将无限或大范围的数值映射到有限、连续的整数区间，保留相对大小关系，用于优化数据范围过大的问题（如坐标压缩、频率统计）。

1
2
3
4
5
6
7
8
9
10
11
12
// 离散化单个值x（tmp为排序去重后的数组）
int idx = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
lower_bound 返回第一个≥当前值的位置，保证相同值映射到同一下标
    
vector<int> discretize(vector<int>& nums) {
    vector<int> tmp = nums;
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    for (auto& x : nums)
        x = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
    return nums;
}

区间合并

合并重叠区间，先按左端点排序，再遍历合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);
    for (auto& interval : intervals) {
        if (interval[0] <= merged.back()[1])
            merged.back()[1] = max(merged.back()[1], interval[1]);
        else
            merged.push_back(interval);
    }
    return merged;
}

数据结构

【【强烈推荐】深入浅出数据结构 - 顶尖程序员图文讲解 - UP主翻译校对 (已完结)】

https://www.bilibili.com/video/BV1Fv4y1f7T1?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

邻接矩阵

存储特点：

使用二维数组 g[i][j] 表示顶点 i 到 j 的连接关系

无向图的矩阵是对称的，有向图可能不对称

矩阵中 1 表示有边，0 或 ∞ 表示无边（带权图存储权重值）

优点：

  1. 实现简单，支持快速查询任意两顶点间是否有边（O (1)）
  2. 便于计算每个顶点的度（行 / 列和）
  3. 适合稠密图（边数接近顶点数平方）

缺点：

  1. 空间复杂度高（O (V²)），存储稀疏图时浪费大量空间（V：顶点vertex E：边edge）
  2. 添加 / 删除顶点需重新调整矩阵大小，效率低
  3. 统计边的总数需要遍历整个矩阵（O (V²)）

链表与邻接表

优点：

  1. 空间效率高（O (V+E)），适合稀疏图（边数远小于顶点数平方）
  2. 便于添加 / 删除顶点和边
  3. 遍历所有边的时间复杂度为 O (E)

缺点：

  1. 判断两顶点间是否有边效率较低（O (degree (v))）
  2. 计算顶点的度需遍历对应链表（O (degree (v))）
  3. 不适合频繁查询任意两顶点间的关系

栈与队列

最小栈（O (1) 获取最小值）

左程云015

https://www.bilibili.com/video/BV15X4y177cM?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

维护一个最小栈minval包含getmin功能 若入栈元素x小于等于最小栈的栈顶则x入最小栈

minVal.empty() || x <= minVal.top()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MinStack {
    stack<int> data, minVal;
public:
    void push(int x) {
        data.push(x);
        if (minVal.empty() || x <= minVal.top())
            minVal.push(x);
    }
    void pop() {
        if (data.top() == minVal.top())
            minVal.pop();
        data.pop();
    }
    int getMin() { return minVal.top(); }
};
单调栈（下一个更大元素）

实现原理：以单调递增栈为例，当新元素入栈时，会将栈中所有比它大的元素弹出，直到栈为空或者栈顶元素小于等于新元素，然后将新元素入栈。单调递减栈则相反。

遍历每个元素时，将当前元素与栈顶元素比较：

若当前元素小于等于栈顶元素 → 直接入栈，保持栈的递增性

若当前元素大于栈顶元素 → 触发以下操作：

  1. 弹出栈顶元素，并记录当前元素为其「下一个更大值」
  2. 持续弹出新的栈顶元素，直到当前元素 ≤ 栈顶
  3. 当前元素入栈，恢复栈的递增顺序

这个过程中，每个元素被弹出时，其「下一个更大值」即为触发弹出的当前元素。遍历结束后，栈内剩余元素的「下一个更大值」均为默认值（如 - 1 或无穷大）。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            res[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}
单调队列（滑动窗口最大值）

实现原理：通常用双端队列来实现。以单调递增队列为例，当新元素要入队时，从队尾开始比较，如果队尾元素大于新元素，则将队尾元素出队，直到队尾元素小于等于新元素或者队列为空，然后将新元素从队尾入队。在进行出队操作时，如果队首元素超出了当前考虑的范围，则将队首元素出队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> dq;
    for (int i = 0; i < nums.size(); ++i) {
        // 移除队尾较小元素
        while (!dq.empty() && nums[i] >= nums[dq.back()])
            dq.pop_back();
        dq.push_back(i);
        // 移除窗口外元素
        if (dq.front() <= i - k)
            dq.pop_front();
        if (i >= k - 1)
            res.push_back(nums[dq.front()]);
    }
    return res;
}

KMP 算法以及find()字符串匹配

左程云100 、101 https://b23.tv/biO1uQB

核心思想：利用已经匹配过的部分信息，避免不必要的字符比较，从而提高匹配效率。

通过预处理模式串的 next 数组，记录模式串中每个位置之前最长的相同前缀和后缀长度。

Next 数组含义： next[i] 表示模式串 pattern[0..i] 的最长公共前后缀长度。 例如：pattern = "ababc"，其 next 数组为 [0, 0, 1, 2, 0]。

匹配过程优化： 当主串 S[i] 与模式串 P[j] 不匹配时，直接将 j 回退到 next[j-1]，而主串指针 i 不回退。

总结：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
53
54
55
56
57
58
59
60
61
int main() {
    string str = "hello world, world!";
    string substr = "world";
    string charset = "aeiou";
    string digits = "0123456789";
    // 1. 基本查找：find() 和 rfind()
    size_t pos1 = str.find(substr);            // 正向查找子串，返回6
    size_t pos2 = str.find(substr, 7);         // 从位置7开始查找，返回13
    size_t pos3 = str.rfind(substr);           // 反向查找子串，返回13
    size_t pos4 = str.find('o');               // 查找字符，返回4
    size_t pos5 = str.find('o', 5);            // 从位置5开始查找字符，返回7

    // 2. 查找任意字符：find_first_of() 和 find_last_of()
    size_t pos6 = str.find_first_of(charset);  // 查找首个元音字母，返回1('e')
    size_t pos7 = str.find_last_of(charset);   // 查找最后一个元音字母，返回11('o')

    // 3. 查找非指定字符：find_first_not_of() 和 find_last_not_of()
    string spaces = "   abc   ";
    size_t pos8 = spaces.find_first_not_of(' '); // 查找首个非空格字符，返回3('a')
    size_t pos9 = spaces.find_last_not_of(' ');  // 查找最后一个非空格字符，返回5('c')

    // 4. 遍历所有匹配位置
    cout << "所有 'world' 的位置：";
    size_t currentPos = 0;
    while ((currentPos = str.find(substr, currentPos)) != string::npos) {
        cout << currentPos << " ";
        currentPos += substr.length(); // 跳过已匹配的部分
    }
    cout << endl; // 输出: 6 13

    // 5. 检查字符串是否包含子串
    bool hasWorld = (str.find(substr) != string::npos); // true

    // 6. 处理未找到的情况
    size_t notFound = str.find("xyz");
    if (notFound == string::npos) {
        cout << "'xyz' 未找到" << endl;
    }

    // 7. 特殊情况：空字符串查找
    size_t emptyPos = str.find(""); // 始终返回0（空字符串被视为存在于字符串开头）

    // 8. 查找首个非数字字符
    string numStr = "123.45";
    size_t dotPos = numStr.find_first_not_of(digits); // 返回3('.')

    // 输出所有结果
    cout << "pos1: " << pos1 << endl; // 6
    cout << "pos2: " << pos2 << endl; // 13
    cout << "pos3: " << pos3 << endl; // 13
    cout << "pos4: " << pos4 << endl; // 4
    cout << "pos5: " << pos5 << endl; // 7
    cout << "pos6: " << pos6 << endl; // 1
    cout << "pos7: " << pos7 << endl; // 11
    cout << "pos8: " << pos8 << endl; // 3
    cout << "pos9: " << pos9 << endl; // 5
    cout << "hasWorld: " << (hasWorld ? "true" : "false") << endl; // true
    cout << "dotPos: " << dotPos << endl; // 3

    return 0;
}

Trie 树（字典树）

左程云044 045 https://b23.tv/biO1uQB

Trie 树通过共享字符串前缀存储多组单词，使查询效率仅取决于字符串长度，适合高频前缀匹配场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct TrieNode {
    vector<TrieNode*> children;  // 子节点数组（假设仅包含小写字母）
    bool isEndOfWord;            // 标记是否为单词结尾
    
    TrieNode() : children(26, nullptr), isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() { root = new TrieNode(); }
    
    // 插入字符串
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEndOfWord = true;  // 标记单词结尾
    }
    
    // 查找字符串
    bool search(string word) {
        TrieNode* node = searchPrefix(word);
        return node != nullptr && node->isEndOfWord;
    }
    
    // 查找前缀
    bool startsWith(string prefix) {
        return searchPrefix(prefix) != nullptr;
    }

private:
    // 辅助函数：查找前缀路径
    TrieNode* searchPrefix(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return nullptr;
            node = node->children[idx];
        }
        return node;
    }
};

并查集（合并查询集合）

蓝不过海呀

https://www.bilibili.com/video/BV1zZRSYUEWV?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

麦克老师讲算法

https://www.bilibili.com/video/BV1jv411a7LK?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

合并 查询 集合

用数组 保存每个节点的父亲

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 p[MAXN];
void Initial(int n){
    for(int i=0; i<n; i++) {
        p[i]=-1;
    }
}
void Union(int x,int y){
    int rootx = Find(x);
    int rooty = Find(y);
    if(rootx!=rooty){//按大小合并
        if(p[rootx]<p[rooty]){
            p[rooty]=rootx;
        } else if(p[rootx]>p[rooty]){
            p[rootx]=rooty;
        } else {
            p[rootx]=rooty;
            p[rooty]--;
        }
    }
    if(rootx!=rooty){//按照高度合并
        if(p[rootx]<p[rooty]){
            p[rootx]+=p[rooty];
            p[rooty]=rootx;
        }else{
            p[rooty]+=p[rootx];
            p[rootx]=rooty;
        }
    }
}
int Find(int x){
    if(p[x]<0)
        return x;
    else
        return Find(p[x]);
}

堆（优先队列）

高效维护和获取极值（最大值或最小值），并支持快速插入、删除操作。一般使用stl库中函数

1
2
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

Hash 表（两数之和）

左程云026 https://b23.tv/biO1uQB

作用为快速查找 / 统计

https://www.bilibili.com/video/BV13m4y1p7VB?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

只用存元素 unordered_set 需要存元素 + 额外信息 unordered_map

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
unordered_map<int, int> mp;
/*去重 / 判重	unordered_set	自动去重，仅需检查元素存在性（如判断数组是否有重复元素）。
统计频率 / 映射关系	unordered_map	需要存储键值对（如统计字符出现次数、记录节点距离）。
缓存中间结果	unordered_map	需要同时存储输入和计算结果（如记忆化搜索）。
快速查找补数 / 配对	unordered_map	需要键值对关联（如两数之和问题，需快速查找目标值的补数）。*/
struct Point { int x, y; };
struct PH { size_t operator()(const Point& p) const {
    return p.x ^ p.y; // 简化哈希函数
}};

int main() {
    // 基础用法
    unordered_set<int> s = {1,2,3};
    s.insert(4);        // 插入
    s.erase(2);         // 删除
    bool exists = s.count(3); // 存在检查
    auto it = s.find(1); // 迭代器查找

    // 自定义类型
    unordered_set<Point, PH> points;
    points.insert({1,2});

    // 遍历
    for (auto& e : s) { /* 使用e */ }
}

搜索与图论

DFS 与 BFS

DFS（深度优先搜索）

一只会code的小金鱼 https://b23.tv/vFaRbc9

排列，指数级 深入探索分支至无法继续，然后回溯后探索其他分支。核心在于递归

DFS适合此类题目：给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。

1
2
3
4
5
6
void dfs(vector<vector<int>>& adj, int u, vector<bool>& visited) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v])
            dfs(adj, v, visited);
}
BFS（广度优先搜索）

**左程云062 ** https://b23.tv/biO1uQB

一只会code的小金鱼 https://b23.tv/vFaRbc9

队列，逐层扩散，扩散几层最短路就是多少，可以单点弹出，整层弹出。标记状态数组，剪枝。

使用要求：任意两相邻节点距离等同(边权相同)。

二段性：一边全符合，另一边全不符合，且队列内最多两种状态。x和x+1。

bfs队列具有的性质：单调性 单调增减

多源bfs

提前把源头存入队列(有个虚拟的源点连接多个边权为0的点(多个源头))。

01bfs

双端队列 队头入队or队尾入队

双向bfs

左程云063

维护两个队列，需要知道起点和终点位置，从起点和终点同时开始bfs，维护状态数组记录两个bfs到的状态，若碰上则证明可以从起点到终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> bfs(vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

拓扑排序（有向无环图）

拓扑排序是对 ** 有向无环图（DAG）** 的顶点进行排序的算法，使得对于每条有向边 (u→v)，顶点 u 在排序中均出现在 v 之前，常用 Kahn 算法（入度队列）或 DFS 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> topologicalSort(vector<vector<int>>& adj, int n) {
    vector<int> inDegree(n, 0);
    for (auto& edges : adj)
        for (int v : edges)
            inDegree[v]++;
    queue<int> q;
    for (int i = 0; i < n; ++i)
        if (inDegree[i] == 0)
            q.push(i);
    vector<int> res;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res.push_back(u);
        for (int v : adj[u])
            if (--inDegree[v] == 0)
                q.push(v);
    }
    return res.size() == n ? res : vector<int>();
}

最短路

左程云064

https://www.bilibili.com/video/BV1Cm4y1g77W?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

Dijkstra 算法（单源最短路径）
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
typedef pair<int, int> PII; // {距离, 节点编号}
// 输入：邻接表graph，源点src，输出：源点到各点的最短距离数组dist
vector<int> dijkstra(vector<vector<PII>>& graph, int src) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX); // 初始化距离为无穷大
    dist[src] = 0; // 源点到自身距离为0
    // 最小堆（优先队列）
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, src}); // {距离, 节点}
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        
        // 跳过已处理的节点（避免重复计算）
        if (d > dist[u]) continue;
        
        // 遍历所有邻接边
        for (auto [v, w] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}
int main() {
    int n = 5; // 节点数
    vector<vector<PII>> graph(n); // 邻接表
    // 添加边 (u->v 权重为w)
    graph[0].push_back({1, 2}); // 0->1 权重2
    graph[0].push_back({2, 4}); // 0->2 权重4
    graph[1].push_back({2, 1}); // 1->2 权重1
    graph[1].push_back({3, 7}); // 1->3 权重7
    graph[2].push_back({3, 3}); // 2->3 权重3
    graph[3].push_back({4, 2}); // 3->4 权重2
    vector<int> dist = dijkstra(graph, 0);
    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << "从节点0到节点" << i << "的最短距离是: ";
        if (dist[i] == INT_MAX) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
    
    return 0;
}
a*算法

左程云065

https://www.bilibili.com/video/BV1t94y187zW?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

问从特定点到特定点的最短距离

与dijkstra算法distance数组相同，区别在小根堆的使用时加一个曼哈顿距离(估计一个长度，影响小根堆弹出顺序，致使运行时间缩短)

距离

距离 - OI Wiki

欧氏距离，一般也称作欧几里得距离，空间两点间的欧氏距离为：根号下a方+b方+c方

缺点：两个整点计算其欧氏距离时，往往答案是浮点型，会存在一定误差。

曼哈顿距离（Manhattan distance）

为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。可以表示为：|x1-x2|+|y1-y2|

[P5098 USACO04OPEN] Cave Cows 3 - 洛谷

切比雪夫距离

是向量空间中的一种度量，二个点之间的距离定义为其各坐标数值差的最大值。

二维中表示为：max(|x1-x2|,|y1-y2|)

如果将曼哈顿距离转换成切比雪夫距离

那么圆形的辐射范围变成了一个矩形，可以用O(n²)扫描线，扫描圆形辐射范围

Floyd 算法（多源最短路径）
1
2
3
4
5
6
7
void floyd(vector<vector<int>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

最小生成树

左程云061

https://www.bilibili.com/video/BV1sK4y1F7LH?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

包含Kruskal prim及其优化

数学知识

筛法 - OI Wiki

素数筛

思路 ：对于任意一个大于1 的正整数 ，那么它的 x倍就是合数（x>1）。利用这个结论，我们可以避免很多次不必要的检测。

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。

这种 线性筛法 也称为 Euler 筛法（欧拉筛法）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> pri;
bool not_prime[N];

void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      pri.push_back(i);
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        // i % pri_j == 0
        // 换言之，i 之前被 pri_j 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
        // pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

欧拉函数（φ(n)）

计算小于等于 n 且与 n 互质的数的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> pri;
bool not_prime[N];
int phi[N];
void pre(int n) {
  phi[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!not_prime[i]) {
      pri.push_back(i);
      phi[i] = i - 1;
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        phi[i * pri_j] = phi[i] * pri_j;
        break;
      }
      phi[i * pri_j] = phi[i] * phi[pri_j];
    }
  }
}

快速幂

左程云098

https://www.bilibili.com/video/BV13k4y1D7Dn?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

计算 a*b mod m

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

矩阵快速幂

返回mat^power % mod

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> matrix_pow(vector<vector<int>> mat, int power, int mod) {
int n = mat.size();

// 初始化单位矩阵

vector<vector<int>> res(n, vector<int>(n, 0));

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

while (power > 0) {

    if (power % 2 == 1) res = multiply(res, mat, mod);

    mat = multiply(mat, mat, mod);

    power /= 2;

}
return res;
}

最大公约数（GCD）

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

最小公倍数（LCM）

1
2
3
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

动态规划

左程云066——088

https://www.bilibili.com/video/BV1Ww41167Ac?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

一只会code的小金鱼

https://www.bilibili.com/video/BV1r84y1379W?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

给定一个问题，拆分为一个个子问题，直到子问题得到解决。保存子问题答案以减少重复计算。(记忆化搜索)再根据子问题答案反推，得到原问题解。

动态规划是递推的子集？

例题:跳台阶 一个楼梯n级台阶，每次走一或两级，问从0到n有多少种方案。

记忆化搜索(dfs+记录答案)想实现记忆化搜索，dfs的参数应该尽可能少，不应该传入不影响边界的参数。

剪枝则应该尽可能把能剪枝的参数传入保留

递归 递分解问题 自顶向下，归得到答案 自底向上。只进行归可不可以？从下逐层往上推

递推公式(dfs向下递归公式)

线性dp 例洛谷u224502

阿福是经验丰富大盗，要洗劫有N家店铺的一条街，每家店有现金。

已知同时洗劫相邻店铺报警系统会启动，阿福不想被抓，给定T组数据，每组数据先给店铺数N，再给N家店铺现金数，求每组数据下 阿福在不惊动警察时最多能得的现金数。

贪心算法

左程云089——094

https://www.bilibili.com/video/BV1be41167yw?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

湖北工业大学ACM集训队 2025寒假培训第四讲——贪心初步

https://www.bilibili.com/video/BV1KGcBeVEyW?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

活动安排问题

选择最多的不重叠活动。

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxActivities(vector<vector<int>>& activities) {
    sort(activities.begin(), activities.end(), [](auto& a, auto& b) {
        return a[1] < b[1];
    });
    int count = 1, lastEnd = activities[0][1];
    for (int i = 1; i < activities.size(); ++i) {
        if (activities[i][0] >= lastEnd) {
            count++;
            lastEnd = activities[i][1];
        }
    }
    return count;
}

哈夫曼编码（最小带权路径长度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Node {
    int freq;
    Node *left, *right;
    Node(int f) : freq(f), left(nullptr), right(nullptr) {}
};
struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};
int huffman(vector<int>& freq) {
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (int f : freq)
        pq.push(new Node(f));
    while (pq.size() > 1) {
        Node* a = pq.top(); pq.pop();
        Node* b = pq.top(); pq.pop();
        Node* parent = new Node(a->freq + b->freq);
        parent->left = a;
        parent->right = b;
        pq.push(parent);
    }
    return pq.top()->freq;
}

博弈类问题

左程云095

https://www.bilibili.com/video/BV1T5411i7Gg?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

简单博弈类问题情境下，每个局面仅存在两种可能：先手必胜（后手必败）和先手必败（后手必胜）状态

简称为 必胜态 必败态

巴什博弈（Bash Game）

简述：两人轮流从一堆物品中取物，每次至少取 1 个，最多取m个，取走最后一个物品者胜。

结论：若物品总数n能被m+1整除，则后手必胜；否则先手必胜。 （核心：先手可通过取n mod (m+1)个物品，使剩余数量为m+1的倍数，后续镜像后手操作即可获胜。）

尼姆博弈（Nim Game）

简述：两人轮流从多堆物品中选一堆，取走任意数量（至少 1 个），取走最后一个物品者胜。

结论：计算所有堆物品数量的异或和（XOR）。若异或和为 0，则后手必胜；否则先手必胜。 （核心：先手可通过操作使各堆数量异或和为 0，后续镜像后手操作即可获胜。）

斐波那契博弈（Fibonacci Game）

简述：一堆物品共n个，两人轮流取物，先手首次取 1 到n-1个，之后每次取物数量不超过对手上一次取物数量的 2 倍，取走最后一个物品者胜。

结论：若n是斐波那契数，则后手必胜；否则先手必胜。 （核心：斐波那契数构成必败态，非斐波那契数可分解为两个不连续的斐波那契数，先手通过取走较小数打破平衡。）

威佐夫博弈（Wythoff Game）

简述：两人轮流从两堆物品中取物，可从一堆取任意数量，或从两堆取相同数量，取走最后一个物品者胜。

结论：设两堆数量为(a, b)（a ≤ b），计算k = b - a。若a = ⌊k * (√5 + 1)/2⌋

（黄金分割数≈1.618），则后手必胜；否则先手必胜。

公平组合游戏 - OI Wiki

图游戏概念：每个博弈局面对应图中一个点，行动对应点到后继点的边，必败局面视为无后继节点的点

公平组合游戏（ICG）

  • 可抽象为有向无环图，符合图游戏规则

SG 函数

左程云096

https://www.bilibili.com/video/BV1N94y1T7Mb?vd_source=89ee9c0333eed94fc15ad7bfeda6fb8c

  1. 定义

    通过 mex（最小非负未出现整数）计算

    必败点 SG 值 = 0

    非必败点 SG 值 = 所有后继节点 SG 值的 mex

  2. 判定

    SG≠0 → 必胜态

    SG=0 → 必败态

SG 定理（Bouton 定理）

总游戏 SG 值 = 各独立子游戏 SG 值的异或和，适用所有 ICG 游戏。

后记

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
这份笔记的记录大抵始于2024年10月，历经大一一整个学年的积累，最终于大一期末考试周、2025年7月7日开始系统性整理与总结并最终于7月9日整理完毕。
它不仅是对算法基础知识的梳理，更是我对大一学年算法学习的系统性回顾。
9月踏入校园时，心中既有对未知的憧憬，也藏着对方向的迷茫。
而选择学习算法、参与竞赛，让我在自由且个人时间充裕的大学环境里找到了些许的目标，也在一次次调试代码，找到了coding的乐趣。
更珍贵的是，这条路上总会遇见同样为一道题熬红双眼、为一个思路击掌欢呼的伙伴——他们既是并肩作战的队友，
也是彼此较劲的对手，这种良性的竞争氛围，远比独自摸索更能推着人往前。（everybody is important）
如果很不幸，你感到了独自学习的些许孤单，也希望你能享受独自coding的寂寞，能有举杯邀明月，对影成三人的乐观。
算法学习当然不是坦途，但抓住初学时的冲劲，耐下心听课、细心做题至关重要。
借着这股冲劲取得的成就，可以形成良好的正反馈，作为你日后迷茫时后盾与明灯。
我认为，学习的三个关键是学习、思考、实践。
学习是地基，也就是听课，需要耐心学习理论知识，理解算法的背后逻辑。
同时很重要的一点是，sort函数可以轻松排序，并不意味着学习冒泡排序无用，
更不意味着学习多种排序方法无用，那些前人们宝贵的经验方法可以拓宽你的思路与视野，
也会起到触类旁通，他山之石可以攻玉的效果。
思考是桥梁，学而不思则会陷入机械记忆和理论与实践脱离的困境，
只有带着带着举一反三疑问去沉下心思考，才能真正理解“所以然”；
实践是终点，也是新的起点。正如“实践是检验真理的唯一标准”，只有在深入思考后亲手写出ac的代码，
看着自己的思路用代码实现，才算真正把课程中的知识内化成自己的东西。
我想说，遭遇挫折与失败实属常态：或许是一道难题百思不解其意，或许是比赛中因细微疏漏导致满盘皆输，
又或许是投入大量精力却收效甚微。如果说问题不出于内，那也只能说尽人事，听天命
but the rain will stop the sky will clear up,nothing will be terrible forever. 
（雨会过，天会晴，事情不会一直这么糟的）
但真正值得思考的，正如肖恩医生所言——拒绝承认失败，并从失败中汲取教训。
面对挫折与失败，关键在于沉下心来完成发现问题、分析问题、解决问题的过程。
如此，失败方能转化为进阶的阶梯，助力你我前行。
最后，还有很多想写的但不知从何写起，那就到这结束吧。
May the road rise up to meet you. （愿你我前路坦荡，一帆风顺）

​ 记于2025年7月9日凌晨2时59分