本文正體字版由OpenCC轉換

可以看出，這道題就是求以每個點位中心，邊長爲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