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

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

3个月前 (06-22)

【蓝桥杯国赛A组】冰山体积计算:动态规划与map统计的解题方案(洛谷P8767) 蓝桥杯国赛 冰山体积计算 动态规划 map统计 取模运算  第1张

一、题目解读

本题为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;
}

五、总结

本题关键在于利用map动态维护冰山状态,通过拆分超限体积实现“化整为零”的统计策略。代码亮点包括:

1. 模块化处理流程(初始化→每日迭代→状态转移)。

2. 取模运算贯穿始终,确保大数计算正确性。

3. 避免显式循环遍历所有冰山,转而统计数量优化效率。

掌握此类动态规划+map组合思路,可高效解决类似区间拆分与统计问题。


原创内容 转载请注明出处

分享给朋友:

相关文章

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

一、题目解读CSP-J 2019年的“公交换乘”题目(洛谷P5661)要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券,而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记...

力扣931题最小下降路径和解析 动态规划解法 LeetCode解题技巧

力扣931题最小下降路径和解析 动态规划解法 LeetCode解题技巧

一、题目解读力扣931题「Minimum Falling Path Sum」(最小下降路径和)要求在一个n x n的整数矩阵中,计算从顶部到底部的最小路径和。路径只能从每个位置向下或对角线移动(即向下...

牛客网288555题解题指南:动态规划求解小红的暑假(附代码解析)

牛客网288555题解题指南:动态规划求解小红的暑假(附代码解析)

一、题目解读牛客网288555题要求解决一个组合数学问题:有三位朋友,每天需邀请其中一位参加聚会,但不能连续两天邀请同一位朋友。给定天数n,求满足条件的不同邀请方案总数。题目考察动态规划、状态转移及组...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。