计蒜客 16445 蒜头君打地鼠 题解【前缀和】

作者: wjyyy 分类: 解题报告 发布时间: 2018-06-23 16:12

点击量:167

 

   前缀和处理45°正方形问题。

 

蒜头君最近迷上了打地鼠,但他发现同时出现在面板上的地鼠太多,于是他想改进一下他的锤子,于是他拿出了一款 k×k 大小的正方形锤子,但是遗憾的是,这个锤子只能斜着砸。如下图所示:

当 k=2 时,若蒜头君敲击黑点,黑点和图中所有蓝色点将一并被敲到。

 

当 k=3时,锤子的图案如下所示:

- - * - -
- * * * -
* * x * *
- * * * -
- - * - -

k 取其他值时以此类推。

 

注意:蒜头君只能敲击面板上的格子,但锤子不一定要全部落在面板内。

 

现在给定一个 n×n 的面板,每个格子可能有地鼠也可能没有地鼠,请编程计算用 k×k 大小锤子敲击时最多能打中多少地鼠。

 

输入输出格式

输入格式:

第一行 2 个整数 n,k,表示面板大小和锤子大小。

 

接下来 n行,每行 n 个整数,若为 1 代表该格子有地鼠,若为 0 代表该格子无地鼠。不会出现其他的数字。

 

输出格式:

输出一个整数,代表最多能砸到的地鼠数。

 

输入输出样例

输入样例#1:
3 2
0 1 1
1 0 1
0 1 0
输出样例#1:
4

说明

对于 50% 的测试数据,满足1≤n≤300,1≤k≤10;

 

对于 80% 的测试数据,满足1≤n≤2000,1≤k≤10;

 

对于 100% 的测试数据,满足 1≤n≤2000,1≤k≤100。

 

   如果挨个枚举找范围内合法的格子,时间复杂度是$ O(N^2K^2)$,可以过50分的数据。如果用普通前缀和优化一下,时间复杂度$ O(N^2K)$,可以拿80分。A掉这个题要求优化掉这个K,那么我们考虑用二维前缀和。

 

   我们原来的图是这样的:(4×4)

○○○○
○○○○
○○○○
○○○○

   我们需要用$ N^2$把它旋转45°,然后做前缀和,旋转后是这样的。

×××○×××
××○×○××
×○×○×○×
○×○×○×○
×○×○×○×
××○×○××
×××○×××

   试着模拟,可以找到原来位置为第i行第j列的点,现在变成了第(i+j-1)行,第(n-i+j)列,用一个新的(大小为2n*2n的)数组存下状态。

 

   我们所能打到的范围,可以手推一下,是所有以圆点为顶点的正方形。而正方形的边长,和没有旋转过的一样,是2*k-1。我们需要枚举每个合法的顶点(圆点),计算以这个点为顶点的边长为2*k-1的正方形前缀和,更新答案,就比较简单了。

 

 

Code:

#include<cstdio>
#include<cstring>
int a[2100][2100];
int b[4100][4100];
long long f[4100][4100];//我为什么要开long long
bool used[4100][4100];
int main()
{
    memset(used,0,sizeof(used));
    f[0][0]=0;
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            b[i+j-1][n-(i-j)]=a[i][j];//旋转
            used[i+j-1][n-(i-j)]=true;
        }
    for(int i=1;i<=2*n-1;i++)
        for(int j=1;j<=2*n-1;j++)
            f[i][j]=b[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
    long long ans=0,sum;
    for(int i=1;i<=2*n-1;i++)
        for(int j=1;j<=2*n-1;j++)
            if(used[i][j])
            {
                sum=f[i+2*k-2][j+2*k-2]-f[i-1][j+2*k-2]-f[i+2*k-2][j-1]+f[i-1][j-1];
                ans=sum>ans?sum:ans;
            }
    printf("%lld\n",ans);
    return 0;
}

 

 

 

 

说点什么

avatar
  Subscribe  
提醒
/* */