[2019.3.8]BZOJ2241 [SDOI2011]打地鼠

Bertha 。 2022-01-09 05:39 147阅读 0赞

如果我们确定了\\(r\\)和\\(c\\),事实上也确定了打地鼠的方案。

因为所有\\(r\\times c\\)的矩形中,只有1个能覆盖当前还有地鼠的位置组成的图形的角落上的那个洞,所以我们只能在那个角落上砸。

比如,我们目前剩下的地鼠分布为

0 0 0 0

0 0 **1** 2

0 2 1 2

2 2 3 1

那么我们只能以第二行的第三个位置(那个加粗的1)为左上角砸1次。

### 做法1 ###

于是我们可以\\(O(nm)\\)枚举\\(r\\),枚举\\(c\\),然后\\(O(nm)\\)从左到右,从上到下枚举点,然后\\(O(rc)\\)给以当前点为左上角的矩形内的数减去当前点剩下的地鼠数量,寻找\\(r\\times c\\)的最大值。

然而这样做是\\(O(n^3m^3)\\)的。

我们可以做一下二维差分,然后省去了最后给矩形内点减去当前点剩下的地鼠数量的步骤。

二维差分:给一个左上端点为\\((x\_1,y\_1)\\),右下端点为\\((x\_2,y\_2)\\)的矩形加上\\(v\\),需要在差分数组的\\(s\_\{x\_1,y\_1\}\\)和\\(s\_\{x\_2+1,y\_2+1\}\\)加上\\(v\\),给\\(s\_\{x\_1,y\_2+1\}\\)给\\(s\_\{x\_2+1,y\_1\}\\)减去\\(v\\),那么左上端点为\\((1,1)\\),右下端点为\\((x,y)\\)的矩形的和就是点\\((x,y)\\)上的实际值了。

时间复杂度\\(O(n^2m^2)\\)。

code:

#include<bits/stdc++.h> #define Add(u,l,d,r,v) (sum[u][l]+=v,sum[d+1][r+1]+=v,sum[u][r+1]-=v,sum[d+1][l]-=v) using namespace std; int n,m,num[110][110],sum[110][110],ans,t,SUM; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&num[i][j]),SUM+=num[i][j]; for(int r=1;r<=n;++r){ for(int c=1;c<=m;++c){ for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)sum[i][j]=0; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; if(sum[i][j]>num[i][j])goto END; if(sum[i][j]<num[i][j]){ if(i+r-1>n||j+c-1>m)goto END; t=num[i][j]-sum[i][j],Add(i,j,i+r-1,j+c-1,t); } } } ans=max(ans,r*c); END: ; } } printf("%d",SUM/ans); return 0; }

### 做法2 ###

我们枚举\\(r\\),假定\\(c=1\\),计算最大的合法的\\(r\\);

然后假定\\(r=1\\),枚举\\(c\\),计算最大的合法的\\(c\\);

那么\\(r\\times c\\)锤子一定是可行的。

为什么呢?

证明:

我们每次锤的点是目前地鼠数非0的位置组成的图形中最上一行最左一列的点，我们设这个点还有\\(x\\)只地鼠。

首先,以这个点为左上端点,锤一个\\(1\\times c\\)的矩形\\(x\\)次是合法的;

其次,以这一行前\\(c\\)个点每一个为左上端点,各锤一个\\(r\\times 1\\)的矩形\\(x\\)次是合法的。

所以这个\\(r\\times c\\)矩形也就是合法的了。

时间复杂度\\(O((n+m)nm)\\)。

code:

#include<bits/stdc++.h> using namespace std; int n,m,num[110][110],sum[110][110],r,c,t,SUM; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&num[i][j]),SUM+=num[i][j]; for(r=n;r>=1;--r){ for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)sum[i][j]=0; for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){ sum[i][j]+=sum[i-1][j]; if(sum[i][j]>num[i][j])goto END1; if(sum[i][j]<num[i][j]){ if(i+r-1>n)goto END1; else t=num[i][j]-sum[i][j],sum[i][j]+=t,sum[i+r][j]-=t; } } break; END1: ; } for(c=n;c>=1;--c){ for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)sum[i][j]=0; for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){ sum[i][j]+=sum[i][j-1]; if(sum[i][j]>num[i][j])goto END2; if(sum[i][j]<num[i][j]){ if(j+c-1>m)goto END2; else t=num[i][j]-sum[i][j],sum[i][j]+=t,sum[i][j+c]-=t; } } break; END2: ; } printf("%d",SUM/(r*c)); return 0; }

转载于:https://www.cnblogs.com/xryjr233/p/BZOJ2241.html