题面传送门
首先明确,这是一道差分裸题,不要被它的蓝标签吓到。
算法简介:差分是一种和前缀和类似的数据结构,毕竟在差分过程中要进行前缀和,所以前缀和是差分的基础。差分能做到O(1)修改,但要O(n)查询,适用范围不如前缀和。差分适合查询极少,修改大大多于查询的题目。
算法实现: 首先我们定义差分数组s与基本数组a。
修改:我们要让x=5,y=9区间内加上z=5,那么我们有一个方法:fx+=z;fy+1−=z;
0 0 0 0 5 0 0 0 0 0 -5 0 0 0
查询:那我们要查询x=5,y=9区间,怎么办呢?因为前缀和是差分的基础,所以先做一遍前缀和。
0 0 0 0 5 5 5 5 5 5 0 0 0 0
那么原数组就出来了。
那怎么查询呢?再做一遍前缀和呗!
0 0 0 0 5 10 15 20 25 25 25 25 25 25
再按照前缀和用ay−ax−1=25−0=25即得答案。
按照前缀和的思路,二维差分怎么办?怎么修改x1=2,y1=5到x2=4,y2=7使其加上z=5?
首先根据套路,ax,y肯定要修改,那剩余怎么办?怎么推?
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
那先做一遍前缀和吧!
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 5 5 5 5 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
做到这里时不对了,a2,8不应该有数值,所以在a2,8上放一个−z。
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0 0 0 0 0 0 0
又不对了,a5,5不应该有数值,所以还要在a5,5上放一个−z
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 0 0 0 -5 0 0 0 0 0 0
但a5,8不应该有负数啊,所以亡羊补牢地在a5,8补上一个z。
所以二维差分修改就是:
ax1,y1+=z
ax1,y2+1−=z
ax2+1,y1=z
ax2+1,y2+1+=z
有感觉和前缀和有点相似。
两个基础数据结构都指向了同一个数学模型:韦恩图!
那么对于这道题,只要枚举锤子的长和宽再枚举每一个点进行二维差分就好了。
个人理解: 差分数组的修改是个很好的方法,但它的代价是复杂的查询。若有其他东西来维护差分数组的查询就很好了。
代码实现:
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,a[239][239],b[239][239];
int main(){
register int i,j,x,y,l,r,ans=0,tot,flag;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++) scanf("%d",&a[i][j]),ans+=a[i][j];
}
for(i=n;i>=1;i--){
for(j=m;j>=1;j--){
if(ans%i==0&&ans%j==0){
flag=0;
memset(b,0,sizeof(b));
for(x=1;x<=n;x++){
for(y=1;y<=m;y++){
b[x][y]+=b[x-1][y]+b[x][y-1]-b[x-1][y-1];
if(a[x][y]<b[x][y]){flag=1;break;}
b[x+i][y]-=a[x][y]-b[x][y];
b[x][y+j]-=a[x][y]-b[x][y];
b[x+i][y+j]+=a[x][y]-b[x][y];
b[x][y]=a[x][y];
}
if(flag) break;
}
if(!flag){
printf("%d",ans/i/j);
return 0;
}
}
}
}
}
题面传送门
这道题是提高组原题,可以用线段树维护区间中是否有少于0的数字,而且思路更简单,但对于差分数组的进一步了解还是很有帮助的。
对于这道题,用二分分出哪一个订单不满足要求,并用差分数组验证,最后是一遍查询。时间复杂度O(nlog2n)
#include<bits/stdc++.h>
using namespace std;
int n,m,s[1000001],d[1000001],q[1000001],a[1000001],b[1000001],c[1000001],l,r,mid,flag;
int main() {
//freopen("1.in","r",stdin);
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++) scanf("%d",&s[i]);
for(register int i=1;i<=m;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
l=0,r=m+1;
while(l+1<r){
flag=0;
memset(d,0,sizeof(d));
mid=(l+r)>>1;
for(register int i=1;i<=mid;i++) d[b[i]]+=a[i],d[c[i]+1]-=a[i];
for(register int i=1;i<=n;i++){
d[i]+=d[i-1];
if(d[i]>s[i]){flag=1;break;}
}
if(flag) r=mid;
else l=mid;
}
if(l==m) printf("0");
else printf("-1\n%d",r);
return 0;
}