CSP-J 入门级 · CSP 2026 入门级第一轮 第 20 题

【完善程序2】

（平衡分割）给定一个长度为 n 的字符串，其中每个字符都是一个十六进制数位。例如，字符串 016A 表示十进制下的四个数 0、1、6、10。现在请选择 k 个切分位置 p_1, p_2, ..., p_k，其中 1 ≤ k < n，且 1 ≤ p_1 < p_2 < ... < p_k < n。再令 p_0 = 0，p_{k+1} = n。对于每个 0 ≤ i ≤ k，计算第 p_i + 1 个到第 p_{i+1} 个数的平均值，记作 b_i。你的目标是使 b_0, b_1, ..., b_k 中最大值与最小值之差尽可能小，并输出这个最小值。其中 2 ≤ n ≤ 20。输入字符串中的字符只可能是 0~9 或 A~F。本题假定字符采用 ASCII 编码。输出答案时保留小数点后 6 位。以下程序通过递归枚举所有可能的连续分段方案。

#include <algorithm>
#include <iomanip>
#include <iostream>

using namespace std;

constexpr int N = 25;

int n, a[N];
char s[N];

double ans = 1e100;

int value(char c) { return 【①】; }

void split(int l, int cnt, double mnb, double mxb) {
    if (l > n) {
        if (cnt == 0) return;
        ans = min(ans, mxb - mnb);
        return;
    }
    int sum = 0;
    for (【②】) {
        sum += a[r];
        double nwb = 【③】;
        split(【④】);
    }
}

int main() {
    cin >> n >> s + 1;
    for (int i = 1; i <= 

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

递归枚举所有连续分段方案。① 是把十六进制字符转成数值（'0'~'9' 减 '0'，'A'~'F' 减 'A'-10）；② 是当前段的右端点 r 从 l 枚举到 n；③ 段平均值 = sum*1.0/(r-l+1)；④ 递归到下一段起点 r+1，切分点数 +1（仅当 r<n），并用 min/max 更新极值；⑤ 起点是 1、切分点数为 0、最小值初始化为 +∞、最大值初始化为 −∞。

② 容易选成从 1 开始——那样 sum 会累加全数组前缀，且 l>1 时会陷入无限递归；③ 若忘写 *1.0 会退化成整数除法（结果永远取整）；④ 里 r <= n 与 r < n 差一个切分点计数，会让"单段方案"被错误地算进答案。

程序分析

int value(char c) { return ① ; }
void split(int l, int cnt, double mnb, double mxb) {
    if (l > n) {                        // 递归终点：第 l..n 个字符分完了
        if (cnt == 0) return;           // 没有任何切分点 → 不合法，排除
        ans = min(ans, mxb - mnb);      // 用本方案的极差更新答案
        return;
    }
    int sum = 0;
    for (②) {                          // 枚举当前段的右端点 r
        sum += a[r];
        double nwb = ③ ;                // 当前段 a[l..r] 的平均值
        split(④);
    }
}
int main() {
    cin >> n >> s + 1;
    for (int i = 1; i <= n; ++i) a[i] = value(s[i]);
    split(⑤);
    cout << fixed << setprecision(6) << ans;
}

算法主线

问题要求：把长度 n 的十六进制串切成 k+1 段（1 ≤ k < n，即至少两段、至多 n 段），使"各段平均值"的极差（最大值 − 最小值）最小。

程序的做法是暴力枚举所有分段方案：

1. 参数 l 表示"当前段的起点"，cnt 表示"已经切了几刀"，mnb / mxb 是"已经形成的各段平均值中的最小/最大值"； 2. 第 22～27 行枚举当前段的右端点 r（从 l 到 n），累计 a[l..r] 的和，算出这一段平均值 nwb，带着更新后的 mnb/mxb 递归处理下一段（起点 r+1）； 3. l > n 时说明所有字符都已分段完毕，用 mxb − mnb 更新全局答案 ans。

逐空分析

① 应填 c - (c < 'A' ? '0' : 'A' - 10) → B 把十六进制字符转成数值：

• '0' ~ '9' → c - '0'；
• 'A' ~ 'F' → 10 ~ 15，即 c - 'A' + 10，而 c - ('A' - 10) = c - 'A' + 10 同值。

判断条件用 c < 'A'（题目声明字符采用 ASCII 编码，'9' 的 ASCII 小于 'A'）：小于 'A' 说明是数字字符 → 减 '0'；否则减 'A' - 10。

• A 的写法 c < '9' ? '0' : 'A' - 10 在 c == '9' 时判错（会把 '9' 当字母处理）；
• C 把两个分支的减数写反；D 的分支表达式 'A' + 10 使结果整体偏移 −20。

选 B。

② 应填 int r = l; r <= n; ++r → D 当前段的右端点必须从本段起点 l 开始枚举到 n，才能覆盖所有"非空连续段" a[l..r]。

• 若从 1 开始（选项 A、B、C 都以 1 起）：sum 会变成整数组的前缀和，与段起点 l 脱节；更严重的是当 l > 1 时递归 split(l, …) 内部又从头累加，导致 l 不再增长 → 无限递归 → 栈溢出；
• B 的 r < n 会漏掉"本段直达末尾"的方案；C 的 r += 2 会漏掉一半右端点。

选 D。

**③ 应填 sum * 1.0 / (r - l + 1) → C 段 a[l..r] 有 r − l + 1 个元素，平均值为 sum / (r−l+1)。为了做浮点除法**必须乘 1.0（否则 sum 与长度为整数，/ 会按整除截断，后面求极差就全错了）。

• A 先整除再乘 1.0，等于没救；
• B 的分母 r − l 少了 1，且写法奇怪；
• D 用 sum − a[r] 漏掉了段内最后一个元素。

选 C。

④ 应填 r + 1, cnt + (r < n), min(mnb, nwb), max(mxb, nwb) → A 四个实参依次是：下一段起点 r + 1；切分点数——只有当 r < n（本段没有吃到末尾）时才算切了一刀，所以是 cnt + (r < n)；以及把 nwb 并入当前极值：最小值取 min、最大值取 max。

• B 用 r <= n，当 r = n 时会多算一刀，使"不切分（cnt 仍为 0）"的单段方案混进答案；
• C、D 把 min 与 max 的位置写反，极值完全错乱。

选 A。

⑤ 应填 1, 0, 1e100, -1e100 → D 初始调用：第 1 个字符开始（l = 1）、还没有切分点（cnt = 0）；为了让第一次 min(mnb, nwb) / max(mxb, nwb) 一定被新值取代，最小值要初始化成"极大"1e100、最大值初始化成"极小"-1e100。

• A 的 l = 0 越界（a[0] 未定义）；
• B 的 l = 0 且极值方向反了；
• C 的极值方向反了（mnb = -1e100 会让极差变成极大的正数）。

选 D。

与题意的一个呼应

cnt == 0 时直接 return，正是为了排除"一刀不切（只有一段）"的方案——题目要求 1 ≤ k < n，至少两段。这个小细节也解释了 ④ 里为什么要用 r < n 计数。

本题小结

套路提示：递归枚举类完善程序的固定套路是"边界（l > n）→ 枚举决策点（for r）→ 更新状态（sum/nwb）→ 递归（新区间 + 新状态）"。填 for 的起点时盯住"决策变量的语义"（这里是段的右端点，必须从 l 起），填极值时盯住"哨兵方向"（求最小值初始化 +∞、求最大值初始化 −∞）。