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

一、问题背景

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

1. 初始有n座体积各异的冰山

2. 每天环境温度变化x（影响所有冰山体积）

3. 可能新增体积为y的冰山

4. 需要计算每日冰山总体积（对998244353取模）

二、核心算法思路

1. 映射统计法：使用map记录各体积冰山的数量

2. 批量处理技巧：按体积分类处理避免逐个操作

3. 边界处理：体积超过k时分裂处理

4. 模运算优化：防止数值溢出

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

#include <iostream>
#include <map>
using namespACe std;

const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, k;
    cin >> n >> m >> k;
    
    map<int, long long> cnt; // 体积->数量映射
    
    // 初始化统计
    for (int i = 0; i < n; ++i) {
        int v;
        cin >> v;
        cnt[v]++;
    }
    
    for (int day = 0; day < m; ++day) {
        int x, y;
        cin >> x >> y;
        
        map<int, long long> new_cnt;
        long long sum = 0;
        
        // 处理现有冰山
        for (auto &[v, num] : cnt) {
            int new_v = v + x;
            if (new_v <= 0) continue;
            
            if (new_v > k) {
                new_cnt[k] = (new_cnt[k] + num) % MOD;
                new_cnt[1] = (new_cnt[1] + (new_v - k) * num) % MOD;
            } else {
                new_cnt[new_v] = (new_cnt[new_v] + num) % MOD;
            }
        }
        
        // 添加新冰山
        if (y > 0) {
            new_cnt[y] = (new_cnt[y] + 1) % MOD;
        }
        
        cnt = move(new_cnt);
        
        // 计算总和
        long long total = 0;
        for (auto &[v, num] : cnt) {
            total = (total + v * num) % MOD;
        }
        
        cout << total << "\n";
    }
    
    return 0;
}

四、关键算法点详解

1. 映射优化：使用map将相同体积的冰山合并处理，避免重复计算

2. 分裂处理：当冰山体积超过k时，自动分裂为1体积的小冰山

3. 每日更新：采用new_cnt临时map确保状态同步更新

4. 模运算处理：在每次加法操作后立即取模，防止数值溢出

五、复杂度分析

• 时间复杂度：O(m * S) S为每日不同体积的数量

• 空间复杂度：O(S) 存储当前冰山状态

六、实际应用场景

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

1. 游戏中的粒子系统模拟

2. 物理仿真中的质量分布计算

3. 资源管理中的分类统计

4. 大数据中的分桶计数

参考：蓝桥杯国赛A组冰山