首页 程序设计 2025信息学院蓝桥杯专题训练

指导老师：毛明松
编撰：衷铭川（大数据 231 班，程设协会负责人）
友链：其实连按部就班也比想象中难
江西财经大学信息管理与数学学院编程会、计算机与人工智能学院程序设计竞赛协会

# 基础算法都有什么？

不算基础算法的基础算法：暴力、打表、模拟。
前缀和、差分、二分、双指针、高精度（bushi），位运算（bushi）（后二较少涉及）。
掌握基础算法，针对规模较大的问题，能够提高代码效率，同时，基础算法也是其他进阶算法的基础。

# 题目

题目集链接：https://vjudge.net/contest/704813
题目集密码：duoxichanganduoxichangan
VJVJ 比较抽象，可能需要～～ 魔法～～科学上网
排行榜链接：https://vjudge.net/contest/704813#rank

题目算法
和久必分分就必和前缀和
语文成绩差分
木材加工二分答案
1122Substring1122~Substring双指针
（选做）高精加高精度
（选做）高精乘高精度
（选做）高精减高精度
（选做）高精除高精度

此次训练只给出了部分题目，可以去洛谷，那里有题库总结：

  • 二分查找和二分答案
  • 前缀和、差分和离散化

# 和久必分分久必和

# 题目大意

给定 nn 个整数 a1,a2,⋯,ana_{1}, a_{2}, \cdots, a_{n}, 求它们两两相乘再相加的和，即

S=a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+an−2⋅an−1+an−2⋅an+an−1⋅anS=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n}

# 数据范围

1≤n≤2×105,1≤ai≤10001 \leq n \leq 2\times10^5,1 \leq a_{i} \leq 1000.

# 题解

# 暴力写法

对题目进行分析，nn 最大到了 2e52e5，如果暴力写这题的话，将会直接 TLETLE

C++
1
2
3
4
5
6
7
8
9
10
11
void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            res += a[i] * a[j];

    cout << res << endl;
}


(🏀杯按点给分，不过 33 个点还是太少了😭)

# 优化写法

前缀和参考链接传送门
观察有，题目要求的式子可以化为：

S=∑i=1n(ai∗(∑j=i+1naj))S=\sum\limits_{i=1}^{n}(a_i*(\sum\limits_{j=i+1}^{n}a_j))

我们只需要用前缀和，预处理出 ∑j=i+1naj\sum\limits_{j=i+1}^{n}a_j 这一部分，那我们就可以在 O(N)O(N) 的复杂度内，求出答案，代码如下：

C++
1
2
3
4
5
6
7
8
9
10
11
12
void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], pre[i] = pre[i - 1] + a[i];

    int res = 0;
    
    for (int i = 1; i <= n; i++)
        res += a[i] * (pre[n] - pre[i]);

    cout << res << endl;
}

# 语文成绩

# 题目大意

其实就是，有若干次操作，每次操作会令 axa_x 到 aya_y 的元素全部都加上 kk.

# 数据范围

对于 40%40\% 的数据，有 n≤103n \le 10^3.
对于 60%60\% 的数据，有 n≤104n \le 10^4.
对于 80%80\% 的数据，有 n≤105n \le 10^5.
对于 100%100\% 的数据，有 n≤5×106n \le 5\times 10^6.

# 题解

# 暴力写法

如果每个修改区间都是 [1,n][1,n]，那肯定直接炸了。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve () {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> g[i];
    
    for (int i = 1; i <= q; i++) {
        cin >> x >> y >> k;
        for (int j = x; j <= y; j++)
            g[j] += k;
    }

    int minn = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
        minn = min(minn, g[i]);

    cout << minn;
}

# 优化写法

差分参考链接传送门
这题可以利用差分将修改区间值的复杂度优化为 O(1)O(1)，之后再 O(n)O(n) 扫一遍整个区间求出修改后的结果并且找出最小值。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve () {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> g[i];

    for (int i = 1; i <= q; i++) {
        cin >> x >> y >> k;
        cf[x] += k, cf[y + 1] -= k;
    }

    int minn = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
        cf[i] += cf[i - 1], minn = min(minn, g[i] + cf[i]);

    cout << minn;
}

# 木材加工

# 题目大意

木材厂有 nn 根原木，现在想把这些木头切割成 kk 段长度均为 ll 的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 ll 的最大值。
木头长度的单位是 cm\text{cm}，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数

# 数据范围

1≤n≤1051\le n\le 10^5，1≤k≤1081\le k\le 10^8，1≤Li≤108(i∈[1,n])1\le L_i\le 10^8(i\in[1,n]).

# 题解

暴力枚举小木头的长度的做法显然是不能被时间复杂度之神原谅的。
这题的正确思路是二分答案，思路很简单，只是需要加强写二分的码力。

C++
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
bool check(int x) {
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        cnt += l[i] / x;
    return cnt >= k;
}

void solve () {
    cin >> n >> k;

    int sum = 0, maxx = 0;

    for (int i = 1; i <= n; i++)
        cin >> l[i], sum += l[i];

    if (sum < k) {
        cout << 0 << endl;
        return;
    }

    int l = 1, r = 1e8;

    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    cout << l << endl;
}

# 1122 Substring

# 题目大意

一个由正整数 (可能为空) 组成的序列 X=(X1,X2,...)X = (X_1, X_2, ...) 如果且仅当它满足以下三个条件时，才称为 1122 序列：

  • ∣X∣\lvert X \rvert 是偶数。这里 ∣X∣\lvert X \rvert 表示 XX 的长度。
  • 对于满足 1≤i≤∣X∣21\leq i\leq \frac{|X|}{2} 的每个整数 ii ， X2i−1X_{2i-1} 和 X2iX_{2i} 都相等。
  • 每个正整数要么完全不出现在 XX 中，要么正好出现两次。也就是说， XX 中包含的每个正整数在 XX 中恰好出现两次。
    给定长度为 NN 的由正整数组成的序列 A=(A1,A2,...,AN)A = (A_1, A_2, ..., A_N) ，打印 AA 的（连续）子数组的最大长度，该数组需要是一个 11221122 序列。

# 数据范围

  • 1≤N≤2×1051\leq N \leq 2 \times 10^5
  • 1≤Ai≤N1\leq A_i \leq N

# 题解

显然，所要的子串的长度必然是偶数，所以我们找的答案应该是 max(getMax(1), getMax(2)) ，同时从 11 和 22 两个位置找答案

C++
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
int getMax(int idx) {
    memset(cnt, 0, sizeof cnt);
    int l = idx, r = idx, res = 0;
    while (r <= n - 1) {
        if (a[r] != a[r + 1]) {
            while (l < r)
                cnt[a[l]]--, l++;
            r += 2, l += 2;
        }
        else {
            cnt[a[r]] += 2;

            while (cnt[a[r]] > 2)
                cnt[a[l]] -= 2, l += 2;

            r += 2;
        }

        res = max(res, r - 1);
    }

    return res;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cout << max(getMax(1), getMax(2)) << endl;
}

# 高精度模板（高精度题目选做）

# 高精度加法

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size())
            t += a[i];
        if (i < b.size())
            t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    
    if(t)
        c.push_back(1);
    
        return c;
}

# 高精度乘法

# 高精度 × 低精度

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> mul(vector<int> &a, int b) {
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || t; i++) {
        if(i < a.size())
            t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }

    while(c.size() > 1 && c.back() == 0)
        c.pop_back(); 
    
    return c;
}

# 高精度 × 高精度

C++
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
string mul(string aa, string bb) {
    vector<int> a, b, c(aa.size() + bb.size(), 0);

    for (int i = aa.size() - 1; i >= 0; i--)
        a.push_back(aa[i] - '0');
    for (int i = bb.size() - 1; i >= 0; i--)
        b.push_back(bb[i] - '0');

    for (int i = 0; i < b.size(); i++)
        for (int j = 0; j < a.size(); j++)
            c[i + j] += a[j] * b[i];

    for (int i = 0; i < c.size() - 1; i++) {
        if (c[i] > 9) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }

    int len = c.size() - 1;
    while (len > 0 && c[len] == 0)
        len--;

    string res = "";
    for (int i = len; i >= 0; i--)
        res += to_string(c[i]);

    return res;
}

# 高精度减法

C++
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
// 比较大小
bool compare(vector<int> &a, vector<int> &b) {
    if (a.size() != b.size())
        return a.size() > b.size();
    else {
        for(int i = a.size() - 1; i >= 0; i--)
            if (a[i] != b[i])
                return a[i] > b[i];
        return 1;
    }

}

vector<int> sub(vector<int> &a, vector<int> &b) {
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i++) {
        t = a[i] - t;
        if(i < b.size())
            t -= b[i];
        c.push_back((t + 10) % 10);
        t < 0 ? t = 1 : t = 0;
    }
    while(c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}

# 高精度除法

C++
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> div(vector<int> &a, int &b, int &res) {
    vector<int> c;
    for(int i = a.size() - 1; i >= 0; i--) {
        res = res * 10 + a[i];
        c.push_back(res / b);
        res %= b;
    }
    reverse(c.begin(), c.end());
    while(c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;    
}