当前位置：首页 > news >正文

从CCPC河南省赛H题‘随机栈’出发，手把手教你用C++ STL priority_queue和map实现贪心与模运算

news 2026/4/28 12:23:07

从随机栈问题到STL实战：贪心策略与模运算的竞赛技巧

在算法竞赛中，数据结构的选择和数学技巧的应用往往是解题的关键。本文将以CCPC河南省赛H题"随机栈"为例，深入探讨如何利用C++ STL中的priority_queue和map实现高效的贪心策略，并处理模运算下的概率计算问题。

1. 问题背景与核心思路

随机栈问题描述了一个包含2n次操作的场景：每次操作要么将一个数字放入集合，要么从当前集合中取出一个数字。最终要求取出的数字序列严格递增的概率，结果需要对998244353取模。

这个问题的核心在于：

贪心策略：每次取出当前集合中最小的数字，确保序列递增
概率计算：每次操作时，选择最小数字的概率等于当前集合中最小数字的个数除以集合大小
模运算处理：由于概率涉及分数，需要使用模逆元进行计算

const int mod = 998244353; int quick_mi(int a, int b) { int ans = 1; while(b) { if(b % 2) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; }

2. 数据结构的选择与实现

2.1 使用优先队列维护最小值

priority_queue是C++ STL中实现堆数据结构的容器适配器。在本题中，我们需要一个小根堆来快速获取当前集合中的最小值：

priority_queue<int, vector<int>, greater<int>> min_heap;

每次插入操作直接将数字压入堆中：

min_heap.push(x);

2.2 使用map维护数字出现次数

为了统计每个数字在当前集合中的出现次数，我们使用map来维护：

unordered_map<int, int> count_map;

当插入数字x时：

count_map[x]++;

当取出数字时，我们需要知道当前最小数字的出现次数：

int min_val = min_heap.top(); int cnt = count_map[min_val];

3. 贪心策略的详细实现

贪心算法的正确性基于以下观察：

如果当前取出的数字小于之前取出的最大值，则无法形成递增序列，概率为0
否则，每次必须取出当前最小的数字才能保证后续可能形成递增序列

实现步骤：

初始化最大值为0，分子和分母的累积变量
遍历所有操作：
- 如果是插入操作，更新堆和计数
- 如果是取出操作：
  - 检查当前最小值是否大于之前最大值
  - 更新概率的分子和分母
  - 从堆中移除该数字

int max_so_far = 0; long long numerator = 1, denominator = 1; for(int i = 0; i < 2*n; i++) { if(op[i] > 0) { // 插入操作 min_heap.push(op[i]); count_map[op[i]]++; } else { // 取出操作 int current_min = min_heap.top(); if(current_min < max_so_far) { cout << 0 << endl; return; } max_so_far = max(max_so_far, current_min); numerator = numerator * count_map[current_min] % mod; denominator = denominator * min_heap.size() % mod; count_map[current_min]--; min_heap.pop(); } }

4. 模运算与概率计算

在模数运算下，分数p/q的计算需要转换为p×q⁻¹ mod MOD。这里q⁻¹是q的模逆元，可以使用费马小定理计算：

注意：模逆元仅在模数为质数且与被模数互质时存在

计算最终结果的代码：

long long result = numerator * quick_mi(denominator, mod-2) % mod; cout << result << endl;

5. 常见错误与优化技巧

5.1 常见错误分析

贪心策略错误：尝试其他取数策略而非总是取最小值
概率计算顺序错误：在模运算下，必须先计算分子分母的积，最后统一求逆元
堆与计数不同步：取出数字后忘记更新计数或堆

5.2 性能优化

提前终止：一旦发现当前最小值小于之前最大值，立即返回0
批量处理：可以累积计算分子分母，减少模运算次数
内存预分配：预先分配足够空间给堆和map，避免动态扩容开销

// 优化：预分配内存 min_heap.reserve(n); count_map.reserve(n);

6. 扩展应用与类似问题

这种结合贪心策略和模运算的技巧在竞赛中非常常见，类似的问题包括：

概率期望问题：需要计算大量概率的乘积并对大质数取模
贪心选择问题：需要动态维护当前最优选择
数据结构综合应用：同时需要堆和哈希表的功能

一个类似的经典问题是TopK问题，同样可以使用堆来解决，但不需要模运算部分。

7. 实战演练与代码模板

下面给出完整的解题代码模板，包含所有关键部分：

#include <bits/stdc++.h> using namespace std; const int MOD = 998244353; long long quick_pow(long long a, long long b) { long long res = 1; while(b) { if(b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } void solve() { int n; cin >> n; vector<int> operations(2*n); for(int i = 0; i < 2*n; i++) { cin >> operations[i]; } priority_queue<int, vector<int>, greater<int>> min_heap; unordered_map<int, int> count_map; int max_val = 0; long long p = 1, q = 1; for(int op : operations) { if(op != -1) { min_heap.push(op); count_map[op]++; } else { if(min_heap.empty()) { cout << 0 << '\n'; return; } int current = min_heap.top(); if(current < max_val) { cout << 0 << '\n'; return; } max_val = current; p = p * count_map[current] % MOD; q = q * min_heap.size() % MOD; count_map[current]--; if(count_map[current] == 0) { count_map.erase(current); } min_heap.pop(); } } long long inv_q = quick_pow(q, MOD-2); long long result = p * inv_q % MOD; cout << result << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }