Beyond the Void
BYVoid
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&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>

上次修改时间 2017-02-03

相关日志