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天前
|
算法 测试技术 C++
【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II
【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II
|
2天前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-48 算法训练 关联矩阵
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-48 算法训练 关联矩阵
38 0
|
2天前
|
算法 测试技术 C#
【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II
【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II
|
2天前
|
算法
【免费】面向多微网网络结构设计的大规模二进制矩阵优化算法
【免费】面向多微网网络结构设计的大规模二进制矩阵优化算法
|
2天前
|
算法 测试技术 编译器
【算法 | 实验18】在字符矩阵中查找给定字符串的所有匹配项
题目描述 题目 在字符矩阵中查找给定字符串的所有匹配项 给定一个M×N字符矩阵,以及一个字符串S,找到在矩阵中所有可能的连续字符组成的S的次数。所谓的连续字符,是指一个字符可以和位于其上下左右,左上左下,右上右下8个方向的字符组成字符串。用回溯法求解。
38 1
|
2天前
|
人工智能 算法
基础算法--前缀和与差分
基础算法--前缀和与差分
|
2天前
|
算法 测试技术 C++
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
|
2天前
|
算法 C++
【动态规划】【矩阵】C++算法329矩阵中的最长递增路径
【动态规划】【矩阵】C++算法329矩阵中的最长递增路径
|
2天前
|
人工智能 移动开发 算法
算法基础:前缀和与差分
算法基础:前缀和与差分
48 1
算法基础:前缀和与差分
|
2天前
|
算法
算法题—顺时针打印矩阵
算法题—顺时针打印矩阵
24 0