POI 2001 Density Map 密度图
可以看出,这道题就是求以每个点位中心,边长为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<=R<N<=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>
上次修改时间 2017-02-03