当前位置：首页 > 蓝桥杯 > 【蓝桥杯国赛A组】冰山体积计算：动态规划与map统计的解题方案（洛谷P8767）

【蓝桥杯国赛A组】冰山体积计算：动态规划与map统计的解题方案（洛谷P8767）

2个月前 (06-22)

一、题目解读

本题为2021年蓝桥杯国赛A组题目“冰山”（洛谷P8767），要求处理冰山在融化与新生成过程中的体积变化。每日存在两种操作：冰山体积按固定值x融化（体积不足x的部分视为完全融化），以及新增体积为y的新冰山。需计算每日剩余冰山的总体积，并对结果取模防止溢出。题目考察动态规划思维与高效数据结构设计。

二、解题思路

采用动态规划+map统计的核心思想：

1. 利用map存储不同体积冰山的数量（体积→数量映射），避免重复计算。

2. 每日迭代时，对现有冰山按融化规则更新体积：

若融化后体积≤0则忽略，>k则拆分为k和剩余部分，≤k则直接记录。

新增冰山直接累加对应体积数量。

3. 循环结束后，遍历map计算总体积并取模。

4. 时间复杂度O(n+m)，空间复杂度O(k)，满足比赛要求。

三、解题步骤

1. 初始化：输入n个初始冰山体积，统计至map。

2. 每日处理：

○ 按融化规则遍历现有冰山，更新新map（new_cnt）。

○ 若新增体积y>0，则新map对应项+1。

○ 交换新旧map完成状态转移。

3. 计算总和：遍历new_cnt，累加体积×数量并取模。

4. 输出当日结果，循环m天。

四、代码与注释

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

const int MOD = 998244353; // 取模常数防溢出

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加快IO速度

    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); // 状态转移
        
        // 计算总和
        for (auto &[v, num] : cnt) {
            sum = (sum + v * num) % MOD;
        }
        
        cout << sum << "\n"; // 输出当日结果
    }
    
    return 0;
}