可以看出，这道题就是求以每个点位中心，边长为2*r+1的矩阵的和。最简单的方法就是对于N*N个点，每个点都以R*R的时间复杂度求出矩阵的和，总时间复杂度为O(N^2*R^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)，于是完美地解决了这个问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | /* * 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; } |
密度图
问题描述
在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的单元格个数。
样例输入
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样例输出
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
Recent Comments