蓝桥杯2021国赛A组冰山问题：冰山模拟问题的映射统计解法

19339201706

一、问题背景

题目模拟了冰山的每日变化过程：

• 初始有n座体积各异的冰山
• 每天环境温度变化x（影响所有冰山体积）
• 可能新增体积为y的冰山
• 需要计算每日冰山总体积（对998244353取模）
  
  

二、核心算法思路

• 映射统计法：使用map记录各体积冰山的数量
• 批量处理技巧：按体积分类处理避免逐个操作
• 边界处理：体积超过k时分裂处理
• 模运算优化：防止数值溢出
  
  

三、完整代码解析（带注释）

1. #include <iostream>
   
2. #include <map>
   
3. using namespACe std;
   
4. 
   
5. const int MOD = 998244353;
   
6. 
   
7. int main() {
   
8.     ios::sync_with_stdio(false);
   
9.     cin.tie(nullptr);
   
10.    
    
11.     int n, m, k;
    
12.     cin >> n >> m >> k;
    
13.    
    
14.     map<int, long long> cnt; // 体积->数量映射
    
15.    
    
16.     // 初始化统计
    
17.     for (int i = 0; i < n; ++i) {
    
18.         int v;
    
19.         cin >> v;
    
20.         cnt[v]++;
    
21.     }
    
22.    
    
23.     for (int day = 0; day < m; ++day) {
    
24.         int x, y;
    
25.         cin >> x >> y;
    
26.         
    
27.         map<int, long long> new_cnt;
    
28.         long long sum = 0;
    
29.         
    
30.         // 处理现有冰山
    
31.         for (auto &[v, num] : cnt) {
    
32.             int new_v = v + x;
    
33.             if (new_v <= 0) continue;
    
34.             
    
35.             if (new_v > k) {
    
36.                 new_cnt[k] = (new_cnt[k] + num) % MOD;
    
37.                 new_cnt[1] = (new_cnt[1] + (new_v - k) * num) % MOD;
    
38.             } else {
    
39.                 new_cnt[new_v] = (new_cnt[new_v] + num) % MOD;
    
40.             }
    
41.         }
    
42.         
    
43.         // 添加新冰山
    
44.         if (y > 0) {
    
45.             new_cnt[y] = (new_cnt[y] + 1) % MOD;
    
46.         }
    
47.         
    
48.         cnt = move(new_cnt);
    
49.         
    
50.         // 计算总和
    
51.         long long total = 0;
    
52.         for (auto &[v, num] : cnt) {
    
53.             total = (total + v * num) % MOD;
    
54.         }
    
55.         
    
56.         cout << total << "\n";
    
57.     }
    
58.    
    
59.     return 0;
    
60. }

复制代码

四、关键算法点详解

• 映射优化：使用map将相同体积的冰山合并处理，避免重复计算
• 分裂处理：当冰山体积超过k时，自动分裂为1体积的小冰山
• 每日更新：采用new_cnt临时map确保状态同步更新
• 模运算处理：在每次加法操作后立即取模，防止数值溢出
  
  

五、复杂度分析

• 时间复杂度：O(m * S) S为每日不同体积的数量
• 空间复杂度：O(S) 存储当前冰山状态
  
  

六、实际应用场景

这种映射统计方法广泛应用于：

• 游戏中的粒子系统模拟
• 物理仿真中的质量分布计算
• 资源管理中的分类统计
• 大数据中的分桶计数
  
  

来源：蓝桥杯2021国赛A组冰山问题：冰山模拟问题的映射统计解法