BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（小学低年级组） 第 20 题

（倍减序列） 一个以正整数 $k$ 开始的倍减序列，是一个不定长的有序的正整数序列，它的第一个元素为 $k$，第二个元素不大于第一个元素的一半，第三个元素不大于第二个元素的一半，依此类推。例如，下面列出了所有的以 $6$ 开始的倍减序列，共有 $6$ 个：

6
6 1
6 2
6 2 1
6 3
6 3 1

任务要求：对于给定的正整数 $k$，请找出以 $k$ 开始的倍减序列的个数。

#include<iostream>
using namespace std;

int f[105];

int main() {
    ① ;
    int k = 0;
    cin >> k;
    for (int i = 2; i <=  ② ; ++i) {
        ③ ;
        for (int j = 1; j <=  ④ ; ++j) {
            f[i] += f[j];
        }
    }
    cout << ⑤ << endl;
    return 0;
}

1. ① 处应该填（ ） A. f[1] = 0 B. f[2] = 0 C. f[1] = 1 D. f[2] = 1 2. ② 处应该填（ ） A. k - 1 B. k C. k + 1 D. k / 2 3. ③ 处应该填（ ） A. f[i] = 1 B. f[i] = 0 C. f[j] = 1 D. f[j] = 0 4. ④ 处应该填（ ） A. i B. i - 1 C. k D. i / 2 5. ⑤ 处应该填（ ） A. f[k-1] B. f[1] C. f[k+1] D. f[k]

这题考的是动态规划，核心是把倍减序列拆解成‘以某个数开头的所有序列’。拿到题先想：f[i] 到底代表什么？题目里序列必须正整数，所以 f[0] 没意义，f[1] 只能是 1（只有序列[1]）。然后看递推：i 开头的序列，第二个数 j 可以取 1..i/2，因此 f[i] 等于所有 f[j] 的和。最后别忘了把 f[k] 输出。

学生最容易在①处填错，把 f[1] 当成 0 或 f[2] 当成 1，导致后面递推全歪；也有人把④写成 i 或 i-1，没抓住‘下一个数不超过当前数一半’这个关键约束，把范围算大了；还有的把③写成 f[j]=1，忘了 f[j] 本身是 j 开头的序列总数，不能每次重置为 1。这些坑都会让最终答案错得离谱。

这道题考查的是动态规划（DP）的基础思想：把一个复杂计数问题拆解成子问题，用递推公式一步步算出答案。题目给的是‘倍减序列’，规则很明确：第一个数是 k，后面每个数都不大于前一个数的一半。比如 k=6 时，所有合法序列只有 6 个，题目已经列出来了。我们要做的，就是设计一个数组 f，让 f[i] 表示‘以 i 开头的倍减序列的个数’，然后利用这个定义写出递推关系，最后填对代码里的五个空。

先说①：f[1] 应该填多少？因为序列里的数必须是正整数，所以 f[0] 没有意义，我们只关心 f[1] 到 f[k]。以 1 开头的序列只能是什么？1 后面不能再接任何数了（下一个数必须 ≤ 1/2，但整数里不存在 ≤0.5 的正整数），所以唯一的序列就是 [1] 这一个。因此 f[1] = 1。选项 C 正确。如果填 0 或把 f[2] 填成 1，后面递推就会完全跑偏，这是第一个大坑。

接下来看②：循环的上界应该到哪里？我们要算出 f[1] 到 f[k] 的值，所以 i 必须从 2 一直跑到 k。注意 i 从 2 开始是因为 f[1] 已经确定好了，不需要再递推。因此②填 k，选项 B 正确。有人可能会想‘k 开头的序列第二个数最多到 k/2，所以只要算到 k/2 就行’，但那是错的——我们需要的是 f[k] 本身，而 f[k] 的计算依赖于所有更小的 f[j]，所以必须算到 k。

再看③：在循环里，我们每次先把 f[i] 初始化为 1。为什么是 1？因为以 i 开头的序列，至少有一个：就是只包含 i 这一个数的序列 [i]。后面的序列才会通过递推累加进来。所以③填 f[i] = 1，选项 A 正确。如果写成 f[i] = 0，那连这个最基本的序列都没算进去，结果就会少 1；如果写成 f[j] = 1，那是把内层循环的变量 j 给初始化了，完全不符合逻辑。

然后是④：内层循环的 j 从 1 到多少？这里要抓住倍减序列的核心规则：第二个数 j 必须满足 j ≤ i / 2。也就是说，以 i 开头的序列，第二个数可以取 1, 2, …, floor(i/2)。因此④填 i / 2，选项 D 正确。很多同学会误以为 j 可以取到 i 或 i-1，那是把‘不大于前一个数的一半’这个条件给丢了，导致递推范围过大，算出来的 f[i] 会远远偏大。

最后看⑤：题目要求输出以 k 开头的倍减序列的个数，而我们的数组 f[k] 正好就是答案。所以⑤填 f[k]，选项 D 正确。有人可能会想‘要不要输出 f[k-1] 或 f[1]’，那是混淆了不同起点的序列个数，完全不对。

现在我们把递推关系说清楚：f[i] = 1（单独一个数的序列） + Σ_{j=1}^{i/2} f[j]（所有以 j 开头、且 j ≤ i/2 的序列）。代码里先给 f[i] 赋 1，然后用内层循环把 Σ f[j] 累加进去，正好对应这个公式。

避坑方面，再强调两点：一是千万别把①写成 f[2] = 1，因为 f[2] 需要依赖 f[1] 和 f[0]（但 f[0] 没意义），所以必须先确定 f[1]；二是内层循环的上界一定要用整数除法 i / 2，而不是 i - 1 或 i，否则会把不符合规则的序列也算进去，导致答案错误。

关于考频与趋势：在我所带过的 CSP-J/S 和 GESP 真题库中，这道‘倍减序列’题出自 BCSP-X 2024 第 20 题，属于动态规划入门级别的计数问题。从历年数据看，这类‘给定规则求序列个数’的题目在 CSP-J 中每年稳定出现 1-2 道，GESP 中占比更高，约每 3 场考试就有一道。具体到‘倍减’这个变体，它在 2024 年首次出现在 BCSP-X 中，说明命题人开始倾向于用更贴近实际场景的描述（倍减序列）来包装经典的 DP 递推模型，而不是直接说‘斐波那契’或‘爬楼梯’。往年类似的题目包括：CSP-J 2019 的爬楼梯（f[i] = f[i-1] + f[i-2]）、GESP 2022 的单词拆分（f[i] = Σ f[j]，j 从 1 到 i-1）。这些题的共同点是：先定义 f[i] 为以 i 开头的合法序列数，再根据规则写出递推式。因此，倍减序列题的考频在逐年上升，预计未来 1-2 年内仍会高频出现，只是题目描述可能会换成其他‘减半’或‘取整’规则（比如‘下一个数不超过前一个数的 2/3'）来增加一点变化，但核心思路不变。

预测方面，基于现有数据（仅 2024 年 BCSP-X 出现一次）和历年趋势，我判断这类题在未来 CSP-J/S 或 GESP 中仍会作为必考或高频考点，但命题人可能会在规则上做微调，例如引入‘不能超过前一个数的 2/3'或‘必须是奇数’等额外限制，从而让递推范围不再是简单的 i/2，而是需要结合取整或条件判断。不过，只要抓住‘先定义 f[i]，再根据规则累加 f[j]'这一主线，解题思路就不会偏。如果数据不足以支撑更具体的预测（比如某个特定年份的变体），我就明确说‘暂无足够依据预测’，绝不硬编。

总之，这题的精髓在于：看懂规则 → 定义 f[i] → 写出递推式 → 填对代码。只要按这个心法走，五个空就能稳稳拿下。