OneCoder Avatar
OneCodercoderli.com · 1023 篇博文
⌘ NOIP

NOIP 全国联赛真题

🎨 视觉封面

【NOIP真题】2001 数的计算 luogu-P1028 | 适用于 GESP四级 / CSP-J 练习

📅 2026-09-17·✍️ OneCoder·计算中...·⏱️ 10 分钟

从一个正整数出发,每次在左侧追加一个不超过其一半的正整数,这种层层衍生的规则自然勾勒出了一棵递推分支树。洛谷 P1028 [NOIP2001 普及组]《数的计算》是一道经典的树形衍生计数问题。表面上看,它可以通过深度优先搜索或纯递归直接模拟生成过程;但随着数值增大,重叠子问题会导致朴素递归呈指数级爆炸超时。通过前缀和优化将状态递推复杂度压缩到 ,不仅是理解记忆化搜索与动态规划分水岭的绝佳载体,也是 GESP 四级跨越至五级进阶的核心思维跃迁。

luogu-P1028 [NOIP2001 普及组] 数的计算

🔗 洛谷原题传送门:luogu-P1028 [NOIP2001 普及组] 数的计算

题目描述

给出正整数 ,要求按如下方式构造数列:

  1. 只有一个数 的数列是一个合法的数列。
  2. 在一个合法的数列的末尾加入一个正整数,但是这个正整数不能超过该数列最后一项的一半,可以得到一个新的合法数列。

请你求出,一共有多少个合法的数列。两个合法数列 不同当且仅当两数列长度不同或存在一个正整数 ,使得 。

输入格式

输入只有一行一个整数,表示 。

输出格式

输出一行一个整数,表示合法的数列个数。

输入输出样例

输入 #1

Code1 行
6

输出 #1

Code1 行
6

说明/提示

样例 1 解释

满足条件的数列为:

数据规模与约定

对于全部的测试点,保证 。


题目深度剖析

1. 规则转化与数学建模

题目要求以一个给定的自然数 开头,每次可以在当前数列末尾添加一个正整数 ,且该正整数必须满足:

我们需要统计从数字 出发,能够产生的所有合法数列的总数量。

观察构造过程可以发现:后续允许添加的数字集合仅取决于当前数列的末尾数字,而与更早之前添加了哪些数完全无关。这正是典型的“无后效性”特征。

我们定义状态:

  • 设 表示以正整数 为开头的合法数列的总个数。

对于以 开头的任意合法数列,其构成方式分为两类:

  1. 单元素数列:仅由 本身构成的数列,方案数为 ;
  2. 多元素数列:在 后面拼接一个合法正整数 (满足 )。一旦确定了第二项为 ,由于后续的拼接规则完全由 及其后续末尾项决定,因此以 为开头的合法数列共有 种,每一种都可以无缝拼接在 的后面形成以 开头的新合法数列。

综合以上两种情况,我们可以得到严密的数学递推关系式:

边界条件非常直观:

  • 当 时,,求和项为空,故 (仅有数列 );
  • 当 时,,(数列为 );
  • 当 时,,(数列为 );
  • 当 时,,(与样例完全一致)。

2. 算法演进:从指数爆炸到线性递推

在等级考试和信奥入门阶段,许多同学初次接触本题时容易直接写出无记忆化的纯递归函数:

C++8 行
// 错误示范:未经记忆化的朴素递归
int dfs(int x) {
    int ans = 1;
    for (int j = 1; j <= x / 2; ++j) {
        ans += dfs(j);
    }
    return ans;
}
为什么朴素递归会严重超时?

如果对 运行上述纯递归代码,计算 dfs(1000) 需要调用 dfs(500)、dfs(250) 等,而计算 dfs(999) 同样会重复调用 dfs(499)、dfs(249)……子问题被重复展开了天文数字般的次数,其调用树的时间复杂度呈指数级爆炸(),程序将直接卡死并导致 TLE(Time Limit Exceeded)。

自底向上的递推 DP 方案

因为计算 只需要依赖已知比它小的子问题答案 ,我们完全可以采用**自底向上(Bottom-Up)**的双层循环递推:

  • 外层循环遍历 从 到 ;
  • 内层循环遍历 从 到 ,累加已算出的 ;
  • 状态计算完毕后直接保存在数组 f[i] 中。
方案 核心思想 时间复杂度 空间复杂度 洛谷评测结果
朴素无记忆化递归 自顶向下暴力递归展开 指数级 栈空间 严重超时 (TLE)
自底向上线性递推 (DP) 循环自小到大推导,打表保存状态 次运算 数组空间 最优满分 (AC),耗时 < 5ms

在 的数据规模下,内层总计算次数仅为 次加法,现代计算机可在不到 毫秒内瞬时算出!

3. 数据边界与整型溢出防范

在编写算法题解时,必须对数值上限保持高度敏锐:

  • 当 时,经过递推计算得出的 ;
  • 标准 32 位有符号整数 int 的上限为 ;
  • 可以看出, 已经达到了约 ,与 int 最大上限仅差不到 !

如果在累加过程中稍有微小改动或拓展,极易触发 32 位整型上溢。因此,遵循 CCF GESP 及 CSP 优良规范,本题推荐使用 64 位整型 long long 存储状态数组,彻底消除边界溢出隐患。

4. 规范避坑与实现要点

  1. 严禁局部变长数组(VLA):
    • 严禁在 main() 函数内部声明形如 long long f[n + 1]; 的局部数组;
    • 规范做法是在全局数据区声明固定常量与数组:const int MAXN = 1005; long long f[MAXN];。全局数组位于静态存储区,自动初始化为全 0。
  2. 标准竞赛输入输出:
    • 保持主函数输入逻辑干净清晰,直接 cin >> n;,不引入冗余的防御性判断代码;
    • 无需复杂的快读模板,基础 cin/cout 即可轻量级秒杀本题。

完整参考代码 (C++11)

C++40 行
/**
 * Problem: luogu-P1028 [NOIP2001 普及组] 数的计算
 * Algorithm: 基础递推 (Dynamic Programming / Recurrence)
 * Standard: C++11 (CCF GESP 官方大纲规范)
 * Author: OneCoder
 */

#include <iostream>

using namespace std;

// 数据规模保证 1 <= n <= 1000
// f[i] 表示以正整数 i 为起点的所有合法数列总数
// 经推导 f(1000) = 1981471878,极接近 32 位有符号整型上限 (2147483647)
// 在全局数据区开辟静态数组,杜绝局部变长数组 (VLA),使用 long long 确保安全防溢出
const int MAXN = 1005;
long long f[MAXN];

int main() {
    int n;
    // 直接读入目标正整数 n
    cin >> n;

    // 自底向上递推计算每一个子问题的解 (1 到 n)
    for (int i = 1; i <= n; ++i) {
        // 每个数本身作为一个单元素数列 [i],即为 1 种合法方案
        f[i] = 1;

        // 在 i 后面可以追加的正整数 j 必须满足 1 <= j <= i / 2
        // 追加 j 之后,后续所有以 j 为开头的合法数列均可接在其后,故累加 f[j]
        for (int j = 1; j <= i / 2; ++j) {
            f[i] += f[j];
        }
    }

    // 输出以 n 开头的合法数列总数量
    cout << f[n] << endl;

    return 0;
}
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!