2026年梧州学院算法校队选拔赛题解

A、马里奥的金币统计

第一步：读题与数据范围分析

题目要求：给定两个整数 a 与 b，输出它们的和 a + b。

输入规模： $-10^9 \le a, b \le 10^9$ 。两个数的范围均在 32 位有符号整型可表示范围内，但相加后可能达到 $\pm 2 \times 10^9$ ，该值仍在 32 位有符号整型范围内（32 位 int 的范围约 $\pm 2.1 \times 10^9$ ）。

时间复杂度要求：由于仅需一次加法和一次输出，因此 $\mathcal{O}(1)$ 即可满足要求。

空间复杂度要求：仅需常数个变量，因此 $\mathcal{O}(1)$ 即可满足要求。

第二步：建模

将问题转化为严格的数学模型：

变量： $设输入变量为 a∈[−10^9,10^9] 和 b∈[−10^9,10^9]，均为整数。$
目标函数：S=a+b，其中 S 为输出值。
约束条件：无。

模型可归约为单次加法运算的标准形式，不涉及任何复杂结构。

第三步：模拟（朴素实现）

最直接的实现方法：读取两个整数，计算它们的和，然后输出。

时间复杂度 O(1)，空间复杂度 O(1)，完全满足题目要求。因此，朴素实现的复杂度已经达到最优，无需进一步优化。

#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ll a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

第四步：优化

由于朴素实现的时间复杂度 O(1) 和空间复杂度 O(1) 均已满足第一步推导的复杂度上限，且该问题不存在任何可优化的时间或空间瓶颈，因此跳过优化步骤。

第五步:最终c++代码

#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ll a, b;
    cin >> a >> b;
    // 计算两数之和
    cout << a + b << endl;
    return 0;
}

B、星露谷种子大采购

第一步：读题与数据范围分析

题目要求：给定 n 种种子的单价和持有的金币数 m，统计单价不超过 m 的种子种类数。

输入规模： $n \le 1000$ ， $a_i, m \le 10^5$ 。

时间复杂度要求：由于 $n$ 最大仅为 1000，即使遍历所有元素也只需 $\mathcal{O}(n)$ 时间，完全满足 $\mathcal{O}(n)$ 解法（甚至 $\mathcal{O}(n \log n)$ 也无压力）的要求。

空间复杂度要求：需要存储 $n$ 个整数， $\mathcal{O}(n)$ 空间即可，满足要求。

第二步：建模

将问题转化为数学模型：

变量：持有金币数 m，种子种类数 n，种子单价数组 a[1..n]（或 a[0..n-1]）。
目标函数： $ans = Σ_{i=1}^{n} [a_i ≤ m]，其中 [P] 表示如果条件 P 成立则为 1，否则为 0。$
约束条件： $1 ≤ n ≤ 1000，1 ≤ a_i, m ≤ 10^5$ 。

模型可归约为“遍历数组并计数满足条件的元素个数”的标准形式。

第三步：模拟（朴素实现）

最直接的实现方法：读取 n 和 m，然后遍历所有种子单价，若单价不大于 m 则计数器加一，最后输出计数器。

用户提供的代码正是这个朴素实现：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] <= m) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

该代码的核心步骤清晰：两次线性扫描（一次读取，一次计数），时间复杂度为 O(n)，空间复杂度为 O(n)。

在当前数据范围（n ≤ 1000）下，该复杂度完全可行，且没有任何实际优化必要。对 n=1000 的规模，任何 O(n) 算法都能在 1ms 内完成。因此朴素实现已是最终方案，无需第四步优化。

第四步：优化

朴素实现已是最终方案，无需第四步优化。

第五步：最终 C++ 代码

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    // 读取种子种类数 n 和持有的金币数 m
    int n, m;
    cin >> n >> m;

    // 存储每种种子单价
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 统计单价不超过 m 的种子种类数
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] <= m) {
            ++ans;
        }
    }

    // 输出结果
    cout << ans << endl;
    return 0;
}

C、Rating群内排行榜

第一步：读题与数据范围分析

题目要求：给定 $N$ 名群友的昵称、报分顺序（输入顺序）和 Rating 值，按照 Rating 从高到低排序，Rating 相同的按报分顺序（即输入顺序）先后排序，输出排序后的名单。

输入规模： $N \le 10^5$ ，Rating $\le 10^5$ ，昵称长度 $\le 10$ 。

时间复杂度要求：由于 $N$ 最大可达 $10^5$ ，最终算法的时间复杂度必须不超过 $\mathcal{O}(N \log N)$ ，否则无法在限制时间内完成。

空间复杂度要求：需要存储 $N$ 条记录， $\mathcal{O}(N)$ 空间是必需的且完全可行。

第二步：建模

将问题转化为排序模型：

变量：设 $i$ 为报分顺序（从 0 开始计数）， $name_i$ 为昵称字符串， $rating_i$ 为整数分数。
目标：对集合 $\{(i, name_i, rating_i)\}$ 进行排序。
排序键：主键 $rating_i$ 降序，次键 $i$ 升序（即报分顺序早的在前）。
约束：排序必须正确实现双键比较，且保证同 Rating 时维持原始顺序。

模型归约为经典的结构体排序问题。排序的严格定义是找到一个排列 $p[0..N-1]$ ，使得对于任意 $u < v$ ，有 $(rating_{p[u]} > rating_{p[v]})$ 或 $(rating_{p[u]} == rating_{p[v]} 且 p[u] < p[v])$ 。

第三步：模拟（朴素实现）

基于第二步的排序定义，最直接的朴素实现是选择一种简单但效率较低的排序算法。冒泡排序是基于比较的直观排序方法，此处采用冒泡排序进行模拟。

核心步骤：

定义结构体 Node，包含 name、rating 和 id。
读入 N，循环读入每条记录并存入数组。
使用冒泡排序：重复遍历数组，每次比较相邻两个元素，若不满足排序规则则交换。排序规则为：若 a.rating < b.rating 则交换（使高 Rating 上浮）；若 a.rating == b.rating 且 a.id > b.id 则交换（使小 id 上浮）。
经过 N-1 轮后数组有序，依次输出。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Node {
    string name;
    int rating;
    int id;
};

bool should_swap(const Node& a, const Node& b) {
    if (a.rating != b.rating) {
        // rating 高的应在前面，如果 a.rating < b.rating 则需要交换
        return a.rating < b.rating;
    }
    // rating 相同，id 小的在前，如果 a.id > b.id 则需要交换
    return a.id > b.id;
}

int main() {
    int N;
    cin >> N;
    vector<Node> arr(N);
    for (int i = 0; i < N; ++i) {
        cin >> arr[i].name >> arr[i].rating;
        arr[i].id = i;
    }

    // 冒泡排序
    for (int i = 0; i < N - 1; ++i) {
        for (int j = 0; j < N - 1 - i; ++j) {
            if (should_swap(arr[j], arr[j+1])) {
                swap(arr[j], arr[j+1]);
            }
        }
    }

    for (const auto& x : arr) {
        cout << x.id + 1 << " " << x.name << " " << x.rating << endl;
    }
    return 0;
}

时间复杂度分析：冒泡排序有两重循环，每次比较和可能的交换为 $\mathcal{O}(1)$ ，因此总时间复杂度为 $\mathcal{O}(N^2)$ 。空间复杂度：使用数组存储， $\mathcal{O}(N)$ 。

在当前数据范围 $N \le 10^5$ 下， $\mathcal{O}(N^2)$ 的时间复杂度将导致运行次数约为 $10^{10}$ 级别，远超常见时间限制（1~2 秒），因此朴素实现不可行，必须进行优化。

第四步：优化（性质驱动，逐步降复杂度）

优化点 1：使用更高效的比较排序算法（如快速排序、归并排序）

性质依据：由于题目仅要求按指定关键字排序，属于基于比较的排序问题，而基于比较的排序算法理论下界为 $\mathcal{O}(N \log N)$ 。冒泡排序的 $\mathcal{O}(N^2)$ 复杂度是因为存在大量冗余比较。使用更优的排序算法可以直接将时间复杂度降至下界。
优化操作：将冒泡排序替换为 C++ 标准库中的 std::sort 函数，该函数通常实现为快速排序的变体（内省排序），时间复杂度为 $\mathcal{O}(N \log N)$ 。同时，提供自定义比较函数以实现双键排序。
复杂度验证：优化后时间复杂度降为 $\mathcal{O}(N \log N)$ ，对于 $N=10^5$ ，运算量约为 $1.7 \times 10^6$ ，完全可接受。空间复杂度仍为 $\mathcal{O}(N)$ 。已满足第一步推导的复杂度上限，优化终止。

因此，最终方案采用 std::sort 实现。

第五步：最终 C++ 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node{
	string name;
	int score;
	int id;
	bool operator<(const node &a)const{
		if(score!=a.score){
			return score>a.score;
		}
		return id<a.id;
	}
};
int main() {
	int n;
	cin>>n;
	vector <node> a;
	for(int i=0;i<n;i++){
		string name;
		int score;
		cin>>name>>score;
		a.push_back({name,score,i});
	}
	sort(a.begin(),a.end());
	for(auto [name,score,id]:a){
		cout<<id+1<<" "<<name<<" "<<score<<endl;
	}
    return 0;
}

注意： std::sort的是不稳定排序，假设排序方式是

bool operator<(const node &a)const{
	return score>a.score;
}

那么当 $score == a.score$ 时，他的顺序是不能确定的,假如第一个报分的人是A1,rating是16000,第二个报分的人是A2,rating是16000, 则A1在前面与A2在前面都有可能出现。

所以推荐std::stable_sort，或者在std::sort排序规则添加一个唯一的键 $id$ ,让他保证只按照我们规定的排序顺序排序，不会随机排序。

D、罗德岛干员搭配

第一步：读题与数据范围分析

题目要求：给定 $n$ 个整数的数组 cost 和一个目标差值 target，统计有多少对不同的下标对 $(i, j)$ ，满足 cost[i] - cost[j] = target。

输入规模： $n \le 10^5$ ，cost[i] $\le 10^9$ ， $target \le 10^9$ 。

时间复杂度要求：由于 $n$ 最大可达 $10^5$ ，最终算法的时间复杂度必须不超过 $\mathcal{O}(n \log n)$ ，否则无法在限制时间内完成。

空间复杂度要求：需要存储 $n$ 个元素， $\mathcal{O}(n)$ 空间是完全可行的。

第二步：建模

给定数组 $cost[0..n-1]$ 和目标差值 $target$ ，要求统计不同且无序的下标对 $(i, j)$ 个数，满足 cost[i] - cost[j] = target。

这里的下标对是有顺序的：先选干员 A（编号 $i$ ），再选干员 B（编号 $j$ ），要求 cost[i] - cost[j] = target。因此， $(i, j)$ 和 $(j, i)$ 是不同的组合，除非 $i = j$ （但题目要求不同的干员，所以 $i \neq j$ ）。根据示例，输入的数组中可能包含重复的值，且不同下标视为不同的干员，因此需要基于下标计数。

变量：

$n$ ：数组长度
$target$ ：目标差值
$cost[i]$ ：第 $i$ 个干员的部署费用

目标：

$ans = Σ_{i=0}^{n-1} Σ_{j=0, j≠i}^{n-1} [cost[i] - cost[j] = target]$

此问题可归约为“两数之和”问题的变种：遍历数组，对于当前元素 cost[i]，需要查找之前已遍历的元素中，有多少个满足与 cost[i] 的差为 target。

将等式变形：

$cost[i] - cost[j] = target$
即 $cost[j] = cost[i] - target$ （情况一：当前元素作为被减数）
或者 $cost[i] = cost[j] + target$ ，即 $cost[j] = cost[i] + target$ （情况二：当前元素作为减数）

因此，在遍历过程中，对于当前元素 $cost[i]$ ，需要查询其 $-target$ 和 $+target$ 的值在之前出现的次数。

第三步：模拟（朴素实现）

最直接的解法是使用双重循环枚举所有 $(i, j)$ 且 $i \neq j$ 的组合，统计满足 $cost[i] - cost[j] = target$ 的对数。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    int n, target;
    cin >> n >> target;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;          // 跳过同一个干员
            if (a[i] - a[j] == target) {
                ++ans;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

时间复杂度分析：双重循环枚举所有对，时间复杂度为 $\mathcal{O}(n^2)$ 。空间复杂度分析：仅使用数组存储， $\mathcal{O}(n)$ 。

由于 $n$ 最大可达 $2 \times 10^5$ ， $\mathcal{O}(n^2)$ 的时间复杂度在最坏情况下需要进行 $4 \times 10^{10}$ 次运算，1秒内最多能进行 $10^8$ ~~$10^9$ 次运算,远超常规时间限制（通常为 1~~2 秒），因此朴素实现不可行，必须进行优化。

第四步：优化（性质驱动，逐步降复杂度）

优化点 1：哈希表优化（利用等式变形与在线查询）

性质依据：由于等式 cost[i] - cost[j] = target 可变形为 cost[j] = cost[i] - target，说明对于每一个 $i$ ，我们只需要知道之前已遍历的元素中，有多少个等于 cost[i] - target 即可统计所有以当前元素作为被减数的有效对。同时，还需考虑当前元素作为减数的情况，即 cost[j] = cost[i] + target。由于哈希表可以在平均 $\mathcal{O}(1)$ 时间内完成查询和插入，因此利用哈希表存储已遍历元素的频次，可以将单次查询和更新操作降至 $\mathcal{O}(1)$ 。
优化操作：遍历数组时，维护一个 unordered_map（哈希表），键为元素值，值为该值出现的次数。对于当前元素 a[i]，在更新哈希表之前，先查询 a[i] - target 和 a[i] + target 在哈希表中的出现次数，并累加至答案。这样做的依据是：当遍历到 $i$ 时，哈希表中记录的是所有 $j < i$ 的元素频次，对于这些 $j$ ， $i$ 都在选定的前一个干员位置，因此 $i > j$ 。而题目要求的是对不同的干员组合 $(i, j)$ ，因此 $i$ 和 $j$ 的前后顺序在遍历时自然分开。同时，因为两数可以互换位置，因此在累积答案时需要同时考虑 +target 和 -target 两种情况。查询完毕后，再将当前元素 a[i] 加入哈希表。这样，一次遍历即可完成统计。
复杂度验证：优化后时间复杂度为 $\mathcal{O}(n)$ ，因为每个元素只进行常数次哈希表操作。空间复杂度为 $\mathcal{O}(n)$ ，用于存储哈希表。已满足第一步推导的复杂度上限，优化终止。

第五步：最终 C++ 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//a[i]-a[j]=m
//a[i]=m+a[j]
//a[j]=a[i]-m
int main() {
	int n,m;
	cin>>n>>m;
	vector <ll> a(n);
	unordered_map <ll,ll> maps;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	ll ans=0;
	for(int i=0;i<n;i++){
		ans+=maps[a[i]-m];
		ans+=maps[a[i]+m]; 
		maps[a[i]]++;
	}
	cout<<ans<<endl;
    return 0;
}

E、MC骨粉机误触事件

第一步：读题与数据范围分析

题目要求：给定 $N$ 格耕地，初始值为 $0$ ，执行 $M$ 次区间加法操作（每次对 $[L, R]$ 加 $K$ ），最后输出所有耕地中的最大值。

数据范围： $N, M \le 10^5$ ， $K \le 10^9$ 。

最坏情况：若所有 $M$ 次操作均覆盖全部 $N$ 格，每格累加总量为 $M \times K = 10^5 \times 10^9 = 10^{14}$ 。该值超出32位int范围（约 $2.1 \times 10^9$ ），因此必须使用64位整数类型（long long，上限约 $9.2 \times 10^{18}$ ）存储中间结果。

时间复杂度要求： $N$ 和 $M$ 均为 $10^5$ 级别。朴素方法对每次操作遍历区间内所有元素进行加法，时间复杂度为 $\mathcal{O}(N \times M) = \mathcal{O}(10^{10})$ ，远超时间限制。因此算法时间复杂度必须达到 $\mathcal{O}(N+M)$ 级别。

第二步：建模

本题是典型的“多次区间修改、最后一次单点查询”问题。

数学模型：

原数组： $a[1..N]$ ，初始全0，存储每格耕地的最终生长阶段值。
$M$ 次操作：第 $i$ 次操作为 $(L_i, R_i, K_i)$ ，表示 $a[L_i..R_i]$ 区间内所有元素增加 $K_i$ 。
目标： $\max(a[1..N])$ 。

差分数组模型：

差分数组的核心原理是通过记录相邻元素的差值，将区间修改转化为两个端点的单点修改，再通过前缀和还原原始数组。

构造差分数组 $diff[1..N+1]$ ： $diff[i] = a[i] - a[i-1]$ （定义 $a[0]=0$ ）。
区间更新操作：对原数组区间 $[L, R]$ 加 $K$ ，等价于：
- $diff[L] += K$ （从 $L$ 开始，后续元素在还原时均增加 $K$ ）
- $diff[R+1] -= K$ （从 $R+1$ 开始，后续元素在还原时不再增加 $K$ ）
还原操作：通过前缀和从差分数组还原原数组，即 $a[i] = a[i-1] + diff[i]$ 。

因此， $a[i] = \sum_{j=1}^{i} diff[j]$ ，差分数组通过前缀和还原为原数组。

第三步：模拟（朴素实现）

最直接的朴素实现是直接按照题目描述，对每次操作的 [L, R] 区间内的每个元素逐一加上 K。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(n + 1, 0);
    
    for (int i = 0; i < m; i++) {
        int l, r;
        ll k;
        cin >> l >> r >> k;
        for (int j = l; j <= r; j++) {
            a[j] += k;
        }
    }
    
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > ans) ans = a[i];
    }
    cout << ans << endl;
    return 0;
}

时间复杂度：每次操作需要 $\mathcal{O}(N)$ 时间遍历区间， $M$ 次操作总共 $\mathcal{O}(N \times M)$ 。在 $N$ 和 $M$ 均为 $10^5$ 时， $\mathcal{O}(10^{10})$ 的运算量远超限制，因此朴素实现不可行，必须进行优化。

空间复杂度： $\mathcal{O}(N)$ ，用于存储数组。

第四步：优化（性质驱动，逐步降复杂度）

优化点 1：差分数组优化

性质依据：由于题目具有“多次区间修改后一次性查询”的特性，与差分数组的核心应用场景完全重合。差分数组能够将区间修改操作从 $\mathcal{O}(N)$ 降低到 $\mathcal{O}(1)$ ，因为每次修改只需要更新两个端点的差分值。同时，由于查询发生在所有修改完成之后，符合差分数组“离线处理”的要求。
优化操作：引入差分数组 diff，将区间更新转化为端点更新：对于每个操作 $(L, R, K)$ ，只需执行：
- diff[L] += K
- diff[R+1] -= K 所有操作完成后，通过一次前缀和扫描还原原数组并同时记录最大值。
复杂度验证：
- 时间复杂度： $M$ 次操作每次 $\mathcal{O}(1)$ ，前缀和还原 $\mathcal{O}(N)$ ，总计 $\mathcal{O}(N+M)$ 。 $N,M=10^5$ 时运算量约 $2 \times 10^5$ ，完全满足要求。
- 空间复杂度：差分数组需 $\mathcal{O}(N)$ 空间，满足要求。
- 优化已达到复杂度上限，无需进一步优化。

第五步：最终 C++ 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	int n,m;
	cin>>n>>m;
	vector <ll> a(n+5);
	for(int i=0;i<m;i++){
		ll l,r,k;
		cin>>l>>r>>k;
		a[l]+=k;
		a[r+1]-=k;
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		a[i]+=a[i-1];
		ans=max(ans,a[i]);
	}
	cout<<ans<<endl;
    return 0;
}

F、猫猫虫的质数蠕动

第一步：读题与数据范围分析

题目要求：猫猫虫每次蠕动前进的距离必须是一个质数（可重复使用同一质数）。有 $Q$ 次独立询问，每次给定总距离 $N$ （ $2 \le N \le 10^5$ ），求最少蠕动次数使总距离恰好为 $N$ 。

数据范围： $Q \le 10^5$ ， $N \le 10^5$ 。

时间复杂度上限：由于询问次数很大，回答单次询问的复杂度必须为 $\mathcal{O}(1)$ 或均摊 $\mathcal{O}(1)$ ，预处理时间可接受 $\mathcal{O}(N \log \log N)$ 或 $\mathcal{O}(N)$ 。空间复杂度 $\mathcal{O}(N)$ 可行。

第二步：建模

该问题等价于：将正整数 N 拆分为若干质数之和，求项数的最小值。形式化如下：

给定 N ∈ ℕ，N ≥ 2。
求最小整数 k，使得存在质数序列 p₁, p₂, …, p_k 满足 ∑ pᵢ = N。

该模型为标准的最少质数拆分问题。由于拆分与顺序无关，且同一质数可无限使用，问题本质是“用质数凑出面值 N 的无界背包问题，要求物品个数最少”。其数学结构可用动态规划或图论（BFS）描述。

第三步：模拟（朴素实现）

最直接的朴素实现是根据问题定义进行暴力搜索或动态规划。

1.DFS 暴力枚举：

尝试所有可能的质数组合，对每一种拆分方案进行深度优先搜索，记录使用质数个数最少的方案。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INT_MAX = 0x3f3f3f3f;
const int MAXN = 100000;
vector<int> primes;
vector<bool> isp(MAXN + 1, true);
int min_cnt;

void init() {
    isp[0] = isp[1] = false;
    for (int i = 2; i <= MAXN; ++i) {
        if (isp[i]) {
            primes.push_back(i);
            for (int j = i * 2; j <= MAXN; j += i)
                isp[j] = false;
        }
    }
}

void dfs(int remain, int cnt) {
    if (remain == 0) {
        if (cnt < min_cnt) min_cnt = cnt;
        return;
    }
    // 剪枝：若当前 cnt 已经不小于已知最小次数，停止搜索
    if (cnt >= min_cnt) return;
    // 尝试所有权值不超过 remain 的质数
    for (int p : primes) {
        if (p > remain) break;
        dfs(remain - p, cnt + 1);
    }
}

int main() {
    init();
    int Q;
    cin >> Q;
    while (Q--) {
        int N;
        cin >> N;
        min_cnt = INT_MAX;
        dfs(N, 0);
        cout << min_cnt << endl;
    }
    return 0;
}

该方法的搜索空间极大，每个状态可选择的质数数量约为 N / log N，树的分支因子巨大，最坏复杂度为指数级，N = 10^5 时完全不可行。

2.动态规划（完全背包）：

定义 dp[x] 为凑出距离 x 所需的最少质数个数，初始化 dp[0] = 0，其余为无穷大。对于每个质数 p，正向更新：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100000;
const int INF = 1e9;

int main() {
    // 质数筛
    vector<bool> isp(MAXN + 1, true);
    vector<int> primes;
    isp[0] = isp[1] = false;
    for (int i = 2; i <= MAXN; ++i) {
        if (isp[i]) {
            primes.push_back(i);
            for (int j = i * 2; j <= MAXN; j += i)
                isp[j] = false;
        }
    }

    // 完全背包
    vector<int> dp(MAXN + 1, INF);
    dp[0] = 0;
    for (int p : primes) {
        for (int x = p; x <= MAXN; ++x) {
            dp[x] = min(dp[x], dp[x - p] + 1);
        }
    }

    int Q;
    cin >> Q;
    while (Q--) {
        int N;
        cin >> N;
        cout << dp[N] << endl;
    }
    return 0;
}

预处理所有 $N$ 范围内的质数需要 $\mathcal{O}(N \log \log N)$ （埃筛）或 $\mathcal{O}(N)$ （线性筛），DP 状态数 $\mathcal{O}(N)$ ，每个状态转移考虑所有质数，质数个数约为 $N / \log N$ ，因此 DP 时间复杂度为 $\mathcal{O}(N^2 / \log N)$ 。当 $N = 2 \times 10^5$ 时，运算量约为 $4 \times 10^{10} / 11.5 \approx 3.5 \times 10^9$ ，过于庞大，无法通过 1~2 秒时限。

因此，朴素 DFS 与 DP 实现均因复杂度过高而不可行，必须依赖更深层的数学性质进行优化。

第四步：优化（性质驱动，逐步降复杂度）

优化点 1：基于哥德巴赫猜想的数学归类

性质依据：由于问题域为“将整数拆分为质数之和求最少项数”，该问题在 $N \le 10^5$ 范围内拥有严格的数学结论。根据哥德巴赫猜想（在该范围内已验证），任意大于 2 的偶数可写成两个质数之和；任意大于 5 的奇数可写成三个质数之和。因此最少项数 ans 必然属于 $\{1, 2, 3\}$ 。这一性质与“质数拆分”问题的最优解结构性重合，可以用条件判断直接得出答案。
优化操作：
- 若 $N$ 本身是质数，ans = 1。
- 若 $N$ 是大于 2 的偶数，ans = 2（根据哥德巴赫猜想，必定存在两个质数之和）。
- 若 $N$ 是奇数且 $N - 2$ 是质数，则 $N = 2 + (N-2)$ ，ans = 2。
- 否则，奇数合数必定拆为三个质数（ $2 + 2 + (N-4)$ 必合法，因为此时 $N-2$ 不是质数， $N-4$ 可继续拆或本身为质数），ans = 3。为支持 $\mathcal{O}(1)$ 质数判定，提前使用欧拉线性筛预处理 $[0, 10^5]$ 内的质数表。
复杂度验证：预处理质数表 $\mathcal{O}(N) = 10^5$ ，单次询问仅需常数次判断，总时间复杂度 $\mathcal{O}(N + Q)$ ，完全满足第一步的复杂度上限。空间复杂度 $\mathcal{O}(N)$ 为存储布尔质数表，达标。该优化将指数级 / $\mathcal{O}(N^2)$ 的搜索降为 $\mathcal{O}(1)$ 判定，优化终止。

第五步：最终 C++ 代码

1.最快方法：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 欧拉线性筛预处理质数表
    vector<bool> is_prime(MAXN + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= MAXN; ++i) {
        if (is_prime[i]) primes.push_back(i);
        for (int p : primes) {
            if (1LL * i * p > MAXN) break;
            is_prime[i * p] = false;
            if (i % p == 0) break;
        }
    }

    int Q;
    cin >> Q;
    while (Q--) {
        int N;
        cin >> N;

        // 情况1：N 本身为质数 → 只需 1 次 , 可以使用复杂度 $\sqrt{N}$ 的素数判断方法
        if (is_prime[N]) {
            cout << "1\n";
            continue;
        }
        // 情况2：N 是偶数 → 哥德巴赫猜想保证可用 2 个质数
        if (N % 2 == 0) {
            cout << "2\n";
            continue;
        }
        // 情况3：N 是奇数且 N-2 为质数 → 2 + (N-2) 共 2 次, 可以使用复杂度为 $\sqrt{N}$ 的素数判断方法
        if (is_prime[N - 2]) {
            cout << "2\n";
            continue;
        }
        // 情况4：其余奇数合数 → 3 次
        cout << "3\n";
    }
    return 0;
}

2.比较简单的能通过的最终代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool isprime(int n){  //判断是否是质数，复杂度 $\mathcal{O}(\sqrt{n})$
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}
int main() {
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		if(isprime(n)){
			cout<<1<<endl;
			continue;
		}
		if(n%2==0){
			cout<<2<<endl;
			continue;
		}
		if(isprime(n-2)){
			cout<<2<<endl;
			continue;
		}
		cout<<3<<endl;
	}
    return 0;
}

因此，利用哥德巴赫猜想的数学结论，就能证明只有选择1、2、3个质数这三种情况，并没有上面的暴力模拟的一大行代码这么吓人。

题解 | 2026年梧州学院算法校队选拔赛题解

2026年梧州学院算法校队选拔赛题解

A、马里奥的金币统计

第一步：读题与数据范围分析

第二步：建模

第三步：模拟（朴素实现）

第四步：优化

第五步:最终c++代码

B、星露谷种子大采购

第一步：读题与数据范围分析

第二步：建模

第三步：模拟（朴素实现）

第四步：优化

第五步：最终 C++ 代码

C、Rating群内排行榜

第一步：读题与数据范围分析

第二步：建模

第三步：模拟（朴素实现）

第四步：优化（性质驱动，逐步降复杂度）

第五步：最终 C++ 代码

D、罗德岛干员搭配

第一步：读题与数据范围分析

第二步：建模

第三步：模拟（朴素实现）

第四步：优化（性质驱动，逐步降复杂度）

优化点 1：哈希表优化（利用等式变形与在线查询）

第五步：最终 C++ 代码

E、MC骨粉机误触事件

第一步：读题与数据范围分析

第二步：建模

数学模型：

差分数组模型：

第三步：模拟（朴素实现）

第四步：优化（性质驱动，逐步降复杂度）

优化点 1：差分数组优化

第五步：最终 C++ 代码

F、猫猫虫的质数蠕动

第一步：读题与数据范围分析

第二步：建模

第三步：模拟（朴素实现）

1.DFS 暴力枚举：

2.动态规划（完全背包）：

第四步：优化（性质驱动，逐步降复杂度）

优化点 1：基于哥德巴赫猜想的数学归类

第五步：最终 C++ 代码

1.最快方法：

2.比较简单的能通过的最终代码：