ACM算法训练【差分矩阵】

简介: ACM算法训练【差分矩阵】


题目


4d40fbcf9e564b2981c5cc339d9c2536.png


数据范围


abc8c1dcf792455ea8ff0ad2f9b79bcd.png


样例


1a6dc5cbac814d048b74a184b16edb13.png


代码


4dc49d69590b443f838d27a7f1a23b7a.png


#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N],b[N][N];
void insertCF(int x1,int y1,int x2,int y2,int c)  //差分核心操作
{
    b[x1][y1]+=c;
    b[x1][y2+1]-=c;
    b[x2+1][y1]-=c;
    b[x2+1][y2+1]+=c;
}
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)   //使用插入的方式构造差分数组
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            insertCF(i,j,i,j,a[i][j]);
        }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        insertCF(x1,y1,x2,y2,c);  //构造差分
    }
    for(int i=1;i<=n;i++)    //求二维前缀和
        for(int j=1;j<=m;j++)
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
    for(int i=1;i<=n;i++)  
    {
        for(int j=1;j<=m;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    return 0;
}
目录
相关文章
|
2月前
|
算法
|
3月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
4月前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
4月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
251 0
|
4月前
|
机器学习/深度学习 算法 搜索推荐
django调用矩阵分解推荐算法模型做推荐系统
django调用矩阵分解推荐算法模型做推荐系统
69 4
|
4月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
165 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
4月前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
|
4月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
4月前
|
算法 C++
蓝桥 算法训练 共线(C++)
蓝桥 算法训练 共线(C++)
|
4月前
|
算法 Java C++
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)

热门文章

最新文章