25、肖恩的投球游戏加强版.docx

解题思路

本题需要求解在一个?n×m?的矩阵球筐中，每个格子最开始的球的个数为?ai,j。进行?q?次操作后，每个格子的球的个数。每次操作给出五个整数?cx1,y1,x2,y2,c，表示以(x1,y1)?为左上角(x2,y2)?为右下角的子矩阵的所有格子都投入?c?个球。为了解决这个问题，我们可以使用二维差分的方法。

二维差分定义和推导过程

二维差分数组是一种用于记录矩阵局部区域的变化的数组。设有一个矩阵?aa，我们定义差分数组?s?如下：

si,j=ai,j?ai?1,j?ai,j?1+ai?1,j?1

这里的差分数组记录了从矩阵的?(1,1)?到?(i,j)?的矩形区域所发生的变化。

对于本题，我们需要在一个子矩阵中同时修改多个格子的值。差分数组的优势在于，我们可以通过修改差分数组的边界值，来实现对子矩阵内所有格子的值的同时修改。

具体地，当我们需要给子矩阵(x1,y1)?到(x2,y2)?中的每个格子都加上?cc?时，我们可以对差分数组进行如下操作：

s_{x_1,y_1}+=csx1,y1+=c

s_{x_1,y_2+1}-=csx1,y2+1?=c

s_{x_2+1,y_1}-=csx2+1,y1?=c

s_{x_2+1,y_2+1}+=csx2+1,y2+1+=c

经过这样的操作，我们实际上在差分数组中标记了一个子矩阵区域的变化。最后，我们需要根据差分数组恢复原矩阵，以得到最终每个格子的球的个数。

恢复原矩阵的方法如下：

ai,j=ai?1,j+ai,j?1?ai?1,j?1+si,j

可以看到，恢复原矩阵的过程是通过累加差分数组的值来完成的。

实现和复杂度分析

根据上述方法，我们可以实现如下算法：

初始化矩阵?aa?和差分数组?ss；

读入矩阵?aa?的初始值，并更新差分数组?ss；

进行?qq?次操作，每次操作根据给定的子矩阵边界和?cc，更新差分数组?ss；

根据差分数组?ss?恢复原矩阵?aa；

输出原矩阵?aa。

算法的时间复杂度为?O(nm+q)，因为我们需要遍历整个矩阵，然后进行?q?次操作。每次操作的时间复杂度为常数级别，因为我们只需要修改差分数组的边界值。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

typedeflonglongLL;

constintN=1010;

LLa[N][N],s[N][N];

intn,m,q;

voidinsert(intx1,inty1,intx2,inty2,intc){

s[x1][y1]+=c;

s[x1][y2+1]-=c;

s[x2+1][y1]-=c;

s[x2+1][y2+1]+=c;

}

intmain(){

ios_base::sync_with_stdio(false);

cin.tie(0);cout.tie(0);

cinnmq;

for(inti=1;i=n;++i){

for(intj=1;j=m;++j){

cina[i][j];

insert(i,j,i,j,a[i][j]);

}

}

while(q--0){

intx1,y1,x2,y2,c;

cinx1y1x2y2c;

insert(x1,y1,x2,y2,c);

}

//求原数组

for(inti=1;i=n;i++){

for(intj=1;j=m;j++){

a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+s[i][j];

couta[i][j];

}

cout\n;

}

return0;

}

Java

importjava.io.*;

importjava.util.*;

publicclassMain{

staticfinalintN=1010;

staticlong[][]a=newlong[N][N];

staticlong[][]s=newlong[N][N];