Rockdu's Blog

题目描述

老蛤有一堆真正的粉丝。 老蛤年迈了。不过好在他有特别多忠实粉丝，愿意献出自己寿命的1s等价交换为他的寿命+1s。 老蛤与粉丝们在一个n×nn×n面积的城市中。老蛤可以吸收距离不超过s的粉丝所提供的寿命。老蛤所在的十字路口(a,b)与粉丝所在的十字路口(c,d)之间距离是|a-c|+|b-d|。 老蛤的洪荒之力会不断变化q次，导致s的值也会变化多次。现在要求你，最聪明的粉丝，计算出对于这q个s，每次处于哪个十字路口可以吸收到最多的寿命以及最多寿命的多少。

输入格式

第一行四个整数n，k,q代表城市面积为n×nn×n，粉丝数目k，q次功力变化； 接下来k行，每行两个整数，为粉丝坐标xi,yixi,yi。 接下来q行，每行一个整数，为当前最大距离s。

输出格式

对于每次s，输出最大吸收寿命。

样例数据

样例下载

数据规模与约定

对于 30%的数据，k≤100, n≤50,q≤5

对于 70%的数据，k≤10000, n≤500,q≤20

对于100%的数据，k≤500000,n≤1000,q≤20,xi, yi≤n, s≤1000000

时间限制：2s2s

空间限制：256MB

仔细斟酌题目大意，其实就是查询一个大小一定的框最多能框进几个点。很简单就可以想到O(n*n*k*q)算法，可以拿30分。

然后我们来思考，由于K实在太大，如果能优化查询岂不美哉。那么能否做到n^2预处理O(1)查询呢？是可以做到的。我们这样考虑，因为曼哈顿距离的出现，所以要求的框框是歪着的，是一个菱形。那么我们何不歪着预处理来支持歪着查询呢？又因为题目所给的是正方形，于是就可以很大方的把原来的正方形矩阵歪着放在一个大的刚好能套下它的正方形矩阵中。这样边长变成了2 * n - 1。就可以进行O(n ^ 2)的预处理和O(1)查询了。代码放在下面：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2005;
int num[maxn][maxn], txn, n, k, q, a, b, x, y, s, mx;

void turn_pos(int x, int y, int &ax, int &ay) {
	int mid = (n >> 1) + 1;
	ay = mid + (y - 1) - (x - 1);
	ax = x + y - 1;
}

int query(int x, int y, int s) {
	int ul[2], dr[2];
	turn_pos(x, y, ul[0], ul[1]);
	ul[0] -= s, ul[1] -= s;
	--ul[0], --ul[1];
	ul[0] = max(ul[0], 0), ul[1] = max(ul[1], 0);
	turn_pos(x, y, dr[0], dr[1]);
	dr[0] += s, dr[1] += s;
	dr[0] = min(dr[0], n), dr[1] = min(dr[1], n);
	return num[dr[0]][dr[1]] - num[ul[0]][dr[1]] - num[dr[0]][ul[1]] + num[ul[0]][ul[1]];
}

int main() {
	scanf("%d%d%d", &txn, &k, &q);
	n = txn * 2 - 1;
	for(register int i = 1; i <= k; ++i) {
		scanf("%d%d", &a, &b);
		turn_pos(a, b, x, y);
		++num[x][y];
	}
	for(register int i = 1; i <= n; ++i) {
		for(register int j = 1; j <= n; ++j) {
			num[i][j] += num[i][j - 1] + num[i - 1][j] - num[i - 1][j - 1];
		}
	}
	for(register int i = 1; i <= q; ++i) {
		scanf("%d", &s);mx = 0;
		for(register int i = 1; i <= txn; ++i) 
			for(register int j = 1; j <= txn; ++j) 
			    mx = max(query(i, j, s), mx);
		printf("%d\n", mx);
	}
	return 0;
}