This post is written in Chinese. Please consider using Google Translate

可以看出，这道题就是求以每个点位中心，边长为2r+1的矩阵的和。最简单的方法就是对于NN个点，每个点都以RR的时间复杂度求出矩阵的和，总时间复杂度为O(N^2R^2)。其实许多次的计算都是冗余的，我们可以类比求最大子矩阵的方法，充分利用已有的值，快速求出矩阵的和。

首先把二维的矩阵压缩为一个一维的序列，即把每k列以第i行为中心[i-r,i+r]的和算出，保存在S[k]中。然后求以第j个位中心，S[k-r]..S[k+r]的和Sum，Sum的值就是对应的W[i,j]的值。当求W[i,j+1]的值时，就不必再重新全部计算，只需考虑它与W[i,j]的增量，即W[i,j+1]=W[i,j]+S[j+r+1]-S[j-r-1]。当换行的时候，只需计算W[i,1]的值即可。这样，由每一行的第一个值推出这一行的所有值，可以大大缩短时间。时间复杂度为O(N^2)，于是完美地解决了这个问题。

/* 
 * Problem: POI2001 map
 * Author: Guo Jiabao
 * Time: 2009.1.5 21:42
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAX=252;

int N,r;
int A[MAX][MAX];
int S[MAX];

void init()
{
    freopen("map.in","r",stdin);
    freopen("map.out","w",stdout);
    scanf("%d%d",&N,&r);
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            scanf("%d",&A[i][j]);
}

void solve()
{
    int i,j,a,b,U;
    a=1;
    if ((b=1+r)>N) b=N;
    for (i=1;i<=N;i++)
    {
        S[i]=0;
        for (j=a;j<=b;j++)
            S[i]+=A[j][i];
    }
    for (i=1;i<=N;i++)
    {
        if (i>1)
        {
            for (j=1;j<=N;j++)
            {
                if (i-r-1>=1)
                    S[j]-=A[i-r-1][j];
                if (i+r<=N)
                    S[j]+=A[i+r][j];
            }
        }
        U=0;
        for (j=a;j<=b;j++)
            U+=S[j];
        printf("%d",U);
        for (j=2;j<=N;j++)
        {
            if (j-r-1>=1)
                U-=S[j-r-1];
            if (j+r<=N)
                U+=S[j+r];
            printf(" %d",U);
        }
        putchar('n');
    }
}

int main()
{
    init();
    solve();
    return 0;
}

<h2><span class="mw-headline">密度图 </span></h2>

问题描述

在ByteLand上有一块地区，蕴藏了ByteLand上最珍贵的Bit矿物质。科学家们将这块地区划分成了N×N个相同大小的单元格， 并对每个单元格进行了考察研究：有的单元格中有丰富的Bit矿物质——科学家用1来标识；有的单元格蕴藏的矿物质很少——科学家用0来标识。

假设用W(i,j)和F(i’,j’)来分别表示两个单元格。那么它们之间的距离被定义为：max(|i - i'|, |j - j'|)，例如W(1,3)和F(4,2)的距离为3。

鉴于可持续发展的思想和开采能力的限制，ByteLand当局计划以一块单元格为中心，开采与中心距离不超过R的所有单元格内的矿藏。为了选定一个合适的单元格作中心，当局希望能够预先了解：以任意一个单元格为中心时，开采量的情况。

于是，当局将一张矿藏地图交给你，上面的N×N个单元格中包含数字0或1。你被要求根据这张矿藏地图，绘制出相应的“矿藏密度图”，分别以每块单元格为中心，计算与中心距离不超过R的所有标识为1的单元格个数。

输入文件

第一行有两个数字N和R（0&lt;=R&lt;N&lt;=250）。

以下N行，每行N个数字。第i+1行第j个数字为单元格(i,j)的标识——0或1。

输出文件

输出文件有N行，每行N个数字。第i行第j个数字表示：与(i,j)距离不超过R的所有标识为1的单元格个数。

样例输入
<pre>5 1
1 0 0 0 1
1 1 1 0 0
1 0 0 0 0
0 0 0 1 1
0 1 0 0 0</pre>
样例输出
<pre>3 4 2 2 1
4 5 2 2 1
3 4 3 3 2
2 2 2 2 2
1 1 2 2 2</pre>