04077: 出栈序列统计

http://cs101.openjudge.cn/practice/04077/

栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。

输入

就一个数n(1≤n≤15)。

输出

一个数，即可能输出序列的总数目。

样例输入

样例输出

提示

先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。　　用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。

这是一个经典的栈操作模拟问题。我们需要统计对于从 1 到 n 的数字，所有可能的出栈序列数量。这个问题的本质就是 栈的合法出栈序列个数问题。

这个数量恰好是 第 n 个卡特兰数（Catalan Number），其定义为：

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})

或者通过递归模拟也可以得到。下面我们给出递归+回溯的写法，逐个模拟进栈和出栈的操作。

✅ Python 代码如下：

python

def count_sequences(n):
    def dfs(push_num, stack, popped):
        nonlocal count
        # 如果已经弹出了 n 个数，说明这个出栈序列是合法的
        if popped == n:
            count += 1
            return
        # 尝试进栈：如果还有数字没进栈
        if push_num <= n:
            stack.append(push_num)
            dfs(push_num + 1, stack, popped)
            stack.pop()
        # 尝试出栈：如果栈不空
        if stack:
            top = stack.pop()
            dfs(push_num, stack, popped + 1)
            stack.append(top)

    count = 0
    dfs(1, [], 0)
    return count

# 读取输入
n = int(input())
print(count_sequences(n))

✅ 拓展：卡特兰数法（更高效）

你也可以直接用卡特兰数公式来快速计算：

python

import math

def catalan_number(n):
    return math.comb(2 * n, n) // (n + 1)

n = int(input())
print(catalan_number(n))

两种方法都可以，递归方式更直观模拟操作，适合理解；卡特兰数方法更高效，适合大 n（比如 n = 15）时使用。

python

"""
尝试所有可能的进栈和出栈顺序，并统计满足条件的序列数量。
当进栈次数和出栈次数都达到n时，即得到一个有效的出栈序列，计数器加1
"""
def count_stack_sequences(n):
    def backtrack(open_count, close_count):
        if open_count == n and close_count == n:
            return 1
        total_count = 0
        if open_count < n:
            total_count += backtrack(open_count + 1, close_count)
        if close_count < open_count:
            total_count += backtrack(open_count, close_count + 1)
        return total_count

    return backtrack(0, 0)

if __name__ == "__main__":
    n = int(input())
    result = count_stack_sequences(n)
    print(result)

加lru_cache就快了，相当于dp。n=15,也是瞬间出。

python

"""
尝试所有可能的进栈和出栈顺序，并统计满足条件的序列数量。
当进栈次数和出栈次数都达到n时，即得到一个有效的出栈序列，计数器加1
"""

from functools import lru_cache

def count_stack_sequences(n):
    
    @lru_cache(None)
    def backtrack(open_count, close_count):
        if open_count == n and close_count == n:
            return 1
        total_count = 0
        if open_count < n:
            total_count += backtrack(open_count + 1, close_count)
        if close_count < open_count:
            total_count += backtrack(open_count, close_count + 1)
        return total_count

    return backtrack(0, 0)

if __name__ == "__main__":
    n = int(input())
    result = count_stack_sequences(n)
    print(result)

04078: 实现堆结构

http://cs101.openjudge.cn/practice/04078/

定义一个数组，初始化为空。在数组上执行两种操作：

1、增添1个元素，把1个新的元素放入数组。

2、输出并删除数组中最小的数。

使用堆结构实现上述功能的高效算法。

输入

第一行输入一个整数n，代表操作的次数。每次操作首先输入一个整数type。当type=1，增添操作，接着输入一个整数u，代表要插入的元素。当type=2，输出删除操作，输出并删除数组中最小的元素。 1<=n<=100000。

输出

每次删除操作输出被删除的数字。

样例输入

样例输出

提示

每组测试数据的复杂度为O(nlogn)的算法才能通过本次，否则会返回TLE(超时) 需要使用最小堆结构来实现本题的算法

练习自己写个BinaryHeap。当然机考时候，如果遇到这样题目，直接import heapq。手搓栈、队列、堆、AVL等，考试前需要搓个遍。

python

class BinaryHeap:
    def __init__(self):
        self._heap = []

    def _perc_up(self, i):
        while (i - 1) // 2 >= 0:
            parent_idx = (i - 1) // 2
            if self._heap[i] < self._heap[parent_idx]:
                self._heap[i], self._heap[parent_idx] = (
                    self._heap[parent_idx],
                    self._heap[i],
                )
            i = parent_idx

    def insert(self, item):
        self._heap.append(item)
        self._perc_up(len(self._heap) - 1)

    def _perc_down(self, i):
        while 2 * i + 1 < len(self._heap):
            sm_child = self._get_min_child(i)
            if self._heap[i] > self._heap[sm_child]:
                self._heap[i], self._heap[sm_child] = (
                    self._heap[sm_child],
                    self._heap[i],
                )
            else:
                break
            i = sm_child

    def _get_min_child(self, i):
        if 2 * i + 2 > len(self._heap) - 1:
            return 2 * i + 1
        if self._heap[2 * i + 1] < self._heap[2 * i + 2]:
            return 2 * i + 1
        return 2 * i + 2

    def delete(self):
        self._heap[0], self._heap[-1] = self._heap[-1], self._heap[0]
        result = self._heap.pop()
        self._perc_down(0)
        return result

    def heapify(self, not_a_heap):
        self._heap = not_a_heap[:]
        i = len(self._heap) // 2 - 1    # 超过中点的节点都是叶子节点
        while i >= 0:
            #print(f'i = {i}, {self._heap}')
            self._perc_down(i)
            i = i - 1



n = int(input().strip())
bh = BinaryHeap()
for _ in range(n):
    inp = input().strip()
    if inp[0] == '1':
        bh.insert(int(inp.split()[1]))
    else:
        print(bh.delete())

04077: 出栈序列统计 ​

04078: 实现堆结构 ​

04077: 出栈序列统计

04078: 实现堆结构