个人主页：

wengqidaifeng

✨ 永远在路上，永远向前走

个人专栏：

数据结构
C语言
嵌入式小白启动！
重要OJ算法题详解
蓝桥杯备战

---

前言

本博客开始讲解蓝桥杯软件赛C/C++组所需要的基本算法中的模拟、高精度、枚举、前缀和以及差分算法。

---

一. 模拟算法

1. 模拟

顾名思义，就是题目让你做什么你就做什么，考察的是将思路转化为代码的能力。也就是说这种题目的解题思路不会特别复杂，可以比较轻松的想到。
这类题一般较为简单，属于竞赛里面的签到题（万事无绝对，有时候也会有非常难的模拟题）。

2. 例题：多项式输出

P1067 多项式输出


来让我们从这道题来开始分析。
模拟 + 分类讨论，对于一元二次方程的的最终结果，我们仅需按照顺序，考虑每一项的三件事情：符号 + 系数 + 次数。
• 处理「符号」：
◦ 如果系数小于 0 ，直接输出 “-”；
◦ 如果系数大于 0 ，除了首项不输出 “+”，其余全部输出 “+”。
• 处理「系数」：
◦ 先取一个绝对值，因为正负的问题已经处理过了；
◦ 当系数不等于 1 ，直接输出这个数；
◦ 但是当系数为 ，且是最后⼀项的时候，这个 也是需要输出的；其余情况下的 不需要输
出。
• 处理「次数」：
◦ 次数大于 1 ，输出 “x^” + 对应的次数；
◦ 次数等于 1 ，输出 “x”；
◦ 次数小于 1 ，什么也不输出。

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n; cin >> n;
// 循环次数
for(int i = n; i >= 0; i--)
{
int a; cin >> a;
if(a == 0) continue; // 处理系数为 0 的情况
// 1. 符号
if(a < 0) cout << '-';
else
{
if(i != n) cout << '+';
}
// 2. 数字
a = abs(a);
if(a != 1 || (a == 1 && i == 0)) cout << a;
// 3. 次数
if(i == 0) continue;
else if(i == 1) cout << 'x';
else cout << "x^" << i;
}
return 0;
}

3.例题：蛇形方阵

P5731 蛇形方阵

模拟填数的过程。
在⼀个矩阵中按照⼀定规律填数的通用解法：
• 定义方向向量，比如本题⼀共四个方向，分别是右、下、左、上，对应：
(0, 1)、(1, 0)、(0, −1)、(−1, 0)
• 循环填数的规则：
◦ 朝⼀个方向走，⼀边走⼀边填数，直到越界；
◦ 越界之后，结合定义的方向向量，求出下⼀轮应该⾛的⽅向以及应该到达的正确位置；
◦ 重复上述过程，直到把所有的数填完为止。

//矩阵方向向量解法
int dx[] = {0, 1, 0, -1};//在矩阵x方向上
int dy[] = {1, 0, -1, 0}；//在矩阵y方向上
//通过数组相加减，来移动
//比如取dx[1]，dy[1],表示向右移动一格

#include <iostream>
using namespace std;
const int N = 15;
// 定义 右，下，左，上 四个⽅向
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int arr[N][N];
int main()
{
int n; cin >> n;
// 模拟填数过程
int x = 1, y = 1; // 初始位置
int cnt = 1; // 当前位置要填的数
int pos = 0; // 当前的⽅向
while(cnt <= n * n)
{
arr[x][y] = cnt;
// 计算下⼀个位置
int a = x + dx[pos], b = y + dy[pos];
// 判断是否越界
if(a < 1 || a > n || b < 1 || b > n || arr[a][b])
{
// 更新出正确的该⾛的位置
pos = (pos + 1) % 4;
a = x + dx[pos], b = y + dy[pos];
}
x = a, y = b;
cnt++;
}
// 输出
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
printf("%3d", arr[i][j]);
}
puts("");
}
return 0;
}

二. 高精度

1. 高精度加法

P1601 加法模板

模拟小学「列竖式」计算「两数相加」的过程。

1. 用字符串读⼊数据；
2. 将字符串的每⼀位拆分，逆序放在数组中；
3. 模拟列竖式计算的过程：
   a. 对应位累加；
   b. 处理进位；
   c. 处理余数。
4. 处理结果的位数。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;
// ⾼精度加法的模版 - c = a + b;
void add(int c[], int a[], int b[])
{
for(int i = 0; i < lc; i++)
{
c[i] += a[i] + b[i]; // 对应位相加，再加上进位
c[i + 1] += c[i] / 10; // 处理进位
c[i] %= 10; // 处理余数
}
if(c[lc]) lc++;
}
int main()
{
string x, y; cin >> x >> y;
// 1. 拆分每⼀位，逆序放在数组中
la = x.size(); lb = y.size(); lc = max(la, lb);
for(int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';
for(int i = 0; i < lb; i++) b[lb - 1 - i] = y[i] - '0';
// 2. 模拟加法的过程
add(c, a, b); // c = a + b
// 输出结果
for(int i = lc - 1; i >= 0; i--) cout << c[i];
return 0;
}

2. 减法

P2142 高精度减法

模拟小学「列竖式」计算「两数相减」的过程。

1. ⽤字符串读⼊数据；
2. 判断两个数的⼤⼩，让较⼤的数在前。注意字典序 vs 数的⼤⼩：
   a. 位数相等：按字典序⽐较；
   b. 位数不等：按照字符串的⻓度⽐较。
3. 将字符串的每⼀位拆分，逆序放在数组中；
4. 模拟列竖式计算的过程：
   a. 对应位求差；
   b. 处理借位；
5. 处理前导零。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;
// ⽐⼤⼩
bool cmp(string& x, string& y)
{
// 先⽐较⻓度
if(x.size() != y.size()) return x.size() < y.size();
// 再按照 字典序 的⽅式⽐较
return x < y;
}
// ⾼精度减法的模板 - c = a - b
void sub(int c[], int a[], int b[])
{
for(int i = 0; i < lc; i++)
{
c[i] += a[i] - b[i]; // 对应位相减，然后处理借位
if(c[i] < 0)
{
c[i + 1] -= 1; // 借位
c[i] += 10;
}
}
// 处理前导零
while(lc > 1 && c[lc - 1] == 0) lc--;
}
int main()
{
string x, y; cin >> x >> y;
// ⽐⼤⼩
if(cmp(x, y))
{
swap(x, y);
cout << '-';
}
// 1. 拆分每⼀位，然后逆序放在数组中
la = x.size(); lb = y.size(); lc = max(la, lb);
for(int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0';
for(int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0';
// 2. 模拟减法的过程
sub(c, a, b); // c = a - b
// 输出结果
for(int i = lc - 1; i >= 0; i--) cout << c[i];
return 0;
}

3. 乘法

P1303 A*B

1. ⽤字符串读⼊数据；
2. 将字符串的每⼀位拆分，逆序放在数组中；
3. 模拟⽆进位相乘再相加的过程：
   a. 对应位求乘积；
   b. 乘完之后处理进位；
   c. 处理余数；
4. 处理前导零。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;
// ⾼精度乘法的模版 - c = a * b
void mul(int c[], int a[], int b[])
{
// ⽆进位相乘,然后相加
for(int i = 0; i < la; i++)
{
for(int j = 0; j < lb; j++)
{
c[i + j] += a[i] * b[j];
}
}
// 处理进位
for(int i = 0; i < lc; i++)
{
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
// 处理前导零
while(lc > 1 && c[lc - 1] == 0) lc--;
}
int main()
{
string x, y; cin >> x >> y;
// 1. 拆分每⼀位，逆序放在数组中
la = x.size(); lb = y.size(); lc = la + lb;
for(int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';
for(int i = 0; i < lb; i++) b[lb - 1 - i] = y[i] - '0';
// 2. 模拟乘法的过程
mul(c, a, b); // c = a * b
// 输出结果
for(int i = lc - 1; i >= 0; i--) cout << c[i];
return 0;
}

4. 除法

P1480 A/B

模拟⼩学「列竖式」计算「两数相除」的过程（注意，我们这⾥是「⾼精度 ÷ 低精度」）。
定义⼀个指针 i 从「⾼位」遍历被除数，⼀个变量 t 标记当前「被除的数」，记除数是 b ；
• 更新⼀个当前被除的数 t = t × 10 + a[i] ；
• t/b 表⽰这⼀位的商， t%b 表⽰这⼀位的余数；
• ⽤ t 记录这⼀次的余数，遍历到下⼀位的时候重复上⾯的过程
被除数遍历完毕之后， t ⾥⾯存的就是余数，但是商可能存在前导 0 ，注意清空。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
int a[N], b, c[N];
int la, lc;
// ⾼精度除法的模板 - c = a / b （⾼精度 / 低精度）
void sub(int c[], int a[], int b)
{
LL t = 0; // 标记每次除完之后的余数
for(int i = la - 1; i >= 0; i--)
{
// 计算当前的被除数
t = t * 10 + a[i];
c[i] = t / b;
t %= b;
}
// 处理前导 0
while(lc > 1 && c[lc - 1] == 0) lc--;
}
int main()
{
string x; cin >> x >> b;
la = x.size();
for(int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';
// 模拟除法的过程
lc = la;
sub(c, a, b); // c = a / b
for(int i = lc - 1; i >= 0; i--) cout << c[i];
return 0;
}

三. 枚举

1. 铺地毯

P1003 铺地毯

枚举所有的地毯，判断哪一个地毯能够覆盖 ((x, y)) 这个位置。

优化枚举方式：

• 因为我们要的是最后一个能够覆盖 ((x, y)) 位置的地毯，那么逆序枚举所有的地毯，第一次找到覆盖 ((x, y)) 位置的就是结果；
• 如果从前往后枚举，我们至少要把所有地毯都枚举完，才能知道最终结果。

#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int n;
int a[N], b[N], g[N], k[N];
int x, y;

int find()
{
    // 从后往前枚举
    for(int i = n; i >= 1; i--)
    {
        // 判断是否覆盖
        if(a[i] <= x && b[i] <= y && a[i] + g[i] >= x && b[i] + k[i] >= y)
            return i;
    }
    return -1;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) 
        cin >> a[i] >> b[i] >> g[i] >> k[i];
    cin >> x >> y;
    cout << find() << endl;
    return 0;
}

2. 回文日期

P2010 回文日期

枚举所有日月的组合，然后根据回文的特性推出年份，再比较这个数字是否在题目给定的区间内。

#include <iostream>
using namespace std;

int x, y;
int day[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main()
{
    cin >> x >> y;
    int ret = 0;
    
    // 枚举月日的组合
    for(int i = 1; i <= 12; i++)
    {
        for(int j = 1; j <= day[i]; j++)
        {
            int k = j % 10 * 1000 + j / 10 * 100 + i % 10 * 10 + i / 10;
            int num = k * 10000 + i * 100 + j;
            if(x <= num && num <= y) ret++;
        }
    }
    cout << ret << endl;
    return 0;
}

四. 二进制枚举

用一个数二进制表示中的 0/1 表示两种状态，从而达到枚举各种情况。

利用二进制枚举时，会用到一些位运算的知识。不熟悉的同学需要去补一下位运算相关的知识。

1. 子集

子集 - 力扣

枚举 (1 \sim (1 << n) - 1) 之间所有的数，每一个数的二进制中 1 的位置可以表示数组中对应位置选上该元素。这样就可以枚举出原数组中所有的子集。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ret;
        
        // 枚举所有状态
        for(int st = 0; st < (1 << n); st++)
        {
            vector<int> tmp;
            for(int i = 0; i < n; i++)
            {
                if((st >> i) & 1)
                    tmp.push_back(nums[i]);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

五. 前缀和

前缀和与差分的核心思想是预处理，可以在暴力枚举的过程中快速给出查询的结果，从而优化时间复杂度。这是经典的用空间换时间的做法。

1. 一维前缀和

【模板】前缀和 - 牛客网

前缀和模板题，直接套用公式创建前缀和数组，然后利用前缀和数组的性质处理 q 次查询。

1. 创建前缀和数组：(f[i] = f[i - 1] + a[i])
2. 查询 ([l, r]) 区间和：(f[r] - f[l - 1])

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

int n, q;
LL a[N];
LL f[N];

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    // 处理前缀和数组
    for(int i = 1; i <= n; i++)
        f[i] = f[i - 1] + a[i];
    
    // 处理 q 次询问
    while(q--)
    {
        int l, r; cin >> l >> r;
        cout << f[r] - f[l - 1] << endl;
    }
    return 0;
}

2. 最大子段和

P1115 最大子段和

考虑以 i 位置的元素 a[i] 为结尾的最大子段和。在求区间和时，相当于是用 f[i] 减去 i 位置前面的某一个 f[x]。如果想要最大子段和，那么用 f[i] 减掉一个前驱最小值即可。

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;

int n;
LL f[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        LL x; cin >> x;
        f[i] = f[i - 1] + x;
    }
    
    LL ret = -1e20;
    LL prevmin = 0;
    
    for(int i = 1; i <= n; i++)
    {
        ret = max(ret, f[i] - prevmin);
        prevmin = min(prevmin, f[i]);
    }
    cout << ret << endl;
    return 0;
}

3. 二维前缀和

【模板】二维前缀和 - 牛客网

二维前缀和模板题，直接套用公式创建前缀和矩阵，然后利用前缀和矩阵的性质处理 q 次询问。

1. 创建前缀和矩阵：(f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j])
2. 查询子矩阵和：(f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1])

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1010;

int n, m, q;
LL f[N][N];

int main()
{
    cin >> n >> m >> q;
    
    // 预处理前缀和矩阵
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            LL x; cin >> x;
            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + x;
        }
    }
    
    // 处理 q 次查询
    while(q--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

六. 差分

前缀和与差分是一对互逆的运算。

1. 一维差分

【模板】 差分

差分模板题，先创建差分数组，然后根据差分数组的性质处理 q 次区间修改，最后还原出来原始的数组。

1. 创建差分数组：(f[i] = a[i] - a[i - 1])
2. 区间修改：(f[l] += k, f[r + 1] -= k)
3. 还原数组：对差分数组做前缀和

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

int n, m;
LL f[N];

int main()
{
    cin >> n >> m;
    
    // 利用差分数组的性质，创建差分数组
    for(int i = 1; i <= n; i++)
    {
        LL x; cin >> x;
        f[i] += x;
        f[i + 1] -= x;
    }
    
    // 处理 m 次修改操作
    while(m--)
    {
        LL l, r, k; cin >> l >> r >> k;
        f[l] += k;
        f[r + 1] -= k;
    }
    
    // 还原出原始的数组
    for(int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i];
        cout << f[i] << " ";
    }
    return 0;
}

2. 二维差分

【模板】 二维差分

二维差分模板题，先根据差分矩阵的性质创建差分矩阵，然后处理 q 次区间修改，最后利用前缀和还原。

区间修改操作：对以 (x1, y1) 为左上角、(x2, y2) 为右下角的子矩阵每个元素加 k：

• (f[x1][y1] += k)
• (f[x1][y2 + 1] -= k)
• (f[x2 + 1][y1] -= k)
• (f[x2 + 1][y2 + 1] += k)

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1010;

int n, m, q;
LL f[N][N];

void insert(int x1, int y1, int x2, int y2, LL k)
{
    f[x1][y1] += k;
    f[x1][y2 + 1] -= k;
    f[x2 + 1][y1] -= k;
    f[x2 + 1][y2 + 1] += k;
}

int main()
{
    cin >> n >> m >> q;
    
    // 预处理差分矩阵
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            LL x; cin >> x;
            insert(i, j, i, j, x);
        }
    }
    
    // 处理 q 次修改操作
    while(q--)
    {
        LL x1, y1, x2, y2, k;
        cin >> x1 >> y1 >> x2 >> y2 >> k;
        insert(x1, y1, x2, y2, k);
    }
    
    // 利用前缀和还原出修改之后的数组
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
            cout << f[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

七. 前缀和与差分的结合应用

1. 从暴力到优化的思想

前缀和和差分虽然看起来是两种独立的算法，但在实际应用中，它们常常需要结合使用才能解决更复杂的问题。

核心思想回顾：

• 前缀和：预处理区间和，实现 O(1) 的区间查询
• 差分：预处理区间修改，实现 O(1) 的区间更新

那么问题来了：如果我们需要同时进行多次区间修改和多次区间查询，该怎么办？

2. 典型场景：先修改，后查询

当我们需要进行 m 次区间修改，然后进行 q 次区间查询时：

• 方案一：每次修改暴力更新数组 → O(m × n) 预处理，查询 O(1) 太慢
• 方案二：每次查询时计算区间和 → 修改 O(1)，查询 O(n) 太慢
• 方案三：差分 + 前缀和 → 修改 O(1)，最后统一还原，查询 O(1) 最优！

流程：

1. 用差分数组记录所有修改操作（O(m)）
2. 对差分数组做前缀和，还原出最终数组（O(n)）
3. 对最终数组做前缀和，准备查询（O(n)）
4. 处理 q 次查询（O(q)）

总时间复杂度：O(n + m + q)，远优于暴力做法！

3. 经典例题：区间修改 + 区间查询

题目描述

给定一个长度为 n 的数组 a，初始全为 0。进行 m 次操作，每次操作将区间 [l, r] 内的每个数加上 k。操作完成后，进行 q 次查询，每次查询区间 [L, R] 的和。

解法分析

这道题不能用普通的前缀和或差分单独解决：

• 只用差分：只能得到最终数组，无法快速回答区间和查询
• 只用前缀和：每次修改都要 O(n) 更新，太慢

正确做法：差分 + 前缀和 联合使用

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

int n, m, q;
LL diff[N];   // 差分数组
LL arr[N];    // 原数组
LL prefix[N]; // 前缀和数组

int main()
{
    cin >> n >> m >> q;
    
    // 1. 用差分数组记录所有修改
    while(m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        diff[l] += k;
        diff[r + 1] -= k;
    }
    
    // 2. 对差分数组做前缀和，还原出最终数组
    for(int i = 1; i <= n; i++)
    {
        arr[i] = arr[i - 1] + diff[i];
    }
    
    // 3. 对最终数组做前缀和，准备查询
    for(int i = 1; i <= n; i++)
    {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    
    // 4. 处理查询
    while(q--)
    {
        int L, R;
        cin >> L >> R;
        cout << prefix[R] - prefix[L - 1] << endl;
    }
    
    return 0;
}

4.总结：算法选择指南

问题类型	解决方案	时间复杂度
多次区间求和查询	一维/二维前缀和	预处理 O(n)，查询 O(1)
多次区间增加修改	一维/二维差分	修改 O(1)，还原 O(n)
先修改后查询	差分 + 前缀和	修改 O(1)，还原 O(n)，查询 O(1)
边修改边查询	树状数组/线段树	后续章节学习

记忆口诀：

• 前缀和，区间和，一减一加笑呵呵
• 差分数组改区间，左加右减记心间
• 两者结合力量大，先差后和顶呱呱

---

最后：

前缀和与差分是算法竞赛中最基础也最重要的预处理技巧。理解它们的本质——前缀和是「累积」，差分是「变化量」——比死记硬背公式更重要。

当你遇到一道题，发现需要频繁地「求区间和」或者「做区间修改」时，第一反应就应该是：能不能用前缀和或差分来优化？

掌握了这些基础算法，你就已经迈出了算法学习中最坚实的一步。下一章我们将学习双指针和二分算法，敬请期待！