Skip to content

note

输入输出优化：

1
2
3
ios::sync_with_stdio(false);
cin.tie(nullptr); 
cout.tie(nullptr);

pair，swap，make_pair在utility里

格式化输出

  1. 浮点数精度 永久，除非手动改回

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
    double pi = 3.1415926535;
cout << fixed << setprecision(2) << pi << "\n"; // 输出 3.14
cout << fixed << setprecision(5) << pi << "\n"; // 输出 3.14159
cout.unsetf(ios::fixed);  //恢复默认输出

//或
cout << fixed << setprecision(6);
double a = 1.2, b = 3.45678910;
cout << a << "\n"; // 1.200000
cout << b << "\n"; // 3.456789

  2. 宽度和填充 一次性，每个输出都要写

功能 代码示例 说明
设置宽度 setw(n) 仅对紧随其后的一个输出有效
设置填充字符 setfill('c') 配合 setw 使用，填充未满处
左对齐 left 默认是右对齐
右对齐 right 恢复默认对齐方式

实例：

1
2
3
4
5
6
int h = 9, m = 5;
// 输出 09:05
cout << setfill('0') << setw(2) << h << ":" << setw(2) << m << "\n";

// 输出左对齐的 10 位宽度
cout << left << setw(10) << "Name" << "Score" << "\n";

  1. 进制转换

    十六进制：cout << hex << 255; （输出 ff）

    八进制：cout << oct << 8; （输出 10）

    十进制：cout << dec << 10; （恢复默认）

    大写控制：cout << uppercase << hex << 255; （输出 FF）

常用STL及其方法

Vector

  • 声明：vector\ v或vector\ v(n,init_val)（初始值
  • push_back(x)
  • size()
  • empty()
  • clear()

String

  • s.substr(pos,len)：截取字符串，pos表示起始索引
  • s.find(str)：查找子串，找不到返回 string::npos
  • s.length()/s.size()

Set/Multiset

自带排序，不允许/允许重复元素

  • insert(x)
  • erase(x)：删除值为x的元素
  • find(x)：查找值为x的迭代器，如果不存在则返回s.end()
  • count(x)：返回x的数量

map/multimap

带排序，按key排

  • mp.count(key)：检查key是否存在，返回1/0.

stack 先进后出 没有clear

  • push(),pop(),top(),empty()

queue 先进先出 没有clear

  • push(),pop(), front(), back()

priority_queue 堆 没有clear

  • push(x), pop(), top()
  • priority_queue<int> pq;：大根堆
  • priority_queue<int, vector<int>, greater<int>> pq;：小根堆，如果元素是pair默认按第一个值排。

deque 双端队列

  • push_front() / push_back() ，pop_front() / pop_back()
  • front(),back(),size(),empty()
  • clear()

algorithm

函数名 功能 复杂度
sort(v.begin(), v.end()) 快速排序（升序） \(O(n \log n)\)
reverse(v.begin(), v.end()) 翻转容器内容 \(O(n)\)
unique(v.begin(), v.end()) 去重（需先排序） \(O(n)\)
lower_bound(v.begin(), v.end(), x) 查找第一个 \(\ge x\) \(O(\log n)\)

去重：

1
2
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

sort 自定义排序

1
2
3
4
5
6
bool cmp(const Item& a, const Item& b) {
    return a.w < b.w; // 升序：a.w 小的在前
}

// 使用时
sort(items.begin(), items.end(), cmp);

对区间[L,R]排序：

1
2
// 语法：sort(v.begin() + 起始下标, v.begin() + 结束下标 + 1);
sort(v.begin() + L, v.begin() + R + 1);

最小公倍数

采用两两合并的形式，根据最小公倍数的性质可知：\(n\) 个数的最小公倍数是这些数中每个数进行质因数分解后，所有的质因数按对应次数累乘的最终结果。

  • 预处理：根据题目给的数据范围进行质数打表。本题题目范围是 \(1e9\)，因此需要计算 \(sqrt(1e9)\) 范围内的质数。
  • 根据质数表找检查每个数的质因数和其对应的次数：
    • 如果一个质因数在不同的数中都有分解出，则次数取高者。
    • 需要注意如果遍历完所有表内质数后，该数还有剩余，则它是一个在 \(sqrt(1e9)\) 范围外的质数，需要单独记录。
  • 基于快速幂求质因数表的乘积和，注意取模。

最大公约数

即辗转相除法，快速求最大公约数。

已知 \(a, b\) 两数，求两者最大公约数，用其中大数除以小数，取余数；对于小数和余数，用大数除以小数，取余数……直到余数为 0，此时的除数就是两者的最大公约数。

基于数学方法的回文数判断

对于 int 型的数字串，如果转换为字符串再判断会有频繁的栈开销和较大的常数，因此可以考虑通过提取 + 翻转原数（除10取模，模*10 ，直到中间位）的后半段，并判断翻转后的数字串是否和前半段相等来快速推断。

组合数计算

从 \(m\) 个不同元素中不重复、不考虑顺序地选出 \(n\) 个的方式总数：

\[C(m, n) = \binom{m}{n} = \frac{m!}{n!(m-n)!}\]

如果需要去重需要在计算前：

1
2
3
std::vector<int> A = {1, 2, 2, 3};
std::set<int> unique_set(A.begin(), A.end()); // 自动去重
std::vector<int> unique_vec(unique_set.begin(), unique_set.end());

埃式筛 \(O(n \log \log n)\)

原理是质数的倍数一定不是倍数，用于快速求特定范围n以内的质数个数，思路如下：

  • 从2开始枚举，标记每个未被标记的数的倍数为合数
  • 遍历到m(m为使得m*m>=n成立的最小值）即可，此时未被标记的数就是1-n范围内的质数。

因为每个被遍历到的未被标记数一定是质数，因此不用再单独判断该数是否为合数。

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
vector<int> countPrimes(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    isPrime[0] = isPrime[1] = false; // 0 和 1 不是质数

    for (int i = 2; i * i <= n; i++) { // 优化二：只需枚举到 sqrt(n)
        if (isPrime[i]) {
            // 优化一：从 i*i 开始标记
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 收集所有质数
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) primes.push_back(i);
    }
    return primes;
}

欧拉筛

和埃氏筛相同，欧拉筛的核心在于一个数的任意整数倍数一定是合数，而欧拉筛减少了对于同一个合数的重复计算（如，埃氏筛中会对16筛两次：28和44），其思路如下：

  • 从2开始遍历，如果当前数在合数数组中为false，就计入质数数组；
  • 用当前数去乘质数数组中的每一个数，并将结果分别标记为合数；
  • 特别的，如果当前数是某一个质数的倍数，就跳出乘算。

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
vector<int> getPrimes(int n) {
    vector<int> primes;    //质数表
    vector<bool> is_prime(n + 1, true);    // is_prime[i]表示i是否是质数
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i); // 找到质数
        }
        // 遍历已知质数表
        for (int p : primes) {
            if (i * p > n) break; // 越界退出         
            is_prime[i * p] = false; // 用当前数字 * 质数 标记合数            
            if (i % p == 0) break; //如果当前数是某个质数的倍数则直接退出，因为它的倍数一定已经被这个质数标记过了
        }
    }
    return primes;
}

线段覆盖

最少线段覆盖目标区间 \([L, R]\)

问题：给定 \(N\) 条线段，从中选出最少的线段，使得它们的并集能完全覆盖指定的区间 \([L, R]\)。

  • 贪心策略：按左端点（Start）从小到大排序。
  • 核心逻辑：
    1. 在所有能覆盖当前左边界 start 的线段中，选择右端点最远的那条。
    2. 更新左边界为该线段的右端点，重复直到覆盖目标。

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) {
    return a.start < b.start; // 按起点升序
});

int res = 0, i = 0, cur_right = L; 
while (cur_right < R) {
    int max_reach = -1e9;
    // 在所有起点 <= 当前边界的线段中，找跑得最远的
    while (i < n && intervals[i].start <= cur_right) {
        max_reach = max(max_reach, intervals[i].end);
        i++;
    }
    if (max_reach <= cur_right) return -1; // 断层了，无法覆盖
    res++;
    cur_right = max_reach; // 更新覆盖进度
}

最大不相交线段数量

问题：给定 \(N\) 条线段，选择尽可能多的线段，使得它们互不重叠。

  • 贪心策略：按右端点（End）从小到大排序。
  • 核心逻辑：
    1. 优先选择结束最早的线段，这样能给后面留出尽可能多的空间。
    2. 每次选择一条线段后，下一条线段的起点必须 \(\ge\) 当前已选线段的终点。

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) {
    return a.end < b.end; // 按结束位置升序
});

int count = 0, last_end = -1e9;
for (auto &seg : intervals) {
    if (seg.start >= last_end) { // 如果起点不重叠
        count++;
        last_end = seg.end;    // 更新边界
    }
}

前缀和/差分

需要尤其注意边界检查。

等差数列一维差分

已知数组arr，对其进行\(k\)次操作，每次操作选取左右两个端点，给定一个相同长度的等差数列[s,e,d]表示数列首尾和公差，一一对应加在选取的区间上，求多次操作后的结果。

本质上是两次一维差分，和一维差分相同，不支持边查边改；在每次操作的预处理中和一维差分有所区别，执行以下四步：

  • arr[l]+=s
  • arr[l+1]+=d-s
  • arr[r+1]-=d+e
  • arr[r+2]+=e

二维差分

在遇到二维矩阵+区域覆盖时考虑二维差分，总体思路是对数据进行预处理后进行二维前缀和，得到的就是每个元素的变化值。

给定矩阵\(matrix\)，进行\(k\)次操作，每次操作对以\([lx,ly]\)和 \([rx,ry]\)分别为左上顶点和右下顶点的矩形区域中的每个值加\(v\)，则进行以下预处理：

  • pre[lx][ly]+=v
  • pre[lx][ry+1]-=v
  • pre[rx+1][ly]-=v
  • pre[rx+1][ry+1]+=v

二维前缀和

预处理时每个节点记录以[0,0]为左上角、该节点为右下角的矩阵的总和；对于每个元素[x,y]，其值为matrix[x][y]+pre[x-1][y]+pre[x][y-1]-pre[x-1][y-1]，需要额外注意边界的情况。

离散化

深度搜索优先

栈实现/递归实现

对于计算岛屿最大面积这类，如果使用递归实现，需要把表示当前陆地总面积的变量放在全局，否则被回退的路径的面积会被忽略。

矩阵水流问题
水从高处向低处流，检查每一个点位中的水能否抵达边界。
思路为反向思考，从边界出发标记可以抵达的点，最后检查所有点能否被边界抵达。

广度搜索优先

主要依赖队列实现，使用队列存储待处理的点，每处理一个点就弹出该点，并将与该点相邻且未访问的点压入队列尾部。应在压入队列时就标记访问，预防反复入队。

模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//遍历地图
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            if(map[x][y].island==0)continue;
            if(map[x][y].isvist)continue;

            //发现wei'fang
            //注意入队后及时标记访问
            sum++;
            map[x][y].isvist=true;
            curr.push({x,y});
            while(!curr.empty()){
                    pair<int,int> currP=curr.front();
                    curr.pop();
                for(int i=0;i<4;i++){
                    int a=currP.first+dx[i];
                    int b=currP.second+dy[i];
                    if(a>n||a<1||b>m||b<1)continue;
                    if(map[a][b].isvist)continue;
                    if(map[a][b].island==0)continue;

                    curr.push({a,b});
                    map[a][b].isvist=true;
                }
            }
        }
    }

双层bfs

用于需要计步且不带边权的最短路，使用嵌套whle循环层序遍历，在每一层开始用que.size()统计当前层的元素数量，并在内层while循环结束后增加计数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
que.push(0);
    isVis[0] = true;
    while (!que.empty()) {
        int sz = que.size();
        while (sz--) {
            int currU = que.front();
            que.pop();

            //此处处理搜索逻辑

            //将当前节点未被访问的出边压入队列
            for (int i : map[currU]) {
                if (isVis[i])continue;
                que.push(i);
                isVis[i] = true;
            }
        }
        res++;
    }

单源多终点最短路

带计数的单源最短路，在双层BFS的基础上将访问标记数组更换为一个记录最短步数的数组，初始化为-1表示没有访问。

需要注意起点的步数始终为0。

多源最短路

转换思路为从单个点逐一搜索转换为多个起点直接放进初始队列同时搜索。

单词接龙

根据单词人为构造图后bfs即可。

Dijkstra

适用于非负权单源最短路，局部贪心，每次更新所有已记录的点中距离源点最短的未访问点。dj的访问顺序并非路径顺序，最终从终点开始反向访问pre数组得到的才是路径。

通过dist和pre数组分别记录点到源点的最短距离、每个思安的前驱节点。思路：

  1. 初始化。

    初始化dist数组为极大值INF，表示源点到节点i的最小距离；
    初始化pre数组为-1，值表示在最短路中节点i的前一个节点；
    向优先队列中压入起点，通常是节点1。

  2. 遍历

    • 查优先队列中的最近点并弹出，如果已访问或总距离比dist中记录的最小距离大，跳过；否则标记访问，并检查该最近点相邻的所有点，更新dist和pre数组

  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
//小根堆 两个参数分别为目标点、和源点的距离
priority_queue<pair<int, int>, vector<pair<int, int>>, compare>
        pq; 
//访问标记
bool flag[105];
//和源点的总距离，前驱节点
int dist[105], pre[105];
//灵界表，两个参数分别为终点、两点间的距离
vector<pair<int, int>> graph[105]; 


// dijkstra
        while (!pq.empty()) {
            pair<int, int> curr = pq.top();
            pq.pop();

            //边界检查
            //如果当前节点已访问，跳过
            if (flag[curr.first])
                continue;
            //如果当前节点的距离为INF，则该节点距离没有更新过，跳过
            if (curr.second == INF)
                continue; 
            //如果已记录的距离小于当前读到的距离，则当前不是一个有效节点，跳过
            if (dist[curr.first] < curr.second)
                continue;
            flag[curr.first] = true;

            for (auto point : graph[curr.first]) {
                if (flag[point.first])
                    continue;

                //更新距离、前驱节点和优先队列
                if (curr.second + point.second < dist[point.first]) {
                    dist[point.first] = curr.second + point.second;
                    pre[point.first] = curr.first;
                    pq.push({point.first, dist[point.first]});
                }
            }
        }

最小生成树-Prim

生成树是保留原图所有点的有向无环连通图。

Prim适用于稠密图，通过选择最近点增加以构建树，即循环选择距离当前树最近且不在树中的点加入树。

  1. 初始化和建图。

    初始化所有dist为INF，dist记录点和树的最近距离。

    选择或确定生成树的第一个元素，将dist中对应的元素置为0，在isvis中标记为已访问。

  2. 循环

    取出优先队列队首并弹出，检查是否访问，如已访问则continue。

    标记当前点为已访问，更新总边权

    遍历当前点所有的相邻点，每个点若已访问或权值大于dist中的值则continue，否则更新dist并将该点压入优先队列。

  3. 其它逻辑处理和输出。

注意事项

  1. 注意所有涉及first和second有没有写反
  2. 遍历相邻点的时候不要把point写成curr。
  3. 定义graph的时候不要漏了数组的方括号。

示例代码

 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
const int MAX=1e3+5;
const int INF=0x3f3f3f3f;
int n,m,u,v,c,res;
vector<pair<int,int>> graph[MAX];   //target,dist
int dist[MAX];
bool isvis[MAX];
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;

int main(){
    //...接收数据...

     //初始化pq，dist；
    for(int i=1;i<=n;i++)dist[i]=INF;
    dist[1]=0;
    pq.push(make_pair(1,0));

    //prim
    while(!pq.empty()){
        //取出队首，标记，更新相邻点到树的距离
        pair<int,int> curr=pq.top();
        pq.pop();
        if(isvis[curr.first])continue;
        isvis[curr.first]=true;
        res=max(res,curr.second);

        for(auto point:graph[curr.first]){
            if(isvis[point.first])continue;
            if(dist[point.first]<=point.second)continue;
            dist[point.first]=point.second;
            pq.push(point);
        }
    }

    //...其他逻辑...
}

最小生成树-Kruskal

Kruskal适用于稀疏图，尤其适用于无法确认图是否能够完全连通和需要输出子生成树数量时。Kruskal通过依次加入最小边以得到最小生成树。

注意一些预处理逻辑，如边少于点一定无法形成生成子树。

  1. 输入和初始化

    接收边并直接存入优先队列；无向图不需要存两次。

    初始化并查集，每个点的父元素指向自身；如需记录以当前节点为根元素的节点数量，将节点数量初始化为1（如果记录边数则为0

  2. 循环，直到队空或满足其它题目的限制

    取出优先队列队首并弹出，并查集检查两个点是否已在同一棵树中，若已在则continue

    若不在则合并两树，累加边权或进行其它处理

  3. 其它逻辑处理和输出

示例代码

带子树数量计数，如果不需要则parent和edge各少一个参数。

 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
    struct Edge{
        int u;
        int v;
        ll dist;
    };

    struct compare{
        bool operator()(Edge a,Edge b){
            return a.dist>b.dist;
        }
    };

    const int MAX=1e4+5;
    const int P=1e3+5;
    int n,m ,k,x,y,l,num,maxEdges=-1;
    ll w;
    priority_queue<Edge,vector<Edge>,compare> pq;
    pair<int,int> parent[P];    //point,num

    int find(int x){
        if(parent[x].first!=x)parent[x].first=find(parent[x].first); 
        return parent[x].first;
    }

    void unite(int x,int y){
        int rootx=find(x);
        int rooty=find(y);
        if(rootx!=rooty){
            parent[rooty].first=rootx;
            parent[rootx].second+=parent[rooty].second;
            maxEdges=max(maxEdges,parent[rootx].second);
        }
    }
        bool query(int x,int y){
        int rootx=find(x);
        int rooty=find(y);
        return rootx==rooty;
    }

    int main(){
        cin>>n>>m>>k;
        for(int i=0;i<m;i++){
            cin>>x>>y>>l;
            pq.push({x,y,l});
        }

        if(n<k){
            cout<<"No Answer";
            return 0;
        }
        if(num==k){
            cout<<"0";
            return 0;
        }

        //init
        for(int i=1;i<=n;i++){
            parent[i].first=i;
            parent[i].second=1;
        }

        num=n;
        while(!pq.empty()&&num!=k){
            Edge edge=pq.top();
            pq.pop();
            if(!query(edge.u,edge.v)){
                num--;
                unite(edge.u,edge.v);
                w+=edge.dist;
            }
        }

        if(num==k)cout<<w;
        else cout<<"No Answer";  

        return 0;
    }

拓扑排序-Kahn

拓扑排序（Topological sorting）解决的问题是对有向无环图的所有的节点排序，要求任意两个存在依赖关系的节点，被依赖的节点都必须在另一个节点前面。
拓扑排序的顺序并不唯一，除了排序也可以用于判断有向图中是否存在环。

通常使用Kahn算法解决，其核心在于入度为0的节点就一定没有被依赖。

  1. 建图，同时记录每个节点入度。

  2. 遍历每个节点的入度，将入度为0的节点全部入队。

  3. 取出队头，遍历它的所有出边，将出边终点的入度-1，并放进结果数组

    • 如果某个终点的入度减至0，则入队。

  4. 检查是否所有节点都放入了结果数组

    如果全部放入，则该数组的顺序就是其中一种拓扑排序

    如果没有，则该图中存在环或不连通。

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//拓扑排序
//建图，int du[]存入度
//初始化后遍历入度，把入度为0的点全部压进队列
//问队列top的出度，存top并将所有top出度节点的入度-1，如果某个节点减到0了也压进队列，直到队列空
//统计已经问过的点，没问完就不能拓扑排序，问完了则输出

//统计：开等同点数的数组，初始化为-1，问完以后检查最后一个点是否是-1。

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> du(numCourses,0);
        vector<vector<int>> graph(numCourses);
        queue<int> que;
        vector<int> res(numCourses,-1);

        //建图
        for(auto point:prerequisites){
            graph[point[1]].push_back(point[0]);
            du[point[0]]+=1;
        }

        //初始化
        if(!que.empty())que.pop();
        for(int i=0;i<numCourses;i++){
            if(du[i]==0)que.push(i);
        }

        //轮询
        int idx=0;
        while(!que.empty()){
            int curr=que.front();
            res[idx++]=curr;
            que.pop();

            for(auto i:graph[curr]){
                du[i]-=1;
                if(du[i]==0)que.push(i);
            }
        }

        //输出
        if(res[numCourses-1]==-1)return vector<int>();
        else return res;
    }

并查集

并查集如其名，使用一个集合（数组）来完成合并和查询的操作，用于判断两个元素是否在同一个集合中。

  • 合并（Unite）：合并两个集合所属的集合，将一个根节点指向另一个根节点。
  • 查询（Find）：查询某个元素所属的集合或根节点。

并查集支持删除单个元素、移动或维护树上的边权，但不能以较低复杂度实现集合的分离。

注意在方法命名上不能使用union，这个是联合体的关键字。

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
//初始化
int parents[size_t];
for(int i=0;i<parents.size();i++){
    parents[i]=i;
}

//带路径压缩的查询
int find(int x){
    //x为需要查询的节点
    if(parents[x]!=x)parents[x]=find(parents[x]);
    return parents[x]
}

冗余连接

无向图

当两个节点已经有同一个根节点时，再连接这两条边就会形成环。
因此使用并查集，边输入边查，如果当前边的两个端点的根节点不同就合并，如果相同则当前边就是所需冗余边。

有向图

观察图可得，对于具有冗余边的有向树，会出现以下两种情况：

image-20260309185505527

因此，我们可以在录入数据的同时记录入度。
即，使用vector<pair<int,int>> edges按顺序记录边，并开一个整型数组记录每个节点的入度。

读入数据后，根据是否存在入度为2的节点进行不同的判断。
对于入度均为1的有向环图，只要删掉其中一条即可，思路和无向图相同，并查集查找并删除即可；
对于存在入度为2的节点的图，可能存在只能删除特定边的情况，因此首先需要先遍历边数组，找出指向该节点的两条边，假设删除第二条边，用并查集检查删除后是否能形成有向树。如果能则第二条边就是答案，否则就是第一条边。

链表合并

并查集记录，以单个点表示当前已经融合的连续段（这里用最左点表示，即合并的时候以左段为父节点），同时更新记录。即，每次合并有以下三步：

  • 合并并查集
  • 更新当前段最左节点和最右节点
  • 合并链表

由于并查集只能记录集合，而无法记录集合间元素的顺序，因此需要一个额外的链表来记录点的顺序。
此处用数组模拟，值为当前节点的下一个节点。

线段树

组织

线段树的sum数组在组织时，假定其结构为满二叉树来开空间。
若数据范围为\(1-n\)，则二叉树的层高最大为\(\log_{2}{n}+2\)，节点总数为\((n^{\log_{2}{n}+2})-1\),即\(4n-1\)。

对于一个任意的大范围[l,r]，若将它的信息放在数组中索引为i的元素中，则其子节点按左右范围拆分为[l,mid]和[mid+1,r]，其中左范围信息在数组中的索引为2*i，右范围为2*i+1。

查询

时间复杂度为\(\log_{}{n}\)。

更新

支持增减、重置、和范围改变为指定值

单开一个add数组记录每个值的变化，原则是懒更新，即记录每次更新，直到必须将更新作用到原信息上时才根据add数组执行更新。
其核心思路是如果当前范围全部会被更新，则将更新的内容存在当前范围中。

如果题目中存在范围改变为指定值的操作，为了区分当前懒更新中记录的值是变化值还是重置的指定值，需要额外单开一个isCover[4n+5]数组进行标记。

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
//线段树模板题。已知一个数列，你需要进行下面两种操作：将某区间每一个数加上 k，求出某区间每一个数的和。
//第一行包含两个整数 n,m (5≤n,m≤1e5),分别表示该数列数字的个数和操作的总个数；
//第二行包含 n个用空格分隔的整数 (0−1e9)，其中第 i 个数字表示数列第 i 项的初始值；
//接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下:
//1 x y k：将区间 [x, y] 内每个数加上 k。
//2 x y：输出区间 [x, y]内的数的和。
#include<iostream> 
#define ll long long
using namespace std;

const int MAX = 1e5 + 5;
ll n, m, k, sign, x, y;
bool isFirst = true;
ll sum[4 * MAX], change[4 * MAX];
ll num[MAX];

void build(ll l, ll r, ll idx) {
    if (l == r) {
        sum[idx] = num[l];
        return;
    }

    ll mid = (l + r) / 2;
    build(l, mid, idx << 1);
    build(mid + 1, r, idx << 1 | 1);
    sum[idx] = sum[idx << 1] + sum[idx << 1 | 1];
}

void lazyUpdate(ll l, ll r, ll idx) {
    if (change[idx] == 0)return;
    ll mid = (l + r) / 2;

    change[idx << 1] += change[idx];
    sum[idx << 1] += (mid - l + 1) * change[idx];
    change[idx << 1 | 1] += change[idx];
    sum[idx << 1 | 1] += (r - mid ) * change[idx];

    change[idx] = 0;
}

void update(ll targetL, ll targetR, ll l, ll r, ll idx) {
    if (targetL<=l && targetR>=r) {
        change[idx] += k;
        sum[idx] += (r - l + 1) * k;
        return;
    }

    //向下一层执行更新
    lazyUpdate(l, r, idx);
    ll mid = (l + r) / 2;
    if (targetL <= mid)update(targetL, targetR, l, mid, idx << 1);
    if (targetR > mid)update(targetL, targetR, mid + 1, r, idx << 1 | 1);
    sum[idx] = sum[idx << 1] + sum[idx << 1 | 1];
}

long long res(ll targetL, ll targetR, ll l, ll r, ll idx) {
    if (targetL <= l && r <= targetR)return sum[idx];
    else {
        lazyUpdate(l, r, idx);
        long long ans = 0;
        ll mid = (l + r) / 2;
        if (targetL <= mid)ans += res(targetL, targetR, l, mid, idx << 1);
        if (targetR > mid)ans += res(targetL, targetR, mid + 1, r, idx << 1 | 1);
        return ans;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }

    //建树
    build(1, n, 1);

    //轮询
    for (int i = 1; i <= m;i++) {
        cin >> sign;
        if (sign == 1) {
            cin >> x >> y >> k;
            update(x, y, 1, n, 1);
        }
        else {
            cin >> x >> y;            
            if (isFirst)isFirst = false;
            else cout << '\n';
            cout<< res(x, y, 1, n, 1);
        }
    }

    return 0;
}

01背包

给定一组物品，每种物品有重量 \(w_i\) 和价值 \(v_i\)，在限定的总容量 \(W\) 内，如何选择物品使得总价值最大。

0/1之意在于每个物品只有一个，状态包括选或不选。

进行递归时需要考虑的问题：

1
2
3
4
5
6
1. 如果当前物品个数越界（超过物品总数），返回0：`if (n > num)return 0`
2. 如果当前物品与剩余容积已被计算过，返回记录值：`if (rem[n][vol])return rem[n][vol]`
3. 如果当前物品体积超过背包剩余容积，跳过当前物品，继续遍历：`dfs(n+1,vol)`
4. 如果当前物品体积小于或等于背包剩余体积，返回不选当前物品和选当前物品分别继续遍历后的最大值：`max(dfs（n+1，vol）,dfs(n+1,vol-v[n])+w[n]）`

注意：情况3和4都应该记录sum值，并存入记忆容器。

定义状态数组\(dp[i][j]\) 表示前 \(i\) 件物品放入容量为 \(j\) 的背包能获得的最大价值，状态转移方程如下：

\[dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])\]

其中，dp[i-1][j]表示不选第 \(i\) 件，dp[i-1][j-w[i]] + v[i]表示选第 \(i\) 件（前提是剩余空间够放）。

由状态转移公式dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])易得：每次进行递归时，\(dp[i][j]\)只与\(dp[i-1][x]\)（x为占位符）相关，因此可使用两个数组f[N]和g[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
#include<iostream>
using namespace std;

const int N = 105;

int maxT, maxN;
int dp[1005] = { 0 };
//t：费用 v价值
int t[N] = { 0 }, v[N] = { 0 };


int main() {
    cin >> maxT >> maxN;
    for (int i = 1;i <= maxN;i++) {
        cin >> t[i] >> v[i];
    }

    for (int i = 1;i <= maxN;i++) {
        //j>t[i]：当前背包的容量
        for (int j = maxT;j >= t[i];j--) {
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
        }
    }
    cout << dp[maxT];
    return 0;
}

完全背包

每种物品可以取无限次。

  • 转移方程：

    与 0/1 背包非常相似，唯一的区别在于选第 \(i\) 件物品时，是从当前这一层状态转移过来的：

    \[dp[i][j] = \max(dp[i-1][j], dp[i][j-w[i]] + v[i])\]

  • 优化思路：

    同样使用一维数组 dp[j]。注意：容量 \(j\) 必须从小到大（正序）遍历。

    原因：正序遍历意味着当你计算 \(dp[j]\) 时，所需的 \(dp[j-w[i]]\) 已经是本轮更新过后的值了，正好符合“物品可以多次放入”的逻辑。

示例代码

1
2
3
4
5
6
// n: 物品数量, W: 背包总容量
for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= W; j++) { // 正序遍历：允许同一件物品被多次放入
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

多重背包

每种物品不是 1 个也不是无限个，而是 \(s_i\) 个。

  • 朴素思路：

    在 0/1 背包的基础上加一层循环，遍历该物品放几个（\(0\) 到 \(s_i\)）。

  • 二进制分组优化：

    原理是任意一个整数 P，都可以表示成若干个 2 的幂次之和 ，而使用这种拆分能在保证dp结果相同时降低时间复杂度。

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int t, maxW;     //宝石的种数和最大容积
int value, wight, num;    //单个价值，单个质量，总数目
int v[N] = { 0 }, w[N] = { 0 };     //价值数组，质量数组
int n = 1;        //二进制分堆计数器
int dp[40005] = { 0 };

int main() {
    cin >> t >> maxW;
    for (int i = 1;i <= t;i++) {
        cin >> value >> wight >> num;

        //二进制分组
        for (int k = 1;k <= num;k <<= 1) {
            v[n] = value * k;
            w[n] = wight * k;
            num -= k;
            n++;
        }
        //最后剩下进不了2的n次方堆的部分
        if (num != 0) {
            v[n] = value * num;
            w[n] = wight * num;
            n++;
        }
    }

    //0/1背包
    for(int i=1;i<=n;i++){
        for (int j = maxW;j > 0;j--) {
            if (j - w[i] < 0)continue;
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

混合背包

有的物品只能用 1 次，有的能用无限次，有的能用 \(s\) 次。

其通用思路为：

  • 将多重背包转换为复数个使用二进制分组优化的01背包
  • 单开状态数组记录每个物品为01背包（包括多重背包转换为的01背包）和完全背包
  • 进入正常背包问题的dp[i]外层循环
  • 根据状态数组决定进入的内层循环是01背包的倒序还是完全背包的顺序
  • 输出dp[t](t为最大时间)

注意：01背包和完全背包的内层for遍历顺序不同，如果采用01背包的两个dp数组回滚会导致完全背包的部分在计算时出错，因此对于这类问题应该只用一个dp数组，所有操作都在原来的数组上修改。

for循环嵌套：01背包中两层for循环判断的本质是是否将第i个物品放入最大容量为j的背包中。

dp[j-w[i]]+w[i]：状态转移方程中的这一部分是选择当前物品时的最大价值。

如果要在容量为j的背包中装下当前物品，那么可以剩下的能装物品的最大容积就是j-w[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
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
#include<iostream>
#include<cstring>
using namespace std;

const int N = 70005;
int h1=0, m1=0, h2=0, m2 = 0;
char _a;    //滤掉时间输入时的字符
int t;       //时间
int tree;    //树的数目
int n=1;       //分堆用的计数器；
int cost, value, num;     //耗费时间，美学价值，可看次数
int c[N] = { 0 }, v[N] = { 0 };     // 二进制分堆后的耗费时间和美学价值；
bool state[70005] = { false };      //ture：01背包；false：完全背包

int dp[1005] = { 0 };      //dp


int main(){
    cin >> h1 >> _a >> m1;
    cin >> h2 >> _a >> m2;
    cin >> tree;
    t = 60 * (h2 - h1) + (m2 - m1);     //最大时间

    for (int x = 1;x <= tree ; x++) {
        cin >> cost >> value >> num;
        //类型标记、分堆处理
        if (num == 0) {
            c[n] = cost;
            v[n] = value;
            state[n] = false;
            n++;
        }
        else {
            for (int i = 1;i <= num;i<<=1) {
                c[n] = cost * i;
                v[n] = value * i;
                state[n] = true; // 01背包
                num -= i;
                n++;
            }
            if (num!=0) {
                c[n] = cost * num;
                v[n] = value * num;
                state[n] = true;
                n++;
            }
        }


    }
    for (int i = 1;i < n;i++) {
            //01背包
        if (state[i]) {
            for (int j = t;j >= 1;j--) {
                if (c[i] > j)continue;
                dp[j] = max(dp[j], dp[j - c[i]] + v[i]);
            }
        }
        //完全背包
        else {
            for (int j = 1;j <=t;j++) {
                if (c[i] > j)continue;
                dp[j] = max(dp[j], dp[j - c[i]] + v[i]);
            }
        }
    }
    cout<<dp[t];

    return 0;
}

字符串匹配-KMP

其核心在于检查子串时如果不匹配不会返回当前串开始处全部重新检查，而是跳过能跳过的部分，以避免重新匹配。

通过

主要分为两步：构建模式串的前缀数组和扫描字符串，时间复杂度为O（m+n)，其中m为模式串p的长度，n为需要扫描的字符串s的长度。

示例代码

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

using namespace std;

// 1. 构建 next 数组 (前缀表)
void getNext(int* next, const string& s) {
    int j = 0; 
    next[0] = 0;
    for (int i = 1; i < s.size(); i++) { 
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j;
    }
}

// 2. KMP 匹配过程
int strStr(string haystack, string needle) {
    if (needle.empty()) return 0;
    int n = haystack.size(), m = needle.size();
    vector<int> next(m);
    getNext(&next[0], needle);

    int j = 0; // 模式串指针
    for (int i = 0; i < n; i++) { // 文本串指针
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1]; // 失配时，j 根据 next 数组回跳
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == m) { // 匹配完全部长度
            return i - m + 1; // 返回起始索引
        }
    }
    return -1;
}

int main() {
    string text = "AABAACAADAABAAAB";
    string pattern = "AABAAB";
    int index = strStr(text, pattern);
    cout << "Pattern found at index: " << index << endl;
    return 0;
}

排错

  1. long long：using ll=long long
  2. 强制类型转换
  3. 声明数组时的范围，常量定义的范围
  4. 容器初始化
  5. 循环的边界检查，循环嵌套的ij有没有写串