首页 书籍 挑战程序设计竞赛

# 暴力搜索

# 递归

在一个函数中再次调用该函数的这种行为叫做递归，这样的函数被称为递归函数。

递归通常包括两个部分：基本情况和递归情况。基本情况是递归函数停止调用自身的条件，而递归情况则是函数继续调用自身的条件。

# 斐波那契数列

斐波那契数列中的每一项都是前两项的和，斐波那契数列可以用递归的方式来定义：F (0) = 0, F (1) = 1, F (n) = F (n-1) + F (n-2)（n ≥ 2）。

#define MAXN_N 100
int memo[MAXN_N + 1];
int fib(int n){
    if(n <= 1) return n;
    if(memo[n] != 0) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

# 栈

#include <iostream>
#include <stack>
int main() {
    std::stack<int> myStack;
    // 将元素压入栈
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);
    // 访问栈顶元素
    std::cout << "Top element: " << myStack.top() << std::endl;
    // 弹出栈顶元素
    myStack.pop();
    // 再次访问栈顶元素
    std::cout << "Top element after pop: " << myStack.top() << std::endl;
    // 检查栈是否为空
    if (myStack.empty()) {
        std::cout << "Stack is empty." << std::endl;
    } else {
        std::cout << "Stack is not empty." << std::endl;
    }
    return 0;
}
# 队列


#include <iostream>
#include <queue>
int main() {
    std::queue<int> myQueue;
    // 将元素加入队列
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);
    // 访问队列的第一个元素
    std::cout << "Front element: " << myQueue.front() << std::endl;
    // 访问队列的最后一个元素
    std::cout << "Back element: " << myQueue.back() << std::endl;
    // 弹出队列的第一个元素
    myQueue.pop();
    // 再次访问队列的第一个元素
    std::cout << "Front element after pop: " << myQueue.front() << std::endl;
    // 检查队列是否为空
    if (myQueue.empty()) {
        std::cout << "Queue is empty." << std::endl;
    } else {
        std::cout << "Queue is not empty." << std::endl;
    }
    // 获取队列的大小
    std::cout << "Queue size: " << myQueue.size() << std::endl;
    return 0;
}
# 深度优先搜索


深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。在深度优先搜索中，从起始顶点开始，沿着一个路径尽可能深地遍历直到末端，然后回溯到前一个节点，继续探索下一个路径，直到所有节点都被访问过为止。


下面是深度优先搜索的基本原理和步骤：


    

  1. 选择一个起始顶点作为搜索的起点，并将其标记为已访问。
    2. 

  2. 从起始顶点开始，选择一个相邻且未被访问过的顶点进行访问，并将其标记为已访问。
    3. 

  3. 重复上述过程，直到当前路径上的所有顶点都被访问过。
    4. 

  4. 如果当前路径上的所有顶点都已被访问过，则回退到上一个顶点，继续选择未被访问过的相邻顶点进行探索。
    5. 

  5. 重复步骤 2 和步骤 4，直到所有顶点都被访问过。
    6. 



深度优先搜索通常使用递归的方式实现，也可以使用栈来辅助实现。在搜索过程中，需要考虑避免重复访问已经访问过的顶点，以防止陷入无限循环。


深度优先搜索适用于解决许多问题，例如查找图中的路径、判断图是否连通、拓扑排序等。在实际应用中，深度优先搜索常常与其他算法结合使用，例如深度优先搜索 + 回溯算法，在解决各种问题时发挥重要作用。


# 部分和问题






#include <iostream>
#define MAXN_N 1000
int a[MAXN_N];
int n,k;
// 已经从前 i 项得到了和 sum，然后对于 i 项之后的进行分支
bool dfs(int i,int sum){
    // 如果前 n 项都计算过了，则返回 sum 是否与 k 相等
    if(i == n) return sum == k;
    // 不加上 a【i】的情况
    if(dfs(i + 1,sum)) return true;
    // 加上 a【i】的情况
    if(dfs(i + 1,sum + a[i])) return true;
    // 凑不成 k
    return false;
}
void solve(){
    if(dfs(0,0)) printf("Yes\n");
    else printf("No\n");
}
# LakingCounting




思路：


    

  1. 遍历园子中的每个位置：从园子的左上角开始，依次遍历每行每列的位置。
    2. 

  2. 寻找水域：当遍历到一个水域（用字符 'W' 表示）时，以该位置为起点进行深度优先搜索。
    3. 

  3. 深度优先搜索（DFS）：从当前水域的位置出发，向上下左右和斜对角线八个方向进行搜索。对于每个相邻且未被访问过的水域，继续进行深度优先搜索，直到搜索完当前水域所连接的所有水域。
    4. 

  4. 计数：每当完成一次深度优先搜索，即找到了一个水洼，对水洼的数量加一。
    5. 

  5. 重复步骤 2-4：继续遍历园子的每个位置，直到所有位置都被访问过为止。
    6. 

  6. 输出结果：输出水洼的总数量。
    7. 



#include <iostream>
int N,M;
char field[105][105];// 园子
// 当前位置 (x,y)
void dfs(int x,int y){
    // 将当前位置替换为.
    field[x][y] = '.';
    // 循环遍历移动八个方向
    for(int dx = -1; dx <= 1; dx++){
        for(int dy = -1; dy <= 1; dy++){
            int nx = x + dx, ny = y + dy;
            // 判断（nx，ny) 是否在园子里，以及是否有积水
            if(0 <= nx && nx < N && 0 < ny && ny < M && field[nx][ny] == 'W') dfs(nx,ny);
        }
    }
    return ;
}
void solve() {
    int res = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(field[i][j] == 'W'){
                // 从有 W 的地方开始 dfs
                dfs(i,j);
                res++;
            }
        }
    }
    printf("%d\n",res);
}
# 广度优先搜索


广度优先搜索（BFS）是一种用于遍历或搜索图形或树的算法。它从给定的起始节点开始，逐层地向外扩展，直到达到目标节点或遍历完整个图形。BFS 通常使用队列来实现。


下面是广度优先搜索的基本步骤：


    

  1. 初始化：将起始节点放入队列中，并标记为已访问。
    2. 

  2. 循环：从队列中取出一个节点，访问该节点，并将其未访问过的相邻节点加入队列。
    3. 

  3. 标记已访问：将已加入队列的节点标记为已访问，以避免重复访问。
    4. 

  4. 重复步骤 2 和步骤 3，直到队列为空或者找到目标节点。
    5. 



广度优先搜索的特点是按照层次进行遍历，先访问离起始节点最近的节点，然后逐渐扩展到离起始节点更远的节点。这样可以确保在搜索过程中找到的节点是按照距离起始节点的顺序排列的，从而可以用于计算最短路径或解决其他与距离相关的问题。


广度优先搜索常用于解决以下问题：


    

  • 从起点到目标点的最短路径问题
    • 

  • 连通性问题，如判断图形中是否存在路径连接两个节点
    • 

  • 图形遍历，访问图形中的每个节点
    • 



# 迷宫最短路径




输出：22


思路：


    

  1. 首先定义了一个迷宫的二维字符数组  maze ，表示迷宫的布局； N  和  M  分别表示迷宫的行数和列数； sx, sy  表示起点坐标； gx, gy  表示终点坐标。
    2. 

  2. 使用队列  que  存储待探索的位置，将起点坐标加入队列，并将起点的到达距离设为 0。
    3. 

  3. 不断循环直到队列为空，每次从队列中取出一个位置进行探索。如果当前位置是终点，则结束搜索。
    4. 

  4. 针对当前位置，向四个方向进行探索，计算移动后的新位置  (nx, ny) 。如果新位置在迷宫范围内，并且是可以通行的地点且未访问过，则将新位置加入队列，更新到达该位置的距离。
    5. 

  5. 最终返回终点位置  (gx, gy)  的到达距离，即为起点到终点的最短路径长度。
    6. 



#include <bits/stdc++.h>
#include <utility>// 包含 pair 的定义
using namespace std;
const int INF = 100000000;
typedef pair<int,int> P;
// 输入
char maze[105][105];// 迷宫字符串
int N, M;
int sx,sy; // 起点坐标
int gx,gy; // 终点坐标
int d[105][105];// 到各个位置的最短距离的数组
//4 个方向的移动向量
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
// 求从（sx，sy）到（gx，gy）的最短距离
// 如果无法到大，则是 INF
int bfs(){
    queue<P> que;
    // 把所有位置都初始化 INF
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++) d[i][j] = INF;
    // 将起点加入队列，并把这一地点的距离设置为 0
    que.push(P(sx,sy));
    d[sx][sy] = 0;
    // 不断循环直到队列的长度为 0
    while(que.size()){
        // 从队列的最前端取出元素
        P p = que.front(); que.pop();
        // 如果取出的状态已经是终点，则结束搜索
        if(p.first == gx && p.second == gy) break;
        // 四个方向循环
        for(int i = 0; i < 4; i++){
            // 移动之后的位置记为（nx，ny）
            int nx = p.first + dx[i],ny = p.second + dy[i];
            // 判断是否可以移动以及是否已经访问过（d [nx][ny] != INF 即为已经访问过了）
            if(0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' && d[nx][ny] ==INF){
                // 可以移动的话，则加入到队列，并且到该位置的距离确定为到 p 的距离 + 1
                que.push(P(nx,ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }
    return d[gx][gy];
}
void solve(){
    int res = bfs();
    printf("%\n",res);
}
# 剪枝


"剪枝" 是一种优化技术，用于减少搜索空间，提高搜索效率。通过剪枝，可以避免不必要的计算和搜索，从而加快算法的执行速度。剪枝通常基于一些条件或规则，当满足特定条件时，就可以提前结束当前分支的搜索。


剪枝的实现方式有很多种，常见的包括：


    

  1. 提前返回： 在搜索过程中，如果发现当前分支已经不可能达到最优解，就可以立即返回，无需继续搜索下去。
    2. 

  2. 约束条件： 根据问题的特点设定一些约束条件，当某个分支不满足约束条件时，就可以剪去该分支。
    3. 

  3. 启发式信息： 利用启发式信息（heuristic）来指导搜索，比如利用估计函数来评估当前状态的价值，从而决定搜索方向。
    4. 

  4. 动态规划： 使用动态规划技术来避免重复计算，减少搜索时间。
    5. 

  5. 排序： 对搜索节点进行排序，先搜索潜力大的节点，减少搜索空间。
    6. 



# 部分和问题


#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<int>& nums, int target, vector<int>& path, int start, vector<vector<int>>& res) {
    if (target == 0) {
        res.push_back(path);
        return;
    }
    for (int i = start; i < nums.size(); ++i) {
        if (nums[i] > target) {
            break;  // 剪枝：当前数字已经大于目标值，不可能找到解
        }
        
        path.push_back(nums[i]);
        backtrack(nums, target - nums[i], path, i + 1, res);
        path.pop_back();
    }
}
int main() {
    vector<int> nums = {2, 3, 7, 8, 10};
    int target = 10;
    vector<vector<int>> res;
    vector<int> path;
    backtrack(nums, target, path, 0, res);
    for (const auto& vec : res) {
        for (int num : vec) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}
# 贪心


贪心算法（Greedy Algorithm）是一种常用的算法思想，通常用于解决最优化问题。在每一步选择中，贪心算法会选择当前状态下的最佳选择，而不考虑未来的结果，即局部最优解希望能够导致全局最优解。


贪心算法的特点包括：


    

  1. 贪心选择性质（Greedy Choice Property）：即在每一步选择中都做出局部最优的选择，希望通过局部最优解最终达到全局最优解。
    2. 

  2. 无后效性（Optimal Substructure）：即问题的最优解包含子问题的最优解。这样，我们可以通过贪心选择构建整个问题的最优解。
    3. 



贪心算法的应用范围较广，适用于一些特定类型的问题，例如：


    

  • 找零钱问题
    • 

  • 区间覆盖问题
    • 

  • 最优任务调度问题
    • 

  • 最小生成树问题（如 Prim 算法、Kruskal 算法）
    • 



然而，贪心算法并不是万能的，它有一些局限性：


    

  • 贪心选择不能回退。一旦做出选择，就不能撤销或更改。因此，可能会错过全局最优解。
    • 

  • 需要证明贪心选择性质和无后效性。如果问题没有这两个性质，贪心算法就不一定能得到最优解。
    • 



# 硬币问题




思路：贪心策略：优先使用面值大的硬币


#include <iostream>
#include <algorithm>
using namespace std;
// 硬币的面值
const int V[6] = {1,5,10,50,100,500};
int C[6];
int A;
void solve(){
    int ans = 0;
    for(int i = 5; i >= 0; i--){
        int t = min(A / V[i], C[i]);// 使用硬币 i 的枚数
        A -= t * V[i];
        ans += t;
    }
    printf("%d\n",ans);
}
# 区间调度问题




思路：贪心策略，在可选的工作中，每次选取结束时间最早的工作


#include <bits/stdc++.h>// 万能头文件
using namespace std;
const int MAX_N = 1000000;
int N, S[MAX_N], T[MAX_N];
// 对工作排序
pair<int,int> itv[MAX_N];
void solve(){
    // 为了让结束时间早的工作排在前面，把 T 存入 first，把 S 存入 second
    for(int i = 0; i < N; i++){
        itv[i].first = T[i];
        itv[i].second = T[i];
    }
    sort(itv,itv + N);
    
    //t 是最后所选工作的结束时间
    int ans = 0, t = 0;
    for(int i = 0; i < N; i++){
        if(t < itv[i].second){
            ans++;
            t = itv[i].first;
        }
    }
    printf("%d\n",ans);
# 字典序最小问题




思路：贪心策略，不断选择 S 开头和末尾中较小的放到 T 的末尾，首尾字符相同时比较下一个字符


#include <bits/stdc++.h>
using namespace std;
// 输入
int N;
char S[205];
void solve(){
    int a = 0, b = N - 1;
    while(a <= b){
        // 左右比较
        bool left = false;
        for(int i = 0; a + i <= b; i++){
            if(S[a + i] < S[b - i]){
                left = true;
                break;
            }
            else if(S[a + i] > S[b - i]){
                left = false;
                break;
            }
        }
        if(left) putchar(S[a++]);
        else putchar(S[b--]);
    }
    putchar('\n');
}
# Saruman’s Army




思路：和村庄安装电线杆类似，从左边开始，距离最接近 R 的点就是目标点，以此类推


#include <bits/stdc++.h>
using namespace std;
int N, R;
int X[10005];
void solve(){
    sort(X,X + N);
    int i = 0, ans = 0;
    while(i < N){
        //s 是没有被覆盖的最左的点的位置
        int s = X[i++];
        // 向右找到距 s 大于 R 的点
        while(i < N && X[i] <= s + R) i++;
        //p 是新标记点
        int p = X[i - 1];
        // 向右找到距离 p 大于 R 的点
        while(i < N && X[i] <= p + R) i++;
        ans++;
    }
    printf("%d\n",ans);
}
# Fence Repair




思路：霍夫曼树，优先拿出两块小的


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, L[2005];
void solve(){
    ll ans = 0;
    // 直到计算到木板块为 1 时为止
    while(N > 1){
        int min1 = 0, min2 = 1;
        if(L[min1] > L[min2]) swap(min1,min2);
        for(int i = 2; i < N; i++){
            if(L[i] < L[min1]){
                min2 = min1;
                min1 = i;
            }
            else if(L[i] < L[min2]){
                min2 = i;
            }
        }
        //2 合一
        int t = L[min1] + L[min2];
        ans += t;
        if(min1 == N - 1) swap(min1,min2);// 如果最小长度的木板 min1 正好是数组中最后一块木板（索引为 N - 1），则交换 min1 和 min2 的位置。
        L[min1] = t;
        L[min2] = L[N - 1];
        N--;
    }
    printf("%lld\n",ans);
}
# 动态规划


动态规划（Dynamic Programming）是一种通过将原问题分解为相互重叠的子问题来求解复杂问题的方法。它通常用于优化问题，能够在问题的解空间中搜索最优解。动态规划算法通常用于解决具有重叠子问题和最优子结构性质的问题。


以下是动态规划解决问题的一般步骤：


    

  1. 确定状态：首先确定问题的状态，即描述问题局部解的变量。这些状态可以是直接给出的信息，也可以是需要计算得到的中间结果。
    2. 

  2. 确定状态转移方程：根据问题的最优子结构性质，即大问题的最优解可以由小问题的最优解推导得到，建立状态转移方程。状态转移方程描述了不同状态之间的转移关系，帮助我们从子问题的最优解推导出原问题的最优解。
    3. 

  3. 初始化边界条件：确定边界条件，即最小的子问题的解。通常需要初始化一些状态，作为后续状态转移的基础。
    4. 

  4. 通过状态转移方程计算最优解：按照状态转移方程逐步计算状态，直到计算出原问题的最优解。
    5. 

  5. 根据实际问题选择解的形式：根据具体问题的需求，确定如何表示和输出最优解。
    6. 



动态规划算法常用于解决背包问题、最长公共子序列、最短路径等问题，能够有效地优化问题的求解过程，避免重复计算，提高算法的效率。


# 记忆化搜索与动态规划


# 01 背包




思路：暴力 针对每个物品有放或者不放两种措施


#include <bits/stdc++.h>
using namespace std;
// 输入
int n, W;
int w[105], v[105];
// 从第 i 个物品开始挑选总重小于 j 的部分
int rec(int i, int j){
    int res;
    if(i == n){
        // 挑选完了
        res = 0;
    } else if(j < w[i]){
        // 无法挑选
        res = rec(i + 1, j);
    }else{
        // 挑或不挑
        res = max(rec(i + 1, j),rec(i + 1,j - w[i]) + v[i]);
    }
    return res;
}
void solve(){
    printf("%d\n",rec(0,W));
}
上述针对每一步都有挑不挑两种措施，最坏情况 o（n^2)


为了优化，可以把每一步结果保存下来


思路：记忆化搜索，复杂度 O (nW)


#include <bits/stdc++.h>
using namespace std;
int n, W;
int w[105], v[105];
int dp[105][105];// 记忆化数组
int rec(int i, int j){
    if(dp[i][j] >= 0){
        // 已经计算过
        return dp[i][j];
    }
    int res;
    if(i == n){
        res = 0;
    } else if(j < w[i]){
        res = rec(i + 1,j);
    }else{
        res = max(rec(i + 1, j),rec(i + 1,j - w[i]) + v[i]);
    }
    // 将结果记录在数组中
    return dp[i][j] = res;
}
void solve(){
    // 用 - 1 表示尚未计算过，初始化整个数组
    memset(dp,-1,sizeof(dp));
    printf("%d\n",rec(0,W));
}
memset  是 C/C++ 中的一个函数，用于将一块内存空间设置为指定的值。它通常用来初始化数组或者其他数据结构。


memset  函数的原型为：


void *memset(void *ptr, int value, size_t num);
其中：


    

  • ptr  是指向要填充的内存区域的指针。
    • 

  • value  是要设置的值，通常是一个无符号字符（ unsigned char ）。
    • 

  • num  是要设置的字节数。
    • 



memset  函数将  ptr  指向的内存区域的前  num  个字节都设置为  value  的值。该函数通常用于初始化数组为特定值、清空内存区域等操作。


例如，可以使用  memset  函数将一个整型数组初始化为 0：


int arr[5];
memset(arr, 0, sizeof(arr));
这样就会将  arr  数组中的所有元素都设置为 0。


思路：记忆化搜索的穷竭写法


#include <bits/stdc++.h>
using namespace std;
int n, W;
int w[105], v[105];
// 目前选择的物品价值总和是 sum，从第 i 个物品之后的物品中挑选重量和小于 j 的物品
int rec(int i, int j, int sum){
    int res;
    if(i == n){
        res = sum;
    }else if(j < w[i]){
        // 挑不了
        res = rec(i + 1,j,sum);
    }else{
        res = max(rec(i + 1, j, sum),rec(i + 1, j - w[i], sum + v[i]));
        
    }
    return res;
}
思路： dp[i][j]  表示在考虑前  i  个物品，背包容量为  j  时的最大总价值。 复杂度 O (nW)


#include <bits/stdc++.h>
using namespace std;
int n, W;
int w[105], v[105];
int dp[105][105];//DP 数组
void solve(){
    for(int i = n - 1; i >= 0; i--){// 从最后一个物品开始倒序遍历
        for(int j = 0; j <= W; j++){// 对于每个物品，遍历所有可能的背包容量 j，从 0 到背包总容量 W，考虑不同的背包容量对应的最大价值。
            if(j < w[i]){
                dp[i][j] = dp[i + 1][j];
            }else{
                dp[i][j] = max(dp[i + 1][j],dp[i + 1][j - w[i]] + v[i]);
            }
        }
    }
    printf("%d\n",dp[0][W]);
}
记忆化搜索（Memoization）和动态规划（Dynamic Programming）都是用于优化递归算法的技术，特别是在解决重叠子问题的情况下。


记忆化搜索是一种自顶向下的方法，通过保存已经计算过的子问题的结果（通常使用数组或哈希表进行存储），以避免重复计算相同的子问题。当需要求解一个子问题时，先检查是否已经计算过该子问题的结果，如果是，则直接返回结果，避免重复计算。


动态规划则是一种自底向上的方法，通过迭代的方式从最小的子问题开始逐步求解更大规模的问题，将中间结果保存起来，并利用已解决的子问题的结果来解决当前问题。动态规划通常需要设计合适的状态转移方程，以确保能够有效地利用之前计算过的结果来求解当前问题。


记忆化搜索和动态规划在解决问题时有一定的相似性，都可以避免重复计算，提高算法的效率。它们之间的主要区别在于解决问题的思考方式：记忆化搜索更强调从顶部向下递归求解，而动态规划则更侧重从底部向上递推求解。


# 最长公共子序列




思路：注意子序列不要求在原序列中是连续的，但是要求保持相对顺序不变。


dp[i][j]  表示序列 X 的前 i 个元素和序列 Y 的前 j 个元素的最长公共子序列的长度。


    

  • 如果 Xi == Yj，则 LCS (Xi, Yj) = 1 + LCS (Xi-1, Yj-1)
    • 

  • 如果 Xi != Yj，则 LCS (Xi, Yj) = max (LCS (Xi-1, Yj), LCS (Xi, Yj-1))
    • 



#include <bits/stdc++.h>
using namespace std;
int n,m;
char s[1005],t[1005];
int dp[1005][1005];
void solve(){
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i] == t[i]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = max(dp[i][j + 1],dp[i + 1][j]);
            }
        }
    }
    printf("%d\n",dp[n][m]);
}
# 进一步探讨递推关系


# 完全背包




思路:dp [i+1] [j] 表示从前 i 个物品中挑选总重量不超过 j 时总价值的最大值


#include <bits/stdc++.h>
using namespace std;
int n, W;
int w[105], v[105];
int dp[105][105];//DP 数组
void solve() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                // 考虑放入第 i+1 种物品和不放入第 i+1 种物品两种选择中，选择能使总价值最大化的情况
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);// 选后者相当于减掉一个物品 i 再进项考虑选不选 i
            }
        }
    }
    printf("%d\n",dp[n][W]);
}
# 滚动数组


滚动数组是一种优化动态规划空间复杂度的技巧，特别适用于状态转移方程中只涉及到上一行状态或者上一列状态的情况。在背包问题中，滚动数组可以用来减少空间复杂度，特别是对于完全背包问题和多重背包问题，这种优化能够显著减少内存使用。


在使用滚动数组的情况下，我们只需要定义一个长度为  j+1  的一维数组，表示当前物品考虑时的背包容量下所能达到的最大总价值。在状态转移时，我们根据上一行的状态值来更新当前行的状态值，从而达到节省空间的目的。


举个简单的例子，在完全背包问题中，如果我们采用滚动数组优化，状态转移方程可以被表示为：


for (int i = 0; i < n; ++i) {  // 对每种物品进行考虑
    for (int j = w[i]; j <= V; ++j) {  // 背包容量从小到大进行考虑
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // 状态转移方程
    }
}
在这段代码中， dp[j]  表示当前考虑的物品能够达到的背包容量为  j  时的最大总价值。通过滚动数组的优化，我们不再需要定义二维数组，而是只需定义一个一维数组  dp ，从而节省了大量的空间。


思路：通过一个数组来实现，用一维数组 dp 来存储背包在不同容量下所能达到的最大总价值，内层循环从当前物品的重量开始遍历到背包的总容量


// 一个数组
int dp[105];
void solve() {
    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]);// 状态转移方程，根据不同情况选择放入或不放入当前物品以获得最大总价值。
        }
    }
    printf("%d\n",dp[W]);
}
思路： 通过滚动数组的技巧，将二维数组转换为两行，每次只需保持两行数据。


// 滚动数组
int dp[2][105];//dp 数组存储背包在不同容量下所能达到的最大总价值
void solve() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i]) {
                dp[(i + 1) & 1][j] = dp[i & 1][j];
            } else {
                dp[(i + 1) & 1][j] = max(dp[i & 1][j],dp[(i + 1) & 1][j - w[i]] + v[i]);
            }
        }
    }
    printf("%d\n",dp[n & 1][W]);
}
(i + 1) & 1  这个表达式的结果可以用来切换两个状态之间的转换，通常用于滚动数组的优化技巧中。在这个特定的背包问题的代码中，用  (i + 1) & 1  来表示 0 和 1 之间的循环切换，以便在二维数组  dp  中交替使用两行来节省空间。


(i + 1) & 1  的计算过程：


    

  • 当  i  为偶数时， (i + 1)  为奇数，二进制表示为  10 ，对应的十进制是 2；而  1  的二进制表示也是  1 。
    • 

  • 当  i  为奇数时， (i + 1)  为偶数，二进制表示为  11 ，对应的十进制是 3；而  1  的二进制表示还是  1 。
    • 

  • 通过对  i  加 1，然后与 1 进行按位与操作，可以实现在 0 和 1 之间进行切换。
    • 



换句话说， (i + 1) & 1  的结果就是一个在 0 和 1 之间交替变化的数列，用于在滚动数组中切换状态，从而实现空间复杂度的优化。


# 01 背包 2




思路：这里条件变了，用老办法会超出


dp [i] [j] 代表前 i 个物品价值总和等于 j 时的最小重量


#include <iostream>
using namespace std;
int w[105],v[105];
int dp[105][10005];
int main()
{
    int n,W;
    cin>>n>>W;
    for (int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    for (int j=1;j<=n*100+1;j++)
    {                      
        dp[0][j]=1e9+1;                   
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n*100+1;j++)
        {
            if (j<v[i]) dp[i][j]=dp[i-1][j];
            else 
            {
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
            }            
        }
    }
    for (int j=n*100+1;j>=0;j--)
    {
        if (dp[n][j]<=W) 
        {
            cout<<j<<endl;
            return 0;
        }
    }   
    return 0;
}
# 多重部分和问题




思路：dp [j] 表示是否可以用给定的数字组合得到值  j


#include <iostream>
using namespace std;
int a[105], m[105];
int dp[100005];
int main()
{
    int n, K;
    cin >> n >> K;
    // 输入每个数字的值
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    // 输入每个数字的出现次数
    for (int i = 1; i <= n; i++)
    {
        cin >> m[i];
    }
    // 初始化 dp 数组
    for (int j = 1; j <= K; j++)
    {
        dp[j] = -1; // 初始化为 -1，表示暂时无法得到和为 j
    }
    // 遍历每个数字
    for (int i = 1; i <= n; i++)
    {
        // 更新 dp 数组的值
        for (int j = 0; j <= K; j++)
        {
            if (dp[j] >= 0 || j == 0)
            {
                dp[j] = m[i]; // 如果当前数字正好等于 j 或者 j 为 0，则更新 dp [j]
            }
            else if (j - a[i] >= 0 && dp[j - a[i]] > 0)
            {
                dp[j] = dp[j - a[i]] - 1; // 判断是否可以通过当前数字和已有的组合得到值 j
            }
            else
            {
                dp[j] = -1; // 其他情况下无法得到和为 j
            }
        }
    }
    // 判断是否可以得到目标值 K
    if (dp[K] >= 0)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
    return 0;
}
# 最长上升子序列




思路： dp  数组用于存储当前已经找到的最长上升子序列。


    

  1. lower_bound(dp, dp + n, a[i]) ：这部分使用  lower_bound  函数在  dp  数组中查找第一个大于或等于  a[i]  的元素的位置。
    2. 

  2. *lower_bound(dp, dp + n, a[i]) ：解引用  lower_bound  的结果，得到指向该位置的引用。
    3. 

  3. *lower_bound(dp, dp + n, a[i]) = a[i] ：将该位置上的值更新为  a[i] 。
    4. 



换句话说，这段代码的作用是将数组  a  中的元素依次插入到数组  dp  中，并确保  dp  数组中存储的是递增的序列。


#include <bits/stdc++.h>
using namespace std;
int n;
int a[105];
int dp[105];
void solve() {
    fill(dp,dp + n,1e7);// 将 dp 数组初始化为很大的数值 1e7
    for(int i = 0; i < n; i++) {
        *lower_bound(dp, dp + n, a[i]) = a[i];// 利用 lower_bound 函数将当前元素插入到 dp 数组中合适的位置
    }
    printf("%d\n", lower_bound(dp, dp + n, 1e7) - dp);
}
lower_bound  是一个 C++ 标准库中的函数，用于在有序序列（如数组或容器）中查找第一个大于或等于给定值的元素的位置。如果找到了符合条件的元素，则返回该元素的迭代器；如果没有找到符合条件的元素，则返回一个指向最后一个元素的下一个位置的迭代器。


以下是  lower_bound  函数的使用示例：


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> vec = {1, 3, 5, 7, 9};
    // 在有序序列 vec 中查找第一个大于或等于 6 的元素的位置
    auto it = lower_bound(vec.begin(), vec.end(), 6);
    if (it != vec.end()) {
        cout << "First element greater than or equal to 6 is: " << *it << endl;
        cout << "Position in the vector: " << it - vec.begin() << endl;
    } else {
        cout << "No element greater than or equal to 6 found in the vector." << endl;
    }
    return 0;
}
# 有关计数问题的 dp


# 划分数




划分数（Partition Number）是一个重要的数学概念，它涉及到将一个正整数拆分成多个正整数之和的问题。具体来说，对于给定的正整数 n，划分数表示将 n 拆分成若干个正整数之和的不同方式的数量。


例如，对于数值 4，它可以被拆分成以下几种方式：


    

  • 4
    • 

  • 3 + 1
    • 

  • 2 + 2
    • 

  • 2 + 1 + 1
    • 

  • 1 + 1 + 1 + 1
    • 



因此，数值 4 的划分数为 5。


思路：


#include <iostream>
using namespace std;
int dp[2][1005]; // 用于存储中间结果的二维数组，dp [i][j] 表示将 j 拆分成 i 个正整数之和的方式数
int main()
{
    int m, n, M;
    cin >> n >> m >> M; // 输入参数 n、m 和 M，分别表示被拆分的数、最多拆分成几个数、取模的数
    // 初始化边界条件，当划分数为 1 时的情况，即将所有的数都拆分成一个数
    for (int j = 0; j <= n; j++)
    {
        dp[1][j] = 1; // 只有一种拆分方式，即拆分成本身
    }
    // 动态规划计算划分数
    for (int i = 2; i <= m; i++) // 从划分数为 2 开始逐步计算到 m
    {
        for (int j = 0; j <= n; j++) // 对于每个被拆分的数值 j
        {
            if (j - i >= 0) // 如果 j 大于等于当前划分数 i
            {
                // 根据动态规划递推公式更新 dp 数组
                //dp [i][j] = 使用 i-1 个数拆分 j 的方式数 + 使用 i 个数拆分 j-i 的方式数
                dp[i & 1][j] = (dp[(i - 1) & 1][j] + dp[i & 1][j - i]) % M; // 注意取模运算
            }
            else // 否则 j 小于当前划分数 i，无法继续拆分 
            {
                dp[i & 1][j] = dp[(i - 1) & 1][j]; // 拆分数为 i 的方式数等于拆分数为 i-1 的方式数
            }
        }
    }
    cout << dp[m & 1][n]; // 输出计算得到的结果
    return 0;
}
# 多重集组合数




思路：dp [i] [j] 代表从前 i 类物品中取出 j 个的取法数


#include <iostream>
using namespace std;
int a[1005];
int dp[2][1005];
int main()
{
    int n,m,M;
    cin>>n>>m>>M;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dp[0][0]=1;
    dp[1][0]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if (j-a[i]-1<0)
            {
                dp[i&1][j]=(dp[i&1][j-1]+dp[(i-1)&1][j])%M;
            }
            else
            {
                dp[i&1][j]=(dp[i&1][j-1]+dp[(i-1)&1][j]-dp[(i-1)&1][j-a[i]-1]+M)%M;// 小细节，+M 是为了防止由于减法产生了负数
            }
        }
    }
    cout<<dp[n&1][m];
    return 0;
}
# 数据结构


# 优先队列和堆


优先队列（Priority Queue）是一种特殊的队列，它的特点是每次出队的元素是队列中优先级最高的元素。在优先队列中，元素通常带有优先级，这样在出队时会优先选择优先级最高的元素。优先队列常常用于实现任务调度、事件模拟等场景。


在 C++ 中，STL（Standard Template Library）提供了优先队列的实现，可以使用 <queue>  头文件中的 priority_queue  类来创建优先队列。通过指定比较函数或使用默认的比较函数，可以实现不同类型的优先队列（最大堆或最小堆）。


#include <iostream>
#include <queue>
using namespace std;
int main() {
    // 创建一个最大堆的优先队列
    priority_queue<int> maxHeap;
    // 插入元素
    maxHeap.push(3);
    maxHeap.push(5);
    maxHeap.push(1);
    // 访问队首元素
    cout << maxHeap.top() << endl;
    // 弹出队首元素
    maxHeap.pop();
    cout << maxHeap.top() << endl;
    return 0;
}
堆（Heap）是一种特殊的树形数据结构，常用于实现优先队列。堆分为最大堆和最小堆两种类型，最大堆指父节点的值大于或等于任意一个子节点的值，最小堆则相反，父节点的值小于或等于任意一个子节点的值。


在实际应用中，通常使用二叉堆（Binary Heap）来实现堆。二叉堆是一种完全二叉树，可以使用数组来表示。在数组中，根节点存储在索引 1 处，父节点和子节点之间的关系可以通过索引之间的计算得到。这种表示方法使得插入和删除元素时能够快速调整堆的结构。


实现：最小堆。插入：直接插到数组末尾，然后上浮；删除，最小值删除（头部），并把数组末尾的元素放到开头并删除，然后下沉


    

  • 对于节点 i，它的左子节点索引为 2i，右子节点索引为 2i+1
    • 

  • 对于节点 i，它的父节点索引为 i/2
    • 



#include <iostream>
#include <vector>
using namespace std;
// 最小堆类
class MinHeap {
private:
    vector<int> heap; // 使用 vector 存储堆元素
    // 上浮操作，用于插入元素时维护堆的性质
    void swim(int k) {
        while (k > 1 && heap[k/2] > heap[k]) { // 如果当前节点的值小于其父节点的值，则交换它们
            swap(heap[k/2], heap[k]);
            k = k/2; // 更新节点索引
        }
    }
    // 下沉操作，用于提取最小值时维护堆的性质
    void sink(int k) {
        int N = heap.size() - 1; // 堆的大小
        while (2*k <= N) { // 当存在子节点时进行循环
            int j = 2*k;
            if (j < N && heap[j] > heap[j+1]) j++; // 找到较小的子节点
            if (heap[k] <= heap[j]) break; // 如果当前节点的值小于等于最小的子节点的值，则不需要调整
            swap(heap[k], heap[j]); // 否则交换当前节点和最小子节点
            k = j; // 更新节点索引
        }
    }
public:
    MinHeap() {
        heap.push_back(-1); // 占位符，不使用索引 0
    }
    // 插入元素
    void insert(int x) {
        heap.push_back(x); // 将元素添加到末尾
        swim(heap.size() - 1); // 上浮操作
    }
    // 提取最小值
    int extractMin() {
        int minVal = heap[1]; // 最小值即为堆顶元素
        swap(heap[1], heap.back()); // 将堆顶元素与末尾元素交换
        heap.pop_back(); // 删除末尾元素
        sink(1); // 下沉操作
        return minVal; // 返回最小值
    }
    // 获取堆的大小
    int size() {
        return heap.size() - 1; // 不算占位符
    }
};
int main() {
    MinHeap minHeap;
    minHeap.insert(3);
    minHeap.insert(1);
    minHeap.insert(5);
    cout << minHeap.extractMin() << endl;
    cout << minHeap.extractMin() << endl;
    return 0;
}
# Expedition




思路：优先序列。将 A 从大到小排序，一次性把油用完，路过的加油站的油放进优先序列里，没油了从优先序列里加最大的油，ans++。如果没到达终点优先序列就没油了则输出 - 1。


#include <iostream>
#include <queue>
#include<algorithm>
using namespace std;
// 比较函数，用于排序加油站信息，按照距离降序排列
bool cmp(pair<int,int> a, pair<int,int> b)
{
    return a.first > b.first;
}
int main()
{
    int n;
    cin >> n; // 读入加油站数量
    pair<int,int> ab[20005]; // 存储加油站信息的数组
    for (int i = 1; i <= n; i++)
    {       
        cin >> ab[i].first >> ab[i].second; // 读入每个加油站的距离和油量
    }
    n++;
    ab[n].first = 0;
    ab[n].second = 0;
    sort(ab + 1, ab + n, cmp); // 按照距离降序排序加油站信息
    int l, p;
    cin >> l >> p; // 读入起点位置和初始油量
    int ans = 0;
    int x = l, oil = p;
    priority_queue<int, vector<int>, less<int>> q; // 优先队列，存储可以到达的加油站的油量
    for (int i = 1; i <= n; i++)
    {
        int d = x - ab[i].first; // 计算当前位置与下一个加油站的距离
        while (oil < d) // 当油量不足以到达下一个加油站时
        {
            if (q.empty()) // 如果优先队列为空，无法加油到达下一个加油站
            {
                cout << -1;
                return 0;
            }
            oil += q.top(); // 加油到达下一个加油站
            q.pop(); 
            ans++; // 加油次数加一
        }
        oil -= d; // 更新油量
        q.push(ab[i].second); // 将当前加油站的油量加入优先队列
        x = ab[i].first; // 更新当前位置为下一个加油站的位置
    }
    cout << ans; // 输出最终加油次数
    return 0;
}
# 二叉搜索树


二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树，具有以下性质：


    

  1. 对于二叉搜索树中的每个节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。
    2. 

  2. 二叉搜索树的左子树和右子树也分别是二叉搜索树。
    3. 



由于这些性质，二叉搜索树可以高效地支持如查找、插入、删除等操作，时间复杂度为 O (logn)，其中 n 为二叉搜索树中节点的数量。


插入节点：


    

  1. 从根节点开始，比较要插入节点的值与当前节点的值。
    2. 

  2. 如果要插入节点的值小于当前节点的值，则向左子树移动；如果大于当前节点的值，则向右子树移动。
    3. 

  3. 如果移动到的位置为空，则将新节点插入到这个位置。
    4. 

  4. 如果新节点的值等于当前节点的值，则可以根据具体情况选择是替换还是进行其他操作（这里一般选择不插入相同值的节点）。
    5. 



删除节点：


    

  1. 如果要删除的节点没有子节点，直接删除即可。
    2. 

  2. 如果要删除的节点只有一个子节点，将其父节点指向其子节点即可。
    3. 

  3. 如果要删除的节点有两个子节点，需要找到其右子树中最小的节点（或者左子树中最大的节点）来取代它。

      

    • 找到右子树中最小的节点：即找到右子树的最左节点。
      • 

    • 将该最小节点的值复制到要删除的节点上，并删除最小节点。
      • 

    

    4. 



#include <iostream>
using namespace std;
// 二叉搜索树节点结构
struct Node {
    int key;
    Node* left;
    Node* right;
    // 构造函数
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};
// 二叉搜索树类
class BinarySearchTree {
private:
    Node* root; // 根节点
    // 插入节点的辅助函数
    Node* insertHelper(Node* root, int key) {
        if (root == nullptr) {
            return new Node(key);
        }
        if (key < root->key) { // 如果要插入节点的值小于当前节点的值
            root->left = insertHelper(root->left, key); // 向左子树移动
        } else if (key > root->key) { // 如果要插入节点的值大于当前节点的值
            root->right = insertHelper(root->right, key); // 向右子树移动
        }
        return root;
    }
    // 查找最小节点
    Node* findMin(Node* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }
    // 删除节点的辅助函数
    Node* deleteHelper(Node* root, int key) {
        if (root == nullptr) {
            return root;
        }
        if (key < root->key) {
            root->left = deleteHelper(root->left, key);
        } else if (key > root->key) {
            root->right = deleteHelper(root->right, key);
        } else {
            if (root->left == nullptr) {
                Node* temp = root->right;
                delete root;
                return temp;
            } else if (root->right == nullptr) {
                Node* temp = root->left;
                delete root;
                return temp;
            }
            Node* temp = findMin(root->right);
            root->key = temp->key;
            root->right = deleteHelper(root->right, temp->key);
        }
        return root;
    }
    // 查找节点的辅助函数
    bool searchHelper(Node* root, int key) {
        if (root == nullptr) {
            return false;
        }
        if (root->key == key) {
            return true;
        }
        if (key < root->key) {
            return searchHelper(root->left, key);
        } else {
            return searchHelper(root->right, key);
        }
    }
public:
    // 构造函数
    BinarySearchTree() : root(nullptr) {}
    // 插入节点
    void insert(int key) {
        root = insertHelper(root, key);
    }
    // 删除节点
    void remove(int key) {
        root = deleteHelper(root, key);
    }
    // 查找节点
    bool search(int key) {
        return searchHelper(root, key);
    }
};
int main() {
    // 创建二叉搜索树
    BinarySearchTree bst;
    // 插入节点
    bst.insert(5);
    bst.insert(3);
    bst.insert(7);
    bst.insert(2);
    bst.insert(4);
    // 删除节点
    bst.remove(3);
    // 查找节点
    cout << "Is 4 in the tree? " << (bst.search(4) ? "Yes" : "No") << endl;
    cout << "Is 6 in the tree? " << (bst.search(6) ? "Yes" : "No") << endl;
    return 0;
}
C++ 标准库的  set  和  map  实现了二叉搜索树的功能


#include <iostream>
#include <set>
using namespace std;
int main() {
    // 创建一个整数集合
    set<int> s;
    // 插入元素
    s.insert(5);
    s.insert(3);
    s.insert(7);
    s.insert(2);
    s.insert(4);
    // 遍历集合并输出
    cout << "Set elements: ";
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    // 查找元素
    int key = 3;
    if (s.find(key) != s.end()) {
        cout << key << " found in the set" << endl;
    } else {
        cout << key << " not found in the set" << endl;
    }
    return 0;
}
#include <iostream>
#include <map>
using namespace std;
int main() {
    // 创建一个整数到字符串的映射
    map<int, string> m;
    // 插入键值对
    m[1] = "one";
    m[2] = "two";
    m[3] = "three";
    // 遍历映射并输出
    cout << "Map elements: ";
    for (auto it = m.begin(); it != m.end(); ++it) {
        cout << "(" << it->first << ", " << it->second << ") ";
    }
    cout << endl;
    // 查找键值对
    int key = 2;
    if (m.find(key) != m.end()) {
        cout << "Key " << key << " found in the map with value " << m[key] << endl;
    } else {
        cout << "Key " << key << " not found in the map" << endl;
    }
    return 0;
}
# 并查集


并查集（Disjoint Set Union，DSU）是一种数据结构，用于管理元素分组和查询元素所属的组别。并查集主要支持两种操作：合并（Union）和查找（Find）。在并查集中，每个集合通常用一棵树表示，树中的一个节点被称为代表元素，代表了该集合。以下是并查集的详细说明：


# 操作：


    

  1. MakeSet(x)：创建一个新的集合，其中包含元素 x。
    2. 

  2. Find(x)：查找元素 x 所属的集合（即根节点的代表元素）。
    3. 

  3. Union(x, y)：将包含元素 x 的集合与包含元素 y 的集合合并成一个集合。
    4. 



# 实现方式：


    

  1. 数组表示：使用一个数组来表示并查集，数组中的每个元素存储该元素所属集合的父节点（或者根节点）。
    2. 

  2. 路径压缩：在进行 Find 操作时，沿着路径将每个节点直接连接到根节点，以减少树的高度，加快后续操作。
    3. 

  3. 按秩合并：在进行 Union 操作时，将秩较小的集合合并到秩较大的集合上，以保持树的平衡，减少树的深度。
    4. 



int par[10005];// 父亲
int rank[10005];// 树的高度
// 初始化 n 个元素
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rank[i] = 0;
    }
}
// 查询树的根
int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);// 路径压缩，将经过节点的父节点都设为根节点
    }
}
// 合并 x 和 y 所属的集合
void unite(int x, int y) {
    x = find(x);// 找到元素 x 的根节点，路径压缩后 x 变为根节点
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}
// 判断 x 和 y 是否属于同一个集合
bool same(int x, int y) {
    return find(x) == find(y);
}
# 食物链




动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B， B 吃 C，C 吃 A。

现有 N 个动物，以 1－N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

第一种说法是 "1 X Y"，表示 X 和 Y 是同类。

第二种说法是 "2 X Y"，表示 X 吃 Y。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1） 当前的话与前面的某些真的话冲突，就是假话；

2） 当前的话中 X 或 Y 比 N 大，就是假话；

3） 当前的话表示 X 吃 X，就是假话。

你的任务是根据给定的 N（1 <= N <= 50,000）和 K 句话（0 <= K <= 100,000），输出假话的总数。


思路：w [fy] = (t - 1 + w [x] + 2 * w [y]) % 3;// 画图总结的公式


#include <iostream>
using namespace std;
int p[50005], w[50005]; // 定义并查集的父节点数组 p 和权值数组 w
// 查找元素 x 所属的集合（根节点）
int find(int x)
{
    int fx = p[x];
    if (x == fx)
        return x;
    // 路径压缩，同时更新权值信息
    p[x] = find(fx);
    w[x] = (w[fx] + w[x]) % 3;
    return p[x];
}
int main()
{
    for (int i = 0; i < 50004; i++)
    {
        p[i] = i;
        w[i] = 0; // 初始化每个元素的父节点和权值信息
    }
    int n, k;
    cin >> n >> k; // 输入元素个数 n 和操作次数 k
    int ans = 0; // 记录不满足条件的操作次数
    while (k--)
    {
        int t, x, y;
        scanf("%d %d %d", &t, &x, &y); // 读入操作类型 t，元素 x 和元素 y
        if (x < 1 || x > n || y < 1 || y > n)
        {
            ans++; // 如果元素 x 或元素 y 不在有效范围内，则答案加一
            continue;
        }
        int fx = find(x);
        int fy = find(y);
        if (fx == fy)
        {
            if (t == 1 && w[x] != w[y])
            {
                ans++; // 如果属于同一集合且不满足条件，答案加一
            }
            else if (t == 2 && (w[x] + 1) % 3 != w[y]) // 3 种关系 a，b 同类，a 吃 b，b 吃 a
            {
                ans++; // 如果属于同一集合且不满足条件，答案加一
            }
        }
        else
        {
            p[fy] = fx; // 合并两个集合
            w[fy] = (t - 1 + w[x] + 2 * w[y]) % 3;// 画图总结的公式
        }
    }
    cout << ans; // 输出最终答案
    return 0;
}
# 图


# 图的搜索




思路：把相邻点染成不同颜色的题叫着色图，对图进行染色需要的最小颜色数称为最小着色数。最小着色数是 2 的图称为二分图。


vector 邻接表的形式如下


顶点：1 2 3 4 5
边的连接关系：
1 2
1 3
2 4
3 4
3 5
4 5



根据上述输入，邻接表会被构建成下面的形式：


G[1]: [2, 3]
G[2]: [1, 4]
G[3]: [1, 4, 5]
G[4]: [2, 3, 5]
G[5]: [3, 4]
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> G[1005]; // 图的邻接表表示
int color[1005]; // 顶点的颜色，0 表示未染色，1 和 -1 分别表示两种颜色
// 深度优先搜索函数，用于染色并检查是否能正确着色
bool dfs(int v, int c)
{
    color[v] = c; // 将顶点 v 染成颜色 c
    for (int i = 0; i < G[v].size(); i++)
    {
        if (color[G[v][i]] == c)
            return false; // 如果相邻顶点颜色相同，则返回 false
        else if (color[G[v][i]] == 0 && !dfs(G[v][i], -c))
            return false; // 如果相邻顶点未染色且染色失败，则返回 false
    }
    return true; // 所有相邻顶点都能正确染色，则返回 true
}
int main()
{
    int n;
    cin >> n; // 读取顶点数量 n
    int x, y;
    while (scanf("%d %d", &x, &y) != EOF) // 从标准输入中读取边的连接关系
    {
        G[x].push_back(y); // 添加边到邻接表中
        G[y].push_back(x); // 无向图需双向添加
    }
    for (int i = 0; i < n; i++)
    {
        if (color[i] == 0) // 若顶点未染色
        {
            if (!dfs(i, 1)) // 进行染色，如果染色失败则输出 "No"
            {
                cout << "No";
                return 0;
            }
        }
    }
    cout << "Yes"; // 所有顶点都能正确染色，则输出 "Yes"
    return 0;
}
# 最短路径问题


# Bellman-Ford


# Dijkstra


# Floyd-Warshall


# 最小生成树


# prim 算法


# Kruskal


# 题目




#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
const int MAX_N = 5005; // 点的最大数量
const int inf = 1 << 20; // 表示无穷大的值
int dist1[MAX_N]; // 存储最短路径长度
int dist2[MAX_N]; // 存储次短路径长度
struct edge
{
    int to;
    int cost;
};
vector<edge> es[MAX_N]; // 存储边的信息
typedef pair<int, int> P;
priority_queue<P, vector<P>, greater<P>> q; // 优先队列
int main()
{
    int n, r;
    cin >> n >> r; // 输入点的数量和边的数量
    fill(dist1, dist1 + n + 1, inf); // 初始化距离数组为无穷大
    fill(dist2, dist2 + n + 1, inf);
    dist1[1] = 0; // 起始点到自身的距离为 0
    q.push(P(0, 1)); // 将起始点加入优先队列
    for (int i = 0; i < r; i++)
    {
        int x, y, d;
        scanf("%d %d %d", &x, &y, &d); // 输入边的信息
        edge e;
        e.to = x;
        e.cost = d;
        es[y].push_back(e); // 将边信息存入对应的结点中
        e.to = y;
        es[x].push_back(e);
    }
    while (!q.empty())
    {
        P p = q.top();
        q.pop();
        int v = p.second;
        if (dist2[p.second] < p.first)
            continue;
        for (int i = 0; i < es[v].size(); i++)
        {
            edge e = es[v][i];
            int d2 = p.first + e.cost;
            if (dist1[e.to] > d2)
            {
                swap(d2, dist1[e.to]); // 更新最短路径值
                q.push(P(dist1[e.to], e.to));
            }
            if (dist2[e.to] > d2 && dist1[e.to] < d2)
            {
                dist2[e.to] = d2; // 更新次短路径值
                q.push(P(dist2[e.to], e.to));
            }
        }
    }
    cout << dist2[n]; // 输出终点的次短路径长度
    return 0;
}
# 




#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int par[20005]; // 并查集的父节点数组
int Rank[20005]; // 并查集树的深度数组
struct edge
{
	int from;
	int to;
	int cost; 
};
// 初始化并查集
void init()
{
	for (int i = 0; i < 20005; i++)
	{
		par[i] = i; // 每个节点的父节点初始化为自己
		Rank[i] = 0; // 每个节点的深度初始化为 0
	}
}
// 查找节点所属集合的根节点
int find(int x)
{
	if (x == par[x]) return x;
	else return par[x] = find(par[x]);
}
// 合并两个集合
void unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (Rank[x] > Rank[y])
	{
		par[y] = x;		
	}
	else
	{
		par[x] = y;
		if (Rank[x] == Rank[y]) Rank[x]++;
	}
}
// 判断两个节点是否属于同一个集合
bool same(int x, int y)
{
	return find(x) == find(y);
}
// 比较边的权重大小
bool cmp(edge a, edge b)
{
	return a.cost > b.cost;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		init(); // 初始化并查集
		vector<edge> es; // 存储边的数组
		int n, m, r;
		scanf("%d %d %d", &n, &m, &r); // 输入点的数量、边的数量以及边的权重
		while (r--)
		{
			int x, y, d;
			scanf("%d %d %d", &x, &y, &d); // 输入边的起点、终点和权重
			y += n; // 将终点的索引值加上点的数量，以区分点在不同的集合中
			edge e;
			e.from = x;
			e.to = y;
			e.cost = d;	
			es.push_back(e);					
		}
		sort(es.begin(), es.end(), cmp); // 按边的权重从大到小排序
		int res = 0;
		for (int i = 0; i < es.size(); i++)
		{
			edge e = es[i];
			if (!same(e.from, e.to)) // 如果边的两个端点不在同一个集合中
			{
				unite(e.from, e.to); // 合并这两个集合
				res += e.cost; // 将边的权重加入结果中
			}
		}
		cout << 10000 * (n + m) - res << endl; // 输出最终结果
	} 
	return 0;
}


#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
const int MAX_N = 1005;
const int inf = 1 << 20;
struct edge
{
	int from;
	int to;
	int cost;
};
vector<edge> es;
int d[MAX_N];
int main()
{
	int n, ml, md;
	cin >> n >> ml >> md;
	fill(d, d + MAX_N, inf); // 初始化距离数组
	d[1] = 0;
	
	while (ml--)
	{
		int al, bl, dl;
		scanf("%d %d %d", &al, &bl, &dl);
		edge e;
		e.from = al;
		e.to = bl;
		e.cost = dl;
		es.push_back(e);
	}
	while (md--)
	{
		int ad, bd, dd;
		scanf("%d %d %d", &ad, &bd, &dd);
		edge e;
		e.from = bd;
		e.to = ad;
		e.cost = -dd; // 注意：这里是负边，用负数表示
		es.push_back(e);
	}	
	for (int i = 0; i <= n; i++) // Bellman-Ford 算法
	{	
		for (int j = 2; j <= n; j++)
		{
			if (d[j] < inf)
			{
				d[j - 1] = min(d[j - 1], d[j]); // 更新距离数组		
			}
		}
		for (int j = 0; j < es.size(); j++)
		{
			edge e = es[j];
			if (d[e.to] > d[e.from] + e.cost)
			{
				d[e.to] = d[e.from] + e.cost;
				if (i == n) // 检测负环路
				{
					cout << "-1";
					return 0;
				}							
			}
		}		
	}	
	if (d[n] >= inf) // 若距离为初始值，则表示走不通
		d[n] = -2;
	cout << d[n]; // 输出结果
	return 0;
}
# 数论


# 辗转相除法


# 最大公约数




思路：暴力检查所有点，复杂度 o（|x1-x2|*|y1-y2|）。画图可以得出答案是 | x1-x2| |y1-y2 | 最大公约数 - 1。那么如何求最大公约数呢？这里用到辗转相除法。


辗转相除法，又称欧几里德算法，用于求两个整数的最大公约数（Greatest Common Divisor，简称 GCD）。算法基于以下定理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。


辗转相除法的步骤如下：


    

  1. 用较大数除以较小数，得到余数。
    2. 

  2. 将较小数作为新的被除数，余数作为新的除数，继续相除，直到余数为 0。
    3. 

  3. 最后一次相除的除数就是最大公约数。
    4. 



#include <iostream>
using namespace std;
// 辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
int main() {
    int num1, num2;
    cout << "输入两个整数：" << endl;
    cin >> num1 >> num2;
    int result = gcd(num1, num2);
    cout << "它们的最大公约数是：" << result << endl;
    return 0;
}
# 有关素数的基础算法


素数是大于 1 的自然数中，除了 1 和本身外没有其他因数的数。换句话说，只能被 1 和自身整除的数被称为素数。


以下是一些前几个素数的例子：


    

  • 2 是最小的素数。
    • 

  • 3, 5, 7, 11, 13, 17, 19, 23, 29 是前面几个素数。
    • 



判断一个数是否为素数通常需要遍历从 2 到该数的平方根范围内的数来进行验证。如果该数可以被其中任何一个数整除，那么它就不是素数。


#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int num;
    cout << "输入一个整数：" << endl;
    cin >> num;
    if (isPrime(num)) {
        cout << num << " 是素数。" << endl;
    } else {
        cout << num << " 不是素数。" << endl;
    }
    return 0;
}
# 埃氏筛法


埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用来查找一定范围内所有素数的古老而有效的算法。这个算法以希腊数学家埃拉托斯特尼的名字命名。


算法的基本思想是从 2 开始，将每个素数的各个倍数标记为非素数，直到不能再继续为止。具体步骤如下：


    

  1. 初始化一个布尔数组，用来表示从 2 到 n 之间的所有数，初始值都为 true，表示都是素数。
    2. 

  2. 从 2 开始遍历到 (\sqrt {n})：

      

    • 如果当前数字 i 是素数（即布尔数组中对应的值为 true），则将 i 的所有倍数标记为非素数（将布尔数组中对应位置的值设为 false）。
      • 

    

    3. 

  3. 遍历结束后，所有值为 true 的位置对应的数字就是素数。
    4. 



#include <iostream>
#include <vector>
using namespace std;
vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n+1, true);
    vector<int> primes;
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }
    return primes;
}
int main() {
    int N;
    cout << "请输入一个整数 N：" << endl;
    cin >> N;
    vector<int> result = sieveOfEratosthenes(N);
    cout << "小于等于 " << N << " 的所有素数为：" << endl;
    for (int prime : result) {
        cout << prime << " ";
    }
    cout << endl;
    return 0;
}
# 区间筛选


区间筛法是一种用于找出某一区间内所有素数的算法，它是埃拉托斯特尼筛法的一种变体。区间筛法通常用于在给定的区间内高效地找出所有素数。


#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 区间筛法找出给定区间 [low, high] 内的所有素数
void segmentedSieve(int low, int high) {
    // 计算 sqrt (high)，作为标记数组的上限
    int limit = floor(sqrt(high)) + 1;
    // 初始化标记数组和素数数组
    vector<bool> isPrime(limit + 1, true);
    vector<int> primes;
    
    // 使用埃拉托斯特尼筛法在 [2, sqrt (high)] 范围内找出素数
    for (int p = 2; p * p <= limit; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= limit; i += p) {
                isPrime[i] = false;
            }
        }
    }
    // 将筛选出的素数存入 primes 数组中
    for (int p = 2; p <= limit; p++) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }
    // 初始化区间内的标记数组，初始都为素数
    vector<bool> isPrimeRange(high - low + 1, true);
    // 对每个素数进行区间筛法
    for (int prime : primes) {
        int start = ceil((double)low / prime) * prime;
        for (int i = max(start, prime * prime); i <= high; i += prime) {
            isPrimeRange[i - low] = false;
        }
    }
    // 输出区间内的所有素数
    for (int i = low; i <= high; i++) {
        if (i >= 2 && isPrimeRange[i - low]) {
            cout << i << " ";
        }
    }
}
int main() {
    int low, high;
    cout << "请输入区间的下界和上界：" << endl;
    cin >> low >> high;
    cout << "区间 [" << low << ", " << high << "] 内的所有素数为：" << endl;
    segmentedSieve(low, high);
    cout << endl;
    return 0;
}
# 快速幂


问题：快速求出 a^k mod p 的结果，时间复杂度为 O (logk)，其中 a,p,k 为 10 的 9 次方。


暴力：


res = 1;
for(int i  = 1; i <= k; i++)
{
	res = res * a mod p;//k 次后再取模
}
// 时间复杂度 O (k);
# 反复平方法


方法是将 a^k 拆成若干项相乘的形式，即把 k 化成二进制形式，变成 2 的幂次相加。


反复平方法（快速幂算法）是一种用来快速计算一个数的整数次幂的算法。它利用了幂运算的一些性质，通过将指数进行二进制拆分的方式，减少了运算的次数，从而提高了计算效率。


下面是反复平方法的基本实现步骤：


    

  1. 将指数 (k) 表示为其二进制形式，例如：( k = b_m 2^m + b_m-1} 2({m-1) + \ldots + b_1 2 + b_0 )。
    2. 

  2. 初始化一个变量  res  为 1，表示结果。
    3. 

  3. 从高位到低位依次处理二进制表达中的每一位：

      

    • 如果当前位 (b_i = 1)，则将结果乘以基数 ( a ) 并取模 ( p )。
      • 

    • 在每一步中，基数 (a) 都会自乘以自身并取模 ( p )。
      • 

    

    4. 

  4. 循环结束后，返回结果  res 。
    5. 



这样，通过对指数进行二进制拆分和利用幂运算的性质，可以大大减少计算的次数，从而提高了计算效率。


int fastExpoMod(int a, int k, int p) {
    long long res = 1;                    // 初始化结果为 1
    long long base = a % p;                // 初始化底数为 a mod p
    while (k > 0) {                        // 当指数大于 0 时进行循环
        if (k % 2 == 1) {                  // 如果当前指数的最低位为 1
            res = (res * base) % p;        // 更新结果为 (res * base) mod p
        }
        base = (base * base) % p;          // 更新底数为 (base^2) mod p
        k /= 2;                            // 将指数右移一位，相当于除以 2
    }
    return (int)res;                       // 返回结果，注意转换为 int 类型
}
int result = fastExpoMod(2, 5, 7);         // 调用函数计算 2^5 mod 7 的结果

      

          
          
          
          
      

  


   


    

  
    
      
    
    更新于