算法学习笔记.md

算法学习笔记

一、用dp数组代替递归

#include<iostream>
using namespace std;
int find();
int chess[30][30]={0};
int n,m,x,y;
int output=0;
int nx=0,ny=0;
int main(){
    cin>>n>>m>>x>>y;
    chess[x][y]=-1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if((abs(i-x)+abs(j-y)==3)&&(j!=y)&&(i!=x)) chess[i][j]=-1;
        }
    }
    find();
    cout<<output;
}
int find(){
    if(chess[nx][ny]==-1) return 0;
    if(nx==n&&ny==m){
        output++;
        return 0;
    }
    if(nx<n){
        nx++;
        find();
        nx--;
    }
    if(ny<m){
        ny++;
        find();
        ny--;
    }
    return 0;
}

#include<iostream>
using namespace std;

int chess[30][30] = {0};
long long dp[30][30] = {0};
int n, m, x, y;

int main() {
    cin >> n >> m >> x >> y;
    chess[x][y] = -1;

    // 标记马的控制范围
    int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {
            chess[nx][ny] = -1;
        }
    }

    // 初始化dp数组
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (chess[i][j] == -1) {
                dp[i][j] = 0;
            } else {
                if (i > 0) dp[i][j] += dp[i-1][j];
                if (j > 0) dp[i][j] += dp[i][j-1];
            }
        }
    }

    cout << dp[n][m];
    return 0;
}

若直接使用递归则当数据较大时会出现超时的情况，此时需考虑DP数组 （动态规划数组，Dynamic Programming Array）

DP数组的作用

记录子问题的解

动态规划将复杂问题分解为多个重叠的子问题，DP数组用于存储这些子问题的解，后续直接查表复用，避免重复计算。
状态转移

DP数组中的每个元素通常代表某个状态的最优解（如最大值、最小值或可行解）。通过状态转移方程，从已知状态推导出未知状态的值。
优化时间复杂度

通过空间换时间，将指数级复杂度的暴力递归转化为多项式复杂度（如O(n^2)）。

DP数组的常见形式

根据问题复杂度，DP数组可以是一维、二维甚至多维：

一维数组 ：适用于单变量状态（如斐波那契数列、爬楼梯问题）。
```
dp[i] = dp[i-1] + dp[i-2]
```
二维数组 ：适用于双变量状态（如背包问题、最长公共子序列）。
```
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1
```

经典示例

斐波那契数列

递归解法重复计算严重，而DP数组只需线性时间：

dp = [0] * (n+1)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]

走迷宫路径总数问题
```
dp[i][j] = dp[i-1][j] + dp[i][j-1]
```

关键点

初始化 ：根据问题定义初始条件（如**dp[0]或dp[0][0]**）。
遍历顺序 ：确保状态转移时子问题的解已计算。
空间优化 ：部分问题可压缩DP数组维度（如用滚动数组将二维转一维）。

DP数组是解决最优化、计数类问题（如最长递增子序列、编辑距离）的重要工具，掌握其设计与状态转移方程是动态规划的关键。

二、用数组代替整数进行高精度计算

在C++中处理超大整数的高精度计算通常使用数组来模拟每一位数字，并手动实现算术运算。以下是详细的实现方法：

1. 存储方式

使用vector<int>存储数字，低位在前以便于处理进位和借位。例如，数值1234存储为[4,3,2,1]。

2. 输入输出转换

将字符串转换为数组，并处理前导零：

vector<int> stringToVector(const string& s) {
    vector<int> res;
    for (int i = s.size() - 1; i >= 0; --i) {
        res.push_back(s[i] - '0');
    }
// 去除输入的前导零，例如 "00123" -> "123"
    while (res.size() > 1 && res.back() == 0) {
        res.pop_back();
    }
    return res;
}

string vectorToString(const vector<int>& v) {
    if (v.empty()) return "0";
    string s;
    for (int i = v.size() - 1; i >= 0; --i) {
        s += (v[i] + '0');
    }
    return s;
}

3. 加法

逐位相加并处理进位：

vector<int> add(const vector<int>& a, const vector<int>& b) {
    vector<int> res;
    int carry = 0;
    for (int i = 0; i < max(a.size(), b.size()) || carry; ++i) {
        int digitA = (i < a.size()) ? a[i] : 0;
        int digitB = (i < b.size()) ? b[i] : 0;
        int sum = digitA + digitB + carry;
        res.push_back(sum % 10);
        carry = sum / 10;
    }
    return res;
}

4. 减法（假设a ≥ b）

逐位相减并处理借位，最后去除前导零：

vector<int> subtract(const vector<int>& a, const vector<int>& b) {
    vector<int> res;
    int borrow = 0;
    for (int i = 0; i < a.size(); ++i) {
        int digitA = a[i] - borrow;
        int digitB = (i < b.size()) ? b[i] : 0;
        borrow = (digitA < digitB) ? 1 : 0;
        if (borrow) digitA += 10;
        res.push_back(digitA - digitB);
    }
// 去除高位零
    while (res.size() > 1 && res.back() == 0) {
        res.pop_back();
    }
    return res;
}

5. 乘法

按位相乘并累加，最后处理进位：

vector<int> multiply(const vector<int>& a, const vector<int>& b) {
    vector<int> res(a.size() + b.size(), 0);
    for (int i = 0; i < a.size(); ++i) {
        for (int j = 0; j < b.size(); ++j) {
            res[i + j] += a[i] * b[j];
        }
    }
// 统一处理进位
    int carry = 0;
    for (int k = 0; k < res.size(); ++k) {
        int value = res[k] + carry;
        res[k] = value % 10;
        carry = value / 10;
    }
// 去除高位零
    while (res.size() > 1 && res.back() == 0) {
        res.pop_back();
    }
    return res;
}

6. 除法（高精度除以低精度）

此处以高精度数除以普通整数为例：

vector<int> divide(const vector<int>& a, int b, int& remainder) {
    vector<int> res;
    remainder = 0;
    for (int i = a.size() - 1; i >= 0; --i) {// 从高位开始处理
        remainder = remainder * 10 + a[i];
        res.push_back(remainder / b);
        remainder %= b;
    }
    reverse(res.begin(), res.end());
// 去除高位零
    while (res.size() > 1 && res.back() == 0) {
        res.pop_back();
    }
    return res;
}

7. 高精度比较

比较两个高精度数的大小：

int compare(const vector<int>& a, const vector<int>& b) {
    if (a.size() != b.size()) {
        return a.size() > b.size() ? 1 : -1;
    }
    for (int i = a.size() - 1; i >= 0; --i) {// 高位在数组末尾
        if (a[i] != b[i]) return a[i] > b[i] ? 1 : -1;
    }
    return 0;
}

8. 示例用法

int main() {
    string s1 = "123456789";
    string s2 = "987654321";

    vector<int> num1 = stringToVector(s1);
    vector<int> num2 = stringToVector(s2);

    vector<int> sum = add(num1, num2);
    cout << "Sum: " << vectorToString(sum) << endl;

    if (compare(num1, num2) >= 0) {
        vector<int> diff = subtract(num1, num2);
        cout << "Difference: " << vectorToString(diff) << endl;
    } else {
        cout << "num1 is smaller than num2" << endl;
    }

    vector<int> product = multiply(num1, num2);
    cout << "Product: " << vectorToString(product) << endl;

    int divisor = 123;
    int remainder;
    vector<int> quotient = divide(num1, divisor, remainder);
    cout << "Quotient: " << vectorToString(quotient)
         << ", Remainder: " << remainder << endl;

    return 0;
}

说明

高精度除以高精度的实现较为复杂，通常涉及试商法或二分查找，需要结合减法、乘法和比较操作。
上述代码未处理负数，实际应用中可添加符号位并在运算时处理符号逻辑。
除法示例展示了除以普通整数的方法，高精度之间的除法需要更复杂的逻辑，建议参考专门的高精度算法库或进一步学习试商法。

三、BFS与并查集路径压缩

题目描述

跳房子游戏是西西艾弗岛上孩子们的传统娱乐方式。今天小 P 造访了西西艾弗岛，小 C 向他示范了跳房子游戏该怎么玩。

在地面上有一字排开的$n$个格子，每个格子上都写着一个数字，第$i$个格子上写着的数字是$a_i$。这些数字满足$a_i < i$且$a_n = 0$。

一开始，小 C 站在第一个格子上。小 C 是一个擅长跳跃的人，他可以往前跳很远，但为了游戏的趣味性，小 C 规定在第$i$个格子上最多能往前跳$k_i$格，而且不能跳到第$n$个格子后面。也就是说，如果小 C 现在站在第$i$个格子上，那么他可以跳到第$i+1$个格子和第$\min(n, i + k_i)$个格子之间的任意格子上。

根据跳房子游戏的规则，如果小 C 在一次跳跃之后落到了第$i$个格子上，那么他需要后退$a_i$格，也就是说小 C 在跳跃后会站在第$i - a_i$个格子上。

玩了一会之后，小 P 突然好奇，小 C 最少需要跳多少次才能到达第$n$个格子呢？小 C 也不知道这个答案，于是他只能来请教你。

输入格式

第一行一个正整数$n$，代表格子的数量。

第二行$n$个非负整数$a_1, a_2, \ldots, a_n$，其中$a_i$表示第$i$个格子上的数字。

第三行$n$个非负整数$k_1, k_2, \ldots, k_n$，其中$k_i$表示小 C 在第$i$个格子时能往前跳的最大格数。

输出格式

输出一行一个整数表示小 C 到达第$n$个格子需要的最少跳跃次数，如果小 C 不能到达第$n$个格子输出$-1$。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

// 并查集相关
int fa[MAXN]; // 并查集数组，用于快速找到未处理的节点

// 路径压缩的查找函数
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]); // 路径压缩优化
    return fa[x];
}

int main() {
    int n;
    cin >> n;
    int a[n+1], k[n+1], dp[n+1]; // 输入数据数组和DP数组

    // 读取输入数据
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i] = -1; // 初始化DP为-1（表示未到达）
    }
    for (int i = 1; i <= n; i++) {
        cin >> k[i];
    }

    // 预处理：计算每个位置j跳跃后的实际目标位置
    int pos[n+1]; // pos[j] = j - a[j]
    for (int j = 1; j <= n; j++) {
        pos[j] = j - a[j];
    }

    // 初始化并查集（每个位置指向自己）
    for (int j = 1; j <= n+1; j++) {
        fa[j] = j;
    }

    // BFS初始化
    queue<int> q;
    dp[1] = 0;    // 起点步数为0
    q.push(1);    // 从起点开始搜索

    while (!q.empty()) {
        int i = q.front(); // 当前处理的位置
        q.pop();

        // 确定跳跃范围[i+1, i+k[i]]
        int start = i + 1;
        int end = i + k[i];
        if (end > n) end = n; // 防止越界

        if (start > end) continue; // 无效范围直接跳过

        // 使用并查集快速遍历可到达的节点
        int j = find(start); // 找到第一个未处理的节点
        while (j <= end) {
            int p = pos[j]; // 计算实际目标位置

            // 如果目标位置未到达过
            if (dp[p] == -1) {
                dp[p] = dp[i] + 1; // 更新步数
                q.push(p);         // 加入队列继续搜索
            }

            // 将当前节点标记为已处理（指向下一个位置）
            fa[j] = find(j + 1);
            // 继续查找下一个未处理的节点
            j = find(j);
        }
    }

    cout << dp[n]; // 输出到达终点的最小步数
    return 0;
}

重点：fa[i]数组与find函数来避免重复处理

考虑使用BFS（广度优先处理），则每个节点只需被处理一次（相同节点的后续处理所用步数一定大于第一次处理）。利用fa数组则可以索引到下一个未被处理过的节点。

在代码中，fa[i] 是并查集（Union-Find）的数据结构，其核心意义是动态维护未处理的节点，实现跳跃式遍历的高效性。以下是具体解析：

`fa[i]` 的核心意义

初始状态：
- 每个位置 i 的 fa[i] 初始化为 i（即指向自己）。
- 含义：所有位置均未被处理，属于独立的集合。
处理过程中的动态更新：
- 当处理位置 i 的跳跃范围 [i+1, i+k[i]] 时，通过 find 函数快速找到该范围内第一个未处理的节点 j。
- 处理完 j 后：将 fa[j] 指向 j+1，即 fa[j] = find(j+1)。
- 效果：后续再次访问到 j 时，find(j) 会直接跳过 j，返回 j+1 的根节点。
路径压缩优化：
- find 函数通过递归路径压缩，使得每个节点的父节点直接指向根节点。
- 结果：fa[i] 最终形成一个“指针链”，将所有已处理的节点链接到未处理节点的起始位置。

`fa[i]` 的具体作用

1. 快速定位未处理的节点

问题：在 BFS 遍历中，每次需要处理 [i+1, i+k[i]] 范围内的节点。若逐个检查是否已处理，时间复杂度为 O(n²)。
解决方案：
- 使用 find(j) 找到范围内第一个未被处理的节点。
- 例如，若 j=2 已处理，则 find(2) 返回 3，直接跳过已处理的 2。

2. 标记已处理的节点

操作：处理完节点 j 后，执行 fa[j] = find(j+1)。
效果：
- 将 j 的父节点指向 j+1 的根节点。
- 后续调用 find(j) 时，直接返回 j+1 的根节点，从而跳过 j。

3. 维护跳跃式遍历

关键逻辑：

int j = find(start);// 找到第一个未处理的节点
while (j <= end) {
    process(j);// 处理节点 j
    fa[j] = find(j+1);// 标记 j 为已处理
    j = find(j);// 跳转到下一个未处理的节点
}

过程示意图：

初始状态: [1]->1, [2]->2, [3]->3, [4]->4, [5]->5
处理 j=2 后: [2]->3, [3]->3 → find(2) 返回 3
处理 j=3 后: [3]->4, [4]->4 → find(3) 返回 4

示例演算

假设 n=5，初始 fa[] = [1,2,3,4,5]：

| 步骤 | 操作 | fa[] 变化 | 说明 | | | | | | | 1 | 处理 i=1，范围 [2,3] | fa[2]=3, fa[3]=4 | find(2) 直接返回 3 → 跳过 2 | | 2 | 处理 i=3，范围 [4,6] | fa[4]=5, fa[5]=6 | find(4) 返回 5 → 处理 4 |

最终，所有节点被高效处理，无需重复检查。

为什么需要 `fa[i]`？

避免重复处理：
- 通过 fa[i] 的指针链，确保每个节点仅被处理一次。
时间复杂度优化：
- 传统 BFS 遍历需要 O(n²) 时间（每次检查所有跳跃位置）。
- 使用并查集后，时间复杂度降至 O(n α(n))（接近线性）。

路径压缩的目标

核心问题：传统的并查集在多次合并后，树可能退化成链状结构（如 1 → 2 → 3 → 4），导致查找根节点的复杂度为 O(n)。
优化目标：通过压缩查找路径，使得每个节点直接指向根节点，降低后续查找的时间复杂度至 接近 O(1)。

路径压缩的实现

在代码中，路径压缩通过递归或迭代的查找函数实现。以下是代码中的关键函数：

int find(int x) {
    if (fa[x] != x)
        fa[x] = find(fa[x]);// 递归路径压缩
    return fa[x];
}

递归压缩过程

查找根节点：递归查找 x 的父节点，直到找到根节点（fa[root] = root）。
压缩路径：在递归返回时，将路径上的所有节点直接指向根节点。

示例演算

假设初始树结构为 1 → 2 → 3 → 4（根节点是1）：

调用 find(4)：
- fa[4] = 3 → 递归调用 find(3)。
- fa[3] = 2 → 递归调用 find(2)。
- fa[2] = 1 → 递归调用 find(1)（根节点）。
- 回溯时更新路径：
  - fa[3] = 1（原指向2，现在直接指向根1）。
  - fa[4] = 1（原指向3，现在直接指向根1）。
最终树结构：所有节点直接指向根节点 1。

路径压缩的复杂度分析

单次查找：接近 O(1)（严格来说是 O(α(n))，其中 α 是阿克曼函数的反函数，增长极慢）。
多次操作：经过路径压缩后，N 次操作的均摊时间复杂度接近 O(N)。

路径压缩的适用场景

频繁查找操作：需要多次查询根节点的场景（如动态连通性问题）。
大规模数据：当数据量极大时，路径压缩的优化效果显著。
与 BFS/DFS 结合：在需要高效跳过已处理节点的算法中（如本题的跳跃问题）。

四、线段树

已知一个数列，你需要进行下面两种操作：

将某区间内的每一个数加上k
求出某空间内的所有数的和

使用常规方法则每次操作的时间复杂度均为O(n)，考虑使用线段树将时间复杂度缩短到O(log n)

线段树模板：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll n, a[100005], d[270000], b[270000]; 
// n:数组长度 a:原数组 d:线段树数组 b:懒标记数组
//build:建树 update:更新 getsum:查询
void build(ll l,ll r,ll p){  // l:区间左端点 r:区间右端点 p:节点标号
    if(l==r){
        d[p]=a[l];
        return;
    }
    ll m = l + (r-l)/2;
    build(l,m,p*2);
    build(m+1,r,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}

void update(ll l,ll r,ll c,ll s,ll t,ll p){  // l:区间左端点 r:区间右端点 c:增加的值 s:修改的区间左端点 t:修改的区间右端点 p:节点标号
    if(l<=s && t<=r){
        d[p]+=(t-s+1)*c;
        b[p]+=c;
        return;
    }
    ll m = s + (t-s)/2;
    if(b[p]){
        d[p*2]+=(m-s+1)*b[p];
        d[p*2+1]+=(t-m)*b[p];
        b[p*2]+=b[p];
        b[p*2+1]+=b[p];
        b[p]=0;
    }
    if(l<=m) update(l,r,c,s,m,p*2);
    if(r>m) update(l,r,c,m+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}

ll getsum(ll l,ll r,ll s,ll t,ll p){ // l:区间左端点 r:区间右端点 s:查询的区间左端点 t:查询的区间右端点 p:节点标号  
    if(l<=s && t<=r) return d[p];
    ll m = s + (t-s)/2;
    if(b[p]){
        d[p*2]+=(m-s+1)*b[p];
        d[p*2+1]+=(t-m)*b[p];
        b[p*2]+=b[p];
        b[p*2+1]+=b[p];
        b[p]=0;
    }
    ll sum=0;
    if(l<=m) sum+=getsum(l,r,s,m,p*2);
    if(r>m) sum+=getsum(l,r,m+1,t,p*2+1);
    return sum;
}
int main(){
    ll q,i1,i2,i3,i4;
    cin>>n>>q;
    for(ll i=1;i<=n;i++) cin>>a[i];
    build(1,n,1);
    while(q--){
        cin>>i1>>i2>>i3;
        if(i1==2){
            cout<<getsum(i2,i3,1,n,1)<<endl;
        }else{
            cin>>i4;
            update(i2,i3,i4,1,n,1);
        }
    }
    return 0;
}

五、二分查找

使用贪心算法+二分查找的方法，借助lower_bound，upper_bound等函数实现在$O(nlogn)$的时间复杂度下完成寻找。

快速求序列的最长递增(递减)子序列的长度 P1020

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a;
    int temp;
    while (cin >> temp) {
        a.push_back(temp);
    }
    int n = a.size();
    
    // 处理最长非递增子序列
    vector<int> dp1;
    for (int x : a) {
        // 使用upper_bound在非递增数组中找插入位置
        auto it = upper_bound(dp1.begin(), dp1.end(), x, greater<int>());
        //寻找第一个小于x的位置
        if (it == dp1.end()) {
            dp1.push_back(x);
        } else {
            *it = x;
        }
    }
    int res1 = dp1.size();
    
    // 处理最长递增子序列
    vector<int> dp2;
    for (int x : a) {
        // 使用lower_bound在递增数组中找插入位置
        auto it = lower_bound(dp2.begin(), dp2.end(), x);
        //寻找第一个不小于x的位置
        if (it == dp2.end()) {
            dp2.push_back(x);
        } else {
            *it = x;
        }
    }
    int res2 = dp2.size();
    
    cout << res1 << endl << res2 << endl;
    return 0;
}

求序列中某数出现次数 P1102

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int N, C;
    cin >> N >> C;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    // 从小到大排序
    ll key = 0;
    for (auto it = a.begin(); it != a.end(); ++it) {
        int temp = *it + C;
        // 寻找 a 中等于 temp 的数的个数
        auto it_lower = lower_bound(next(it), a.end(), temp);
        // it_lower 为第一个大于等于 temp 的数的下标
        auto it_upper = upper_bound(next(it), a.end(), temp);
        // it_upper 为第一个大于 temp 的数的下标
        ll count = it_upper - it_lower;
        key += count;
    }
    cout << key << endl;
}

六、使用优先队列快速输出最大元素

在 C++ 中，优先队列（priority_queue）是一种容器适配器，用于实现堆（Heap）数据结构。它允许我们以高效的方式动态地插入元素，并始终能够快速访问优先级最高的元素（通常是最大值或最小值）。优先队列广泛应用于各种算法和场景中，例如 Dijkstra 最短路径算法、Huffman 编码等。

基本特性

底层实现：priority_queue 默认基于一个最大堆（Max Heap）实现，也就是说，默认情况下，队列的顶部元素是最大的。
访问限制：优先队列只允许访问优先级最高的元素（即堆顶元素），并且只能从顶部删除元素。无法直接访问其他元素。
时间复杂度：
- 插入元素（push）：$\mathcal{O}(\log n)$
- 删除顶部元素（pop）：$\mathcal{O}(\log n)$
- 访问顶部元素（top）：$\mathcal{O}(1)$

基本用法

#include <iostream>
#include <queue>

int main() {
    // 定义一个默认的最大堆优先队列
    priority_queue<int> pq;

    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // 输出优先队列的顶部元素
    cout << "Top element: " << pq.top() << endl; // 输出 30

    // 删除顶部元素
    pq.pop();

    // 再次输出顶部元素
    cout << "Top element after pop: " << pq.top() << endl; // 输出 20

    return 0;
}

自定义比较规则

默认情况下，priority_queue 是一个最大堆。如果需要实现最小堆或其他自定义规则，可以通过自定义比较函数来实现。

示例：实现最小堆

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 使用 greater<int> 实现最小堆
    priority_queue<int, vector<int>, greater<int>> pq;

    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // 输出优先队列的顶部元素
    cout << "Top element (min heap): " << pq.top() << endl; // 输出 10

    // 删除顶部元素
    pq.pop();

    // 再次输出顶部元素
    cout << "Top element after pop: " << pq.top() << endl; // 输出 20

    return 0;
}

示例：自定义对象的优先队列

假设我们有一个自定义类 Person，并希望根据年龄进行排序：

#include <iostream>
#include <queue>
#include <string>

struct Person {
    string name;
    int age;

    // 构造函数
    Person(string name, int age) : name(name), age(age) {}
};

// 自定义比较规则
struct CompareAge {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age; // 按年龄从大到小排序
    }
};

int main() {
    // 定义优先队列，使用自定义比较规则
    priority_queue<Person, vector<Person>, CompareAge> pq;

    // 插入元素
    pq.push(Person("Alice", 30));
    pq.push(Person("Bob", 25));
    pq.push(Person("Charlie", 35));

    // 输出优先队列的顶部元素
    cout << "Top person: " << pq.top().name << " (" << pq.top().age << " years old)" << endl;

    return 0;
}

重要成员函数

以下是 priority_queue 的常用成员函数及其功能：

| 函数名 | 功能描述 | |--|| | push(value) | 向队列中插入一个元素 | | pop() | 删除队列中的顶部元素 | | top() | 返回队列中的顶部元素（不删除） | | empty() | 检查队列是否为空 | | size() | 返回队列中元素的数量 |

七、使用稀疏表（ST）预处理降低时间复杂度

例题（CSP-37-4）

已知： $$f(l, r) = gcd(a_l, a_{l+1}, \ldots, a_r)$$ 求： $$\sum_{i=1}^{n} \sum_{j=i}^{n} (f(i, j) \times i \times j)$$

A、构建并用动态规划填充稀疏表

稀疏表（Sparse Table）是一种用于快速查询区间信息的数据结构。在本题中，稀疏表被用来高效地存储和查询任意区间的最大公约数（GCD）。以下是稀疏表的构建过程：

int k = log2(n) + 1;
vector<vector<int>> st(n + 1, vector<int>(k + 1));
for (int i = 1; i <= n; ++i) {
    st[i][0] = a[i];
}
for (int j = 1; j <= k; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
        st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
}

1. 初始化稀疏表

$$ st[i][0] = a[i] $$

第一列表示长度为$2^0 = 1$的区间，因此直接初始化为数组中的元素值。

2. 动态规划填充稀疏表

对于$j \geq 1$，通过动态规划公式填充稀疏表： $$ st[i][j] = \text{gcd}(st[i][j-1], st[i + 2^{j-1}][j-1]) $$ -$st[i][j-1]$：表示从$i$开始，长度为$2^{j-1}$的区间的 GCD。 -$st[i + 2^{j-1}][j-1]$：表示从$i + 2^{j-1}$开始，长度为$2^{j-1}$的区间的 GCD。

两个子区间的并集正好覆盖了从$i$开始，长度为$2^j$的区间，因此它们的 GCD 就是整个大区间的 GCD。

B、定义区间查询函数

为了快速查询任意区间的 GCD 值，我们定义了一个查询函数：

auto query_gcd = [&](int l, int r) {
    int len = r - l + 1;
    int j = log2(len);
    return gcd(st[l][j], st[r - (1 << j) + 1][j]);
};

1. 查询原理

对于任意区间$[l, r]$，其 GCD 值可以通过两个重叠子区间的 GCD 值计算得到： $$ \text{gcd}([l, r]) = \text{gcd}(st[l][j], st[r - 2^j + 1][j]) $$ 其中： -$j = \lfloor \log_2(r - l + 1) \rfloor$，即满足$2^j \leq r - l + 1$的最大指数。 -$st[l][j]$：表示从$l$开始，长度为$2^j$的区间的 GCD。 -$st[r - 2^j + 1][j]$：表示从$r - 2^j + 1$开始，长度为$2^j$的区间的 GCD。

C、主逻辑：遍历所有起始位置并计算贡献值

以下是主逻辑部分的代码：

long long res = 0;
for (int i = 1; i <= n; ++i) {
    int current_gcd = a[i];
    int left = i;
    while (left <= n) {
        int l = left, r = n;
        int best = left;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (query_gcd(i, mid) == current_gcd) {
                best = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        long long sum_j = (long long)(best + left) * (best - left + 1) / 2 % MOD;
        res = (res + (long long)current_gcd * i % MOD * sum_j % MOD) % MOD;
        left = best + 1;
        if (left <= n) {
            current_gcd = query_gcd(i, left);
        }
    }
}
cout << res << '\n';

1. 遍历每个起始位置

外层循环遍历数组中的每个起始位置$i$。对于每个$i$，我们需要找到以$i$为起点的所有区间，并计算它们对结果的贡献值。

2. 使用二分查找确定区间

内层循环通过二分查找确定以$i$为起点的最大区间$[left, best]$，使得该区间的 GCD 值等于$\text{current_gcd}$。具体步骤如下：

定义搜索范围$[l, r]$，初始值为$[left, n]$。
计算中间点$mid = \lfloor \frac{l + r}{2} \rfloor$。
如果$\text{query_gcd}(i, mid) = \text{current_gcd}$，说明区间可以扩展到$mid$，更新$best = mid$并继续向右搜索。
否则，向左收缩搜索范围。

3. 计算区间贡献值

对于区间$[left, best]$，其贡献值为： $$ \text{贡献值} = \text{current_gcd} \times i \times \sum_{j=left}^{best} j \mod MOD $$ 其中： -$\sum_{j=left}^{best} j$是区间$[left, best]$内所有索引的和，公式为： $$ \sum_{j=left}^{best} j = \frac{(best + left) \times (best - left + 1)}{2} $$

最终结果累加到$\text{res}$中，并对$MOD$取模。

4. 更新状态

更新$left = best + 1$，继续处理下一个区间。
如果$left \leq n$，更新$\text{current_gcd} = \text{query_gcd}(i, left)$。

D、总结

稀疏表的作用：稀疏表通过动态规划的方式预处理数组中任意区间的 GCD 值，支持$O(1)$时间复杂度的区间查询。
二分查找的优化：通过二分查找确定以某个起始位置为起点的最大区间，避免暴力枚举所有可能的区间。
贡献值的计算：利用数学公式高效计算区间内的索引和，从而快速累加贡献值。
时间复杂度：$O(n⋅logn⋅logV)$

八、使用Dijkstra算法寻找最小路径

1. 概述

Dijkstra 算法是一种经典的单源最短路径算法，用于在一个加权图中找到从一个起点到其他所有节点的最短路径。它由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年提出。

适用场景：适用于带非负权值的图。
时间复杂度：
- 普通实现：$O(V^2 + E)$（稠密图）。
- 优先队列优化：$O((V + E) \log V)$（稀疏图）。

2. 核心思想

Dijkstra 算法基于贪心策略，逐步扩展当前已知的最短路径，直到覆盖所有节点。其核心思想可以概括为以下几点：

初始化：将起点的距离设为 0，其他节点的距离设为无穷大（$\infty$）。
选择最小距离节点：从未处理的节点中选择当前距离最小的节点作为当前节点。
松弛操作：尝试通过当前节点更新其邻接节点的距离。如果通过当前节点到达某个邻接节点的距离更短，则更新该邻接节点的距离。
重复：标记当前节点为已处理，并继续选择下一个未处理且距离最小的节点，直到所有节点都被处理。

3. 算法步骤

以下是 Dijkstra 算法的详细步骤：

初始化：
- 定义数组$\text{dist}[v]$，用于存储从起点到每个节点$v$的最短距离，初始值为$\infty$，起点的距离为 0。
- 定义布尔数组$\text{visited}[v]$，用于标记节点是否已经处理过。
选择当前节点：
- 从未处理的节点中选择当前距离最小的节点$u$。
松弛操作：
- 遍历当前节点$u$的所有邻接边$(u, v, w)$，尝试更新邻接节点$v$的距离： $$ \text{dist}[v] = \min(\text{dist}[v], \text{dist}[u] + w) $$
标记已处理：
- 将当前节点$u$标记为已处理。
重复：
- 重复上述过程，直到所有节点都被处理或优先队列为空。

4. C++ 实现

以下是用 C++ 实现 Dijkstra 算法的关键代码：

数据结构定义

struct Edge {
    int to;     // 目标节点
    int weight; // 边的权重
};

核心算法

void dijkstra(int start, const vector<vector<Edge>>& graph, vector<int>& dist) {
    int n = graph.size(); // 图中节点的数量
    dist.assign(n, INT_MAX); // 初始化距离为无穷大
    dist[start] = 0; // 起点到自身的距离为 0

    // 定义优先队列 (距离, 节点)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start}); // 将起点加入优先队列

    while (!pq.empty()) {
        auto [currentDist, u] = pq.top(); // 取出当前距离最小的节点
        pq.pop();

        // 如果当前距离大于已知的最短距离，跳过
        if (currentDist > dist[u]) continue;

        // 遍历 u 的所有邻接边
        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            // 松弛操作：尝试更新到 v 的更短路径
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight; // 更新最短距离
                pq.push({dist[v], v});      // 将更新后的节点加入优先队列
            }
        }
    }
}

5. 时间复杂度分析

普通实现（使用数组选择最小距离节点）：
- 每次选择最小距离节点需要$O(V)$，共需选择$V$次。
- 每次松弛操作需要遍历所有边，总时间为$O(E)$。
- 总时间复杂度为： $$ O(V^2 + E) $$
优化实现（使用优先队列）：
- 每次插入和删除操作的时间复杂度为$O(\log V)$。
- 总时间复杂度为： $$ O((V + E) \log V) $$

6. 注意事项

负权边：
- Dijkstra 算法不能处理负权边。如果图中存在负权边，请改用 Bellman-Ford 算法。
无向图：
- 如果图是无向图，在添加边时需要同时添加正向和反向边。
不可达节点：
- 如果某些节点无法从起点到达，它们的距离会保持为$\infty$，在输出时可以用 "INF" 表示。

九、unordered_map代替传统单向链表

unordered_map 是 C++ 标准库中的一个关联容器，用于存储键值对（key-value pairs），其底层实现是哈希表（hash table）。与 map 不同的是，unordered_map 不保证元素的顺序，但提供了平均情况下 常数时间复杂度 的查找、插入和删除操作。

📌 基本特性

无序性（Unordered）：不按 key 的顺序排列。
唯一键（Unique keys）：每个 key 在 map 中必须是唯一的。
快速访问：基于哈希函数实现，查找、插入、删除的时间复杂度为：
- 平均情况：O(1)
- 最坏情况：O(n)（哈希冲突严重时）

🔧 定义和初始化

unordered_map<key_type, value_type> map_name;

示例：B3631 单向链表

题目描述

实现一个数据结构，维护一张表（最初只有一个元素 $1$）。需要支持下面的操作，其中 $x$ 和 $y$ 都是 $1$ 到 $10^6$ 范围内的正整数，且保证任何时间表中所有数字均不相同，操作数量不多于 $10^5$：

1 x y ：将元素 $y$ 插入到 $x$ 后面；
2 x ：询问 $x$ 后面的元素是什么。如果 $x$ 是最后一个元素，则输出 $0$；
3 x：从表中删除元素 $x$ 后面的那个元素，不改变其他元素的先后顺序。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    unordered_map<int, int> next_node; // 当前节点 -> 下一节点
    next_node[1] = 0; // 初始只有一个元素 1，后面没有元素
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;// 插入 y 到 x 后面
            next_node[y] = next_node[x]; // y 指向 x 原来的下一个
            next_node[x] = y;             // x 现在指向 y
        } else if (op == 2) {
            int x;
            cin >> x;
            cout << next_node[x] << '\n';
        } else if (op == 3) {
            int x;
            cin >> x;
            int to_delete = next_node[x];
            if (to_delete != 0) {
                next_node[x] = next_node[to_delete]; // 跳过要删除的节点
                next_node.erase(to_delete);          // 删除该节点
            }
        }
    }
    return 0;
}

🧩 常用操作

操作	描述
`map[key]`	访问或插入指定 key 的元素
`map.at(key)`	访问指定 key 的元素，若不存在则抛出异常
`map.insert({key, value})`	插入键值对
`map.find(key)`	返回指向该 key 的迭代器，若未找到返回 `end()`
`map.erase(key)` / `map.erase(it)`	删除指定 key 或迭代器位置的元素
`map.size()`	返回当前元素个数
`map.empty()`	判断是否为空
`map.clear()`	清空所有元素

⚙️ 自定义哈希函数和比较函数

默认情况下，unordered_map 使用 hash 来计算 key 的哈希值，并使用 operator== 进行相等比较。如果要使用自定义类型作为 key，则需要提供相应的哈希函数和比较函数。

示例：使用自定义结构体作为 key

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash {
    size_t operator()(const Point& p) const {
        return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
    }
};

int main() {
    unordered_map<Point, string, PointHash> pointMap;
    pointMap[{1, 2}] = "Point A";
    pointMap[{3, 4}] = "Point B";

    for (const auto& [key, val] : pointMap) {
        cout << "(" << key.x << ", " << key.y << "): " << val << "\n";
    }

    return 0;
}

🆚 unordered_map vs map

特性	`unordered_map`	`map`
内部结构	哈希表	红黑树（平衡二叉搜索树）
元素顺序	无序	按 key 升序排列
插入/查找时间复杂度	平均 O(1)，最差 O(n)	O(log n)
是否支持自定义比较	支持（需自定义哈希和等于函数）	支持（可通过比较函数自定义排序）

FilesExpand file tree

算法学习笔记.md

Latest commit

History

算法学习笔记.md

File metadata and controls

算法学习笔记

一、用dp数组代替递归

DP数组的作用

DP数组的常见形式

经典示例

关键点

二、用数组代替整数进行高精度计算

1. 存储方式

2. 输入输出转换

3. 加法

4. 减法（假设a ≥ b）

5. 乘法

6. 除法（高精度除以低精度）

7. 高精度比较

8. 示例用法

说明

三、BFS与并查集路径压缩

题目描述

输入格式

输出格式

重点：fa[i]数组与find函数来避免重复处理

fa[i] 的核心意义

fa[i] 的具体作用

示例演算

为什么需要 fa[i]？

路径压缩的目标

路径压缩的实现

递归压缩过程

示例演算

路径压缩的复杂度分析

路径压缩的适用场景

四、线段树

五、二分查找

快速求序列的最长递增(递减)子序列的长度 P1020

求序列中某数出现次数 P1102

六、使用优先队列快速输出最大元素

基本特性

基本用法

自定义比较规则

示例：实现最小堆

示例：自定义对象的优先队列

重要成员函数

七、使用稀疏表（ST）预处理降低时间复杂度

例题（CSP-37-4）

A、构建并用动态规划填充稀疏表

1. 初始化稀疏表

2. 动态规划填充稀疏表

B、定义区间查询函数

1. 查询原理

C、主逻辑：遍历所有起始位置并计算贡献值

1. 遍历每个起始位置

2. 使用二分查找确定区间

3. 计算区间贡献值

4. 更新状态

D、总结

八、使用Dijkstra算法寻找最小路径

1. 概述

2. 核心思想

3. 算法步骤

4. C++ 实现

数据结构定义

核心算法

5. 时间复杂度分析

6. 注意事项

九、unordered_map代替传统单向链表

📌 基本特性

🔧 定义和初始化

示例：B3631 单向链表

题目描述

🧩 常用操作

⚙️ 自定义哈希函数和比较函数

示例：使用自定义结构体作为 key

🆚 unordered_map vs map

`fa[i]` 的核心意义

`fa[i]` 的具体作用

为什么需要 `fa[i]`？