OneCoder Avatar
OneCodercoderli.com · 1023 篇博文
【NOIP真题】2003 栈 luogu-P1044 | 适用于 GESP四级 / CSP-J 练习📷 题解插图

【NOIP真题】2003 栈 luogu-P1044 | 适用于 GESP四级 / CSP-J 练习

📅 2026-09-18·✍️ OneCoder·计算中...·⏱️ 15 分钟

后进先出(LIFO)的“栈”结构是计算机底层系统调用的基石,而在有限容量和固定入栈顺序下,究竟能衍生出多少种不同的合法出栈序列?洛谷 P1044 [NOIP2003 普及组]《栈》将这个看似繁复的操作序列计数问题,推向了组合数学最著名的明珠之一——卡特兰数(Catalan Number)。本题既可以用“最后出栈元素划分”建立二维动态规划递推,也可以直接通过折线反射定理推导出闭式组合公式。无论对于 GESP 四级的递推枚举训练,还是 CSP-J 的组合数学认知,这道题目都是连接基础语法与高维数学模型的典范。

luogu-P1044 [NOIP2003 普及组] 栈

🔗 洛谷原题传送门:luogu-P1044 [NOIP2003 普及组] 栈

题目描述

宁宁考虑的是这样一个问题:一个操作数序列,(图示为 1 到 3 的情况),栈 A 的深度大于 。

现在可以进行两种操作,

  1. 将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作)
  2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)

使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3 生成序列 2 3 1 的过程。

(原始状态如上图所示)

你的程序将对给定的 ,计算并输出由操作数序列 经过操作可能得到的输出序列的总数。

输入格式

输入文件只含一个整数 ()。

输出格式

输出文件只有一行,即可能输出序列的总数目。

输入输出样例

输入 #1

Code1 行
3

输出 #1

Code1 行
5

说明/提示

样例 1 解释

对于输入 ,初始序列为 。合法的出栈序列共有 种,分别为:

  • (push 1, pop 1, push 2, pop 2, push 3, pop 3)
  • (push 1, pop 1, push 2, push 3, pop 3, pop 2)
  • (push 1, push 2, pop 2, pop 1, push 3, pop 3)
  • (push 1, push 2, pop 2, push 3, pop 3, pop 1,即题面配图所示过程)
  • (push 1, push 2, push 3, pop 3, pop 2, pop 1)

注:序列 是不可能通过合法入栈出栈得到的,因为若 第一个出栈,说明 均已入栈,此时栈顶必须是 ,不可能先弹出 。因此总方案数为 。

数据规模与约定

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


题目深度剖析

1. 问题本质与数学建模

本题表面上考察的是数据结构“栈”的先进后出(LIFO)操作模拟,但题目并不要求我们输出所有具体的出栈排列,而是询问可能得到的合法出栈序列的总数。这是一个纯粹的组合计数与递推建模问题。

为了理清状态关系,我们需要找到一个能够将规模为 的大问题,不重不漏地拆解为更小规模子问题的“划分基准”。

在所有的合法出栈序列中,原本的操作数 最终都必然要出栈。我们聚焦于最后一个出栈的数是谁:

  • 设元素 ()是整个序列中最后离开栈的那个数;
  • 既然 是最后一个出栈的数,那么在 进栈之后、直到 最终出栈出栈之前,其余所有的数都必须完成各自的进栈与出栈全过程;
  • 又因为操作数是严格按照 的顺序依次由队列头端送入栈中:
    1. 所有比 先进栈的数是 ,共 个数。它们必须在 最终出栈之前就已经全部出栈并进入输出序列;
    2. 所有比 后进栈的数是 ,共 个数。它们在 进栈之后才依次进栈,并且必须在 最终出栈之前全部出栈完毕。

因此,当确定了元素 是最后一个出栈的元素时:

  • 前 个元素自身的进出栈过程构成一个独立的子问题,方案数为 ;
  • 后 个元素自身的进出栈过程同样构成一个独立的子问题,方案数为 ;
  • 这两个子问题在时间与逻辑上是完全解耦且独立的。根据数学中的乘法原理,以 为最后一个出栈元素的总方案数为:

因为元素 可以是 中的任意一个,并且以不同元素作为最后一个出栈元素的方案集互不相交(互斥),根据数学中的加法原理,将所有可能的 对应的方案数求和,即可得到长度为 的出栈序列总数:

令变量代换 ,当 从 遍历到 时, 从 遍历到 ,上式可标准写作:

这就是离散数学与计算机科学中最著名的数列之一——**卡特兰数(Catalan Number)**的标准卷积递推关系式!

2. 卡特兰数的边界与前几项验证

卡特兰数的边界条件约定如下:

  • :空序列对应 个元素的栈操作,唯一的一种合法状态(不进行任何操作);
  • :只有一个元素,直接进栈后出栈,方案数为 。

利用卷积递推式逐步手动推导前几项:

  • : (合法序列:1 2、2 1)
  • : (与样例输出完全一致!)
  • :

3. 算法演进:两种递推思维的碰撞

在 CCF GESP 四级(简单递推)与 CSP-J 学习阶段,掌握多角度建模有助于深入理解动态规划与递推的真谛。对于本题,存在两种经典的解法模型:

视角一:一维卡特兰数卷积递推(推荐解法)
  • 核心思路:直接利用上述推导出的卡特兰数递推式 。
  • 实现方式:自底向上双层循环递推,外层 从 到 ,内层 从 到 ,累乘求和。
  • 优势:逻辑凝练,空间占用仅为 ,代码量极少,是考场上的首选武器。
视角二:二维状态记忆化递推 / 动态规划
  • 核心思路:从栈的操作过程状态出发进行建模。
  • 状态定义:设 表示当前待入栈队列中还有 个数,且栈内部当前存有 个数时的后续合法出栈序列总数。
  • 状态转移:
    • 若栈为空(),此时无法进行出栈操作,必须执行入栈操作:待入栈数减 ,栈内数加 ,即 ;
    • 若栈非空(),此时既可以执行入栈(需满足 ),也可以执行出栈:
  • 边界条件:当队列中已无待入栈元素()时,栈中剩余的 个元素只能唯一按自顶向下顺序依次弹出,方案数固定为 ,即对所有 均有 。
  • 目标解:初始状态为 个元素待入栈、栈为空,即 。
递推方案 建模视角 状态定义 时间复杂度 空间复杂度 适用场景
一维卡特兰卷积递推 宏观数学划分(最后出栈元素) 表示规模为 时的出栈方案数 次计算 一维数组 推荐解法,代码极简,速度极快
二维状态网格递推 微观操作模拟(push/pop 决策) 表示待入栈 个、栈内 个 矩阵递推 二维数组 直观展示状态机转移,教学意义高

在题目给定的数据范围 下,两种方法均在不到 毫秒内瞬时出解,洛谷评测均为最优满分(100 分 AC)。

4. 数据范围与整型边界考量

  • 题目保证 ;
  • 经计算,第 项卡特兰数为:
  • 标准 32 位有符号整型 int 的最大取值范围为 ;
  • 虽然 未超过 int 上限,但乘法累加过程中若涉及更高项(例如 时 , 时 就会彻底爆 int)。
  • 遵循竞赛规范与 CCF 优良习惯,计数类问题统一采用 64 位整型 long long 存储状态数组,彻底消除整型溢出风险。

5. 常见考场避坑点

  1. 切勿遗漏 的边界初值:
    • 很多初学者误以为“没有元素就是 种方案”,从而赋初值 ;
    • 一旦 ,根据卷积公式 ,会导致后续所有项全为 !在组合数学中,空集的方案数定义为 。
  2. 严禁使用局部变长数组(VLA):
    • 不要在 main() 函数内部编写 long long h[n + 1];,这在 C++11 标准与 GESP 官方机考环境下严禁使用;
    • 规范做法是在全局数据区声明固定大小的静态常量数组 const int MAXN = 25; long long h[MAXN];。
  3. 保持输入输出简洁标准:
    • 无需引入繁杂的快读加速模板,直接使用标准 cin >> n; 与 cout << h[n] << endl; 即可。

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

C++44 行
/**
 * Problem: luogu-P1044 [NOIP2003 普及组] 栈
 * Algorithm: 卡特兰数 (Catalan Number) / 卷积递推 (Recurrence)
 * Standard: C++11 (CCF GESP 官方大纲规范)
 * Author: OneCoder
 */

#include <iostream>

using namespace std;

// 数据规模:保证 1 <= n <= 18
// h[i] 表示含有 i 个元素的操作数序列,经过合法的进栈、出栈操作后可能得到的出栈序列总数(即第 i 项卡特兰数)
// 当 n = 18 时,h[18] = 477638700,在 32 位整型范围内,但为防止乘法溢出及遵循规范统一采用 long long
const int MAXN = 25;
long long h[MAXN];

int main() {
    int n;
    // 直接读入操作数序列长度 n
    cin >> n;

    // 边界初始化:
    // 0 个元素(空状态)方案数为 1,1 个元素只有 1 种出栈可能
    // 注意:h[0] 必须初始化为 1,否则后续卷积乘积项将全部退化为 0
    h[0] = 1;
    h[1] = 1;

    // 自底向上递推计算卡特兰数 h[2] 到 h[n]
    // 状态转移方程:h[i] = sum_{j=0}^{i-1} (h[j] * h[i - 1 - j])
    // 物理意义:枚举第 (j + 1) 个元素作为整个序列中“最后一个出栈”的元素,
    // 其前半部分 j 个元素与后半部分 (i - 1 - j) 个元素各自独立构成子卡特兰序列
    for (int i = 2; i <= n; ++i) {
        h[i] = 0; // 初始化当前状态累计和
        for (int j = 0; j < i; ++j) {
            h[i] += h[j] * h[i - 1 - j];
        }
    }

    // 输出包含 n 个数时所有可能的出栈序列总数目
    cout << h[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 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!