- gf24202 的博客
2025年全国青少年信息素养大赛国赛真题
-
gf24202
LV 10
@
2026-8-15 16:43:08
2025年全国青少年信息素养大赛国赛真题 详细解析
T1 积木摆放
题目理解
题目描述 有一排共 n 块积木，第 i 块积木初始高度为 a_i。你最多可以执行 k 次搭建操作：每一次操作选定一段连续的积木区间 [l, r]，将区间内每一块积木的高度全部 +1。你可以自由选择每次操作的区间，总操作次数不能超过 k。求执行完操作之后，单块积木能够达到的最大高度（其余积木高度无需考虑）。
样例分析
输入：
5 2
1 2 3 2 1
输出：
5
解释：将2次操作全部作用在第3块积木上，每次选择区间[3,3]
第3块积木最终高度：3+2=5
思路分析
贪心策略
这道题的关键在于理解操作的性质：
- 每次操作可以选择任意连续区间 [l, r]
- 区间内的所有积木高度都 +1
- 我们只关心单块积木能达到的最大高度
最优策略：
- 找到初始高度最大的积木
- 每次操作都选择只包含这一块积木的区间 [i, i]
- 这样每次操作只会给目标积木 +1
- k 次操作后，目标积木高度 = max(a) + k
为什么这样是最优的？
- 任何一次操作，如果区间长度 > 1，那么目标积木 +1 的同时还会给其他积木 +1，但这对我们追求单块最大高度没有额外帮助
- 如果要让某块积木增加高度，每次操作最多只能让它 +1
- 所以一块积木最多能增加 k 的高度
- 初始最高的积木加上 k 就是理论最大值
- 这个理论最大值完全可以达到（每次都选单点区间）
代码实现
#include <bits/stdc++.h>
using namespace std;
int n, k; // n:积木数量, k:最多操作次数
int a[1005]; // 存储每块积木的高度
int ans; // 记录初始最大高度
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> k;
// 读入所有积木高度，同时找出最大值
for (int i = 1; i <= n; ++i) {
cin >> a[i];
ans = max(a[i], ans); // 更新最大高度
}
// 初始最大值 + k 次操作 = 最终答案
cout << ans + k;
return 0;
}
复杂度分析
- 时间复杂度：O(n)，只需遍历一次数组
- 空间复杂度：O(n)，存储积木高度
易错点
- 注意是"最多"k 次操作，不是必须用 k 次
- 区间可以选择任意 [l, r]，包括 l = r
- 答案 = 最大值 + k，因为每次操作都能给目标积木 +1
T2 密码破译
题目理解
题目描述 给定一个仅由小写英文字母组成的字符串 s。定义优美子串：子串内部，每一种出现过的字符，出现次数全部相等。例如：aabb（a、b各2次）、aabbcc（a、b、c各2次）均为优美子串。求字符串中最长的优美子串长度，若无合法子串输出 0。
样例分析
样例输入1：aabbcc
样例输出1：6
解释：整串字符各出现2次，a:2, b:2, c:2，符合优美子串定义
样例输入2：aaabbc
样例输出2：4
解释：最长合法子串为 aabb，长度为4（a:2, b:2）
思路分析
暴力枚举法
由于数据范围很小（|s| ≤ 100），可以采用枚举所有子串的方法：
- 枚举子串的起点 i（0 到 n-1）
- 枚举子串的终点 j（i 到 n-1）
- 统计子串 s[i..j] 中每个字符的出现次数
- 检查是否"优美"：所有出现过的字符次数相等
- 更新答案
判断逻辑详解
如何判断一个子串是否优美？
例如子串 "aabbcc"：
'a'出现2次，'b'出现2次，'c'出现2次
所有出现过的字符次数都是2 → 优美 ✓
例如子串 "aaabbc"：
'a'出现3次，'b'出现2次，'c'出现1次
次数不完全相等 → 不优美 ✗
判断步骤：
- 统计26个字母的出现次数
- 找到第一个出现次数 > 0 的字符，记录它的出现次数作为"基准值"
- 遍历所有26个字母，如果某个字母出现次数 > 0 但 != 基准值，则不优美
- 如果所有出现过的字母次数都等于基准值，则优美
代码实现
#include <bits/stdc++.h>
using namespace std;
int ans = 1; // 记录最长优美子串长度，初始为1
int n; // 字符串长度
string s; // 输入字符串
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> s;
n = s.size();
// 特判：空字符串或长度为1
if (n == 0) {
cout << 0;
return 0;
}
// 枚举所有子串
for (int i = 0; i < n; ++i) { // 子串起点
int cnt[55] = {0}; // 统计26个字母出现次数，初始化为0
for (int j = i; j < n; ++j) { // 子串终点
cnt[s[j] - 'a']++; // 当前字符计数+1
// 检查当前子串是否优美
int base = 0; // 基准次数
bool flag = true; // 是否优美
for (int k = 0; k < 26; ++k) {
if (cnt[k] != 0) { // 这个字符出现了
if (base == 0) {
base = cnt[k]; // 第一次遇到出现过的字符，记录基准
} else if (base != cnt[k]) {
flag = false; // 出现次数不同，不是优美子串
break;
}
}
}
if (flag) {
ans = max(ans, j - i + 1); // 更新答案
}
}
}
cout << ans;
return 0;
}
复杂度分析
- 时间复杂度：O(n² × 26) = O(26 × n²)
- n ≤ 100，所以最多 10000 × 26 = 260000 次操作，非常快
- 空间复杂度：O(1)，只用了常数额外空间
优化思路（可选）
可以提前预处理前缀和，用前缀和快速得到任意子串的字符出现次数：
prefix[i][c] = 前i个字符中字符c出现的次数
子串[l..r]中字符c的次数 = prefix[r+1][c] - prefix[l][c]
这样判断的复杂度从 O(26) 降到 O(26)，但总体还是 O(n² × 26)。
易错点
- 子串可以为空吗？题目没有明确说，但长度为1的子串一定优美，所以答案至少为1
- 字符只包含小写字母，所以只需要统计26个字母
- 注意cnt数组要重置，放在外层循环i里面初始化
T3 探险迷宫
题目理解
题目描述 给定 n 行 m 列迷宫：
- 0：空地可通行
- 1：墙壁不可通行
- S：起点
- T：终点
- P：传送门
人物上下左右移动一步耗时1；踩到任意传送门 P，可免费瞬间传送至任意其他传送门，传送仅可触发一次。求起点到终点最短耗时，无法到达输出 -1。
样例分析
输入：
3 4
S010
1P01
00PT
输出：
3
解释：
S(1,1) → (1,2) → (1,3)? 不对，地图是：
行1: S 0 1 0
行2: 1 P 0 1
行3: 0 0 P T
最优路径：
S(1,1) → (1,2) 步数1
(1,2) → (2,2)P 步数2，踩到传送门
从(2,2)传送到(3,3)P 步数2（传送不耗时）
(3,3) → (3,4)T 步数3
总耗时3步
思路分析
BFS + 状态
这是一个带状态的最短路问题，使用BFS求解：
为什么是BFS？
- 每一步的代价都是1（移动）
- 传送不消耗步数
- 要求最短路径，BFS天然适合无权图
状态的难点：传送门
- 传送门可以免费传送到任意其他传送门
- 但传送只能使用一次
- 所以需要记录是否已经使用过传送
状态设计
v[x][y][z]
z = 0: 还没有使用传送
z = 1: 已经使用过传送
BFS 逻辑
- 从起点开始，状态为 (x, y, 0) 表示未使用传送
- 扩展四个方向的相邻格子
- 如果到达传送门 P：
- 可以选择不传送，继续走（状态仍为0）
- 如果尚未使用传送（z=0），可以选择传送至任意其他P，状态变为1
- 如果到达终点，输出步数
- 如果队列为空，输出 -1
传送逻辑详解
踩到传送门 P 时：
┌─────────────────────────────────────┐
│ 如果 z == 0 (未使用传送) │
│ ├─ 选项1: 不传送 │
│ │ 状态不变，继续BFS │
│ └─ 选项2: 传送 │
│ 传送至所有其他P位置 │
│ 状态变为 z=1 │
│ 步数不变（传送不耗时） │
├─────────────────────────────────────┤
│ 如果 z == 1 (已使用传送) │
│ 只能选择不传送 │
│ 状态不变，继续BFS │
└─────────────────────────────────────┘
代码实现
#include <bits/stdc++.h>
using namespace std;
int n, m; // 迷宫行数、列数
int sx, sy; // 起点坐标 (S)
int zx, zy; // 终点坐标 (T)
int p[55][2]; // 存储所有传送门坐标
int cnt = 0; // 传送门数量
int dx[5] = {0, 0, 1, -1}; // 方向数组：右、左、下、上
int dy[5] = {1, -1, 0, 0};
char a[55][55]; // 迷宫地图
bool v[55][55][2]; // 访问标记 [x][y][z]
// 节点结构体
struct Node {
int x, y; // 坐标
int step; // 已耗步数
int used; // 是否已使用传送 (0/1)
};
// 判断坐标是否合法
bool canPass(int x, int y) {
if (x < 1 || y < 1 || x > n || y > m) return false; // 越界
if (a[x][y] == '1') return false; // 墙壁
return true;
}
void bfs(int x, int y) {
// 特判：起点就是终点
if (x == zx && y == zy) {
cout << 0 << "\n";
return;
}
queue<Node> q;
q.push({x, y, 0, 0}); // 起点入队，步数0，未使用传送
v[x][y][0] = true; // 标记已访问
while (!q.empty()) {
Node cur = q.front();
q.pop();
int used = cur.used;
// 四个方向移动
for (int i = 0; i < 4; ++i) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
int nstep = cur.step + 1;
// 越界或墙壁或已访问
if (!canPass(nx, ny)) continue;
if (v[nx][ny][used]) continue;
// ========== 情况1: 踩到传送门 ==========
if (a[nx][ny] == 'P') {
// 如果未使用传送
if (used == 0) {
// 选项1: 不传送，直接走上去
v[nx][ny][0] = true;
if (nx == zx && ny == zy) {
cout << nstep << "\n";
return;
}
q.push({nx, ny, nstep, 0});
// 选项2: 使用传送
for (int j = 1; j <= cnt; ++j) {
int tx = p[j][0];
int ty = p[j][1];
// 不能传送到自己
if (tx == nx && ty == ny) continue;
// 目标传送门位置必须可通行
if (!canPass(tx, ty)) continue;
// 已访问过（在used=1状态下）
if (v[tx][ty][1]) continue;
// 标记访问，状态变为1
v[tx][ty][1] = true;
// 检查是否到达终点
if (tx == zx && ty == zy) {
cout << nstep << "\n";
return;
}
// 入队，步数不变
q.push({tx, ty, nstep, 1});
}
continue; // 处理完传送，进入下一个方向
}
// ========== 已使用传送 ==========
else {
// 已使用传送，只能直接走上去
v[nx][ny][1] = true;
if (nx == zx && ny == zy) {
cout << nstep << "\n";
return;
}
q.push({nx, ny, nstep, 1});
continue;
}
}
// ========== 情况2: 普通空地 ==========
v[nx][ny][used] = true;
if (nx == zx && ny == zy) {
cout << nstep << "\n";
return;
}
q.push({nx, ny, nstep, used});
}
}
// 队列为空，无法到达终点
cout << -1 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
// 读入地图，记录起点、终点、传送门
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
if (a[i][j] == 'S') {
sx = i;
sy = j;
}
if (a[i][j] == 'T') {
zx = i;
zy = j;
}
if (a[i][j] == 'P') {
p[++cnt][0] = i;
p[cnt][1] = j;
}
}
}
// 特殊情况：只有一个传送门
// 根据题目说明，踩到任意传送门可传送至任意其他传送门
// 只有一个传送门时，无法传送，把P当成普通空地
if (cnt == 1) {
a[p[1][0]][p[1][1]] = '0';
}
bfs(sx, sy);
return 0;
}
复杂度分析
- 时间复杂度：O(n × m × 2 + cnt × 传送次数)
- 每个位置最多访问2次（used=0和used=1）
- 最坏情况：O(2 × n × m + cnt × 传送)
- 空间复杂度：O(n × m × 2)
易错点
- 传送次数限制：只能使用一次，不是每个传送门只能使用一次
- 传送不消耗步数：传送到另一个P时步数不变
- 传送门本身也是空地：到达P后，可以选择不传送直接走过去
- 只有一个传送门：无法传送，P应视为普通空地
- 起点或终点在传送门上：题目没说清楚，但代码可以处理
T4 物资补给
题目理解
题目描述 背包最大承重为 W，一共有 n 种物资。第 i 种物资：每件重量 w_i，每件价值 v_i，最多可以取 c_i 件。每种物资可以取 0∼c_i 件，物品不可拆分。在总重量不超过背包承重 W 的前提下，求背包能够装下的最大总价值。
样例分析
输入：
3 10
2 3 3
3 4 2
4 5 2
输出：
14
解释：
物品1取3件：重量 3×2=6，价值 3×3=9
物品2取0件
物品3取1件：重量 1×4=4，价值 1×5=5
总重量 6+4=10，总价值 9+5=14
思路分析
多重背包问题
这个问题属于多重背包（Multiple Knapsack）：
- 有 n 种物品
- 每种物品有数量限制 c_i
- 每种物品可以取 0 到 c_i 件
- 在容量限制下最大化价值
为什么不用完全背包？
- 完全背包每种物品无限取
- 这里每种物品有数量上限 c_i
为什么不用01背包直接展开？
- 直接展开：把 c_i 件物品拆成 c_i 个独立物品
- 如果 c_i 很大（如 100000），展开后物品数量过多
- 需要用二进制拆分优化
二进制拆分优化
核心思想：把 c_i 件物品分成若干"组"，每组打包成一个新物品，使得这些组能够组合出 0 到 c_i 之间的任意数量。
二进制拆分原理
对于数量 c，拆分为：
1, 2, 4, 8, ..., 2^(k-1), r
其中 r = c - (1+2+4+...+2^(k-1))
这些数可以组合出 0 到 c 之间的任意整数
举例说明
c = 10
拆分为：1, 2, 4, 3 (剩余)
验证：1+2+4=7，7+3=10 ✓
用1,2,4可以组合0~7
加上3可以组合3~10
合并：0~10 ✓
c = 13
拆分为：1, 2, 4, 6 (剩余)
1+2+4=7，7+6=13 ✓
1,2,4覆盖0~7
加6覆盖6~13
合并：0~13 ✓
拆分后做什么？
拆分后得到一组"新物品"，每个新物品有：
- 重量 = 原重量 × 该组件数
- 价值 = 原价值 × 该组件数
然后对这些新物品做01背包（每个物品选或不选）。
为什么这样能保证最优解？
因为任意取的件数 x (0 ≤ x ≤ c) 都可以用拆分后的组组合出来，所以所有可能的方案都能被表示。
代码实现
#include <bits/stdc++.h>
using namespace std;
int n, W; // n:物品种类数, W:背包容量
int dp[2005]; // dp[j]:容量j时的最大价值
int ww[100005]; // ww[i]:第i个拆分组的重量
int vv[100005]; // vv[i]:第i个拆分组的价值
int cnt = 0; // 拆分组总数
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> W;
// 处理每一种物品
for (int i = 1; i <= n; ++i) {
int w, v, c;
cin >> w >> v >> c;
// 二进制拆分：将c件物品拆分成log(c)组
// k: 当前组的件数，从1开始，每次翻倍
for (int k = 1; c > 0; k <<= 1) {
int t = min(k, c); // 实际取 t 件
ww[++cnt] = w * t; // 打包成新物品：重量
vv[cnt] = v * t; // 打包成新物品：价值
c -= t; // 减去已取走的件数
}
}
// 01背包：对每个拆分后的物品做选择
for (int i = 1; i <= cnt; ++i) {
// 从大到小遍历容量，确保每个物品只选一次
for (int j = W; j >= ww[i]; --j) {
dp[j] = max(dp[j], dp[j - ww[i]] + vv[i]);
}
}
// 输出容量为W时的最大价值
cout << dp[W];
return 0;
}
二进制拆分详细演示
以样例输入为例，展示完整的拆分过程：
输入：
3 10
2 3 3
3 4 2
4 5 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
处理物品1: w=2, v=3, c=3
拆分过程：
k=1, c=3
t = min(1, 3) = 1
组1: 重量=2×1=2, 价值=3×1=3
c = 3-1 = 2
k=2, c=2
t = min(2, 2) = 2
组2: 重量=2×2=4, 价值=3×2=6
c = 2-2 = 0
k=4, c=0 → 循环结束
物品1拆分成2组：(2,3), (4,6)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
处理物品2: w=3, v=4, c=2
拆分过程：
k=1, c=2
t = min(1, 2) = 1
组3: 重量=3×1=3, 价值=4×1=4
c = 2-1 = 1
k=2, c=1
t = min(2, 1) = 1
组4: 重量=3×1=3, 价值=4×1=4
c = 1-1 = 0
物品2拆分成2组：(3,4), (3,4)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
处理物品3: w=4, v=5, c=2
拆分过程：
k=1, c=2
t = min(1, 2) = 1
组5: 重量=4×1=4, 价值=5×1=5
c = 2-1 = 1
k=2, c=1
t = min(2, 1) = 1
组6: 重量=4×1=4, 价值=5×1=5
c = 1-1 = 0
物品3拆分成2组：(4,5), (4,5)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
最终拆分结果（6组）：
组1: (2,3) 代表物品1取1件
组2: (4,6) 代表物品1取2件
组3: (3,4) 代表物品2取1件
组4: (3,4) 代表物品2取1件（第2件）
组5: (4,5) 代表物品3取1件
组6: (4,5) 代表物品3取1件（第2件）
做01背包后得到 dp[10] = 14
选择：组2(4,6) + 组1(2,3) + 组5(4,5) = (10,14)
对应：物品1取3件 + 物品3取1件 ✓
为什么二进制拆分能保证全覆盖？
数学证明
设 c = 2^k - 1 + r，其中 0 ≤ r < 2^k
拆分结果为：1, 2, 4, ..., 2^(k-1), r
要证明：任意整数 x (0 ≤ x ≤ c) 都能表示为这些数的和。
情况1：0 ≤ x < 2^k
- x 可以用 1, 2, 4, ..., 2^(k-1) 的某些和表示（二进制表示）
情况2：2^k ≤ x ≤ c
- 令 y = x - r，则 0 ≤ y ≤ 2^k - 1
- y 可以用 1, 2, 4, ..., 2^(k-1) 的某些和表示
- 所以 x = r + y 可以用 r 加上这些数表示
覆盖合并：
- 情况1覆盖：[0, 2^k - 1]
- 情况2覆盖：[r, r + 2^k - 1] = [r, c]
- 因为 r < 2^k，两个区间有重叠，合并后覆盖 [0, c]
复杂度分析
| 阶段 | 复杂度 | 说明 |
|---|---|---|
| 二进制拆分 | O(n × log₂(c_max)) | 每种物品拆分成 log₂(c) 组 |
| 01背包 | O(cnt × W) | cnt 是拆分后的总组数 |
| 总复杂度 | O(n × W × log₂(c_max)) | 约 100 × 2000 × 7 = 1.4×10^6 |
空间复杂度：O(W + cnt)，dp数组和拆分数组
为什么不用vector？
题目要求用静态数组，所以用 ww[] 和 vv[] 存储拆分后的物品。
数组大小估算：
- n ≤ 100
- 每种物品最多拆分成 log₂(100) + 1 ≈ 7 组
- 总组数 ≤ 700
- 开 100005 完全安全
易错点
- 二进制拆分的剩余部分：最后剩余的数直接加入，不要丢弃
- 01背包容量遍历方向：必须从大到小，确保每个物品只选一次
- 输出 dp[W]：不是 dp[n] 或其他
- 数组大小：ww 和 vv 要足够大（100005），dp 要 ≥ W+1（2005）
四题总结
| 题号 | 题目 | 核心算法 | 时间复杂度 | 关键点 |
|---|---|---|---|---|
| T1 | 积木摆放 | 贪心 | O(n) | 每次操作只作用于目标积木 |
| T2 | 密码破译 | 枚举+统计 | O(n²×26) | 子串枚举，字符计数判断 |
| T3 | 探险迷宫 | BFS+状态 | O(2×n×m) | 传送门状态处理 |
| T4 | 物资补给 | 多重背包+二进制拆分 | O(n×W×log c) | 二进制拆分优化 |
题目难度分析
- T1：★☆☆☆☆ 签到题，简单贪心
- T2：★★☆☆☆ 暴力枚举即可
- T3：★★★★☆ BFS加上状态，稍复杂
- T4：★★★☆☆ 经典多重背包优化
竞赛技巧总结
- 看清数据范围：决定用什么算法
- 贪心策略：T1 直接找最大值
- 暴力枚举：T2 数据小，直接枚举所有子串
- 状态设计：T3 需要记录"是否使用传送"
- 二进制拆分：T4 经典优化，务必掌握
建议
- T1 和 T2 是送分题，一定要拿满分
- T3 注意传送门状态的处理，容易漏掉"不传送"这个选项
- T4 的二进制拆分是多重背包的常用优化，理解透彻后可以应对更复杂的问题