盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5110 Alexandra and COS(dp+分块)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5110

题意

有一张n*m的地图,其中一些格点上有宝藏。现在有一种探测器,只能够探测到其前方西北到东北距离为d的倍数的格点,定义该距离max(|x1-x|,|y1-y|)。现在给q个探测器,分别求出其能够探测到的宝石数量。1≤n,m,d≤1000,1≤q≤500000

思路

直接暴力的做时间复杂度为qncase, 会超时。
需要用分块的方式来做。g[d][n][m]表示在(n,m)点,距离为d的数量。
那么可以用右三角形-左三角形, 即g[d][x][y] = gr[d][x][y] - gl[d][x -1][y]
当d比sqrt(n)小时,可以预处理出来复杂度为nmsqrt(n),反之可以直接暴力算

代码

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
int n, m, q, x, y, d, B;
int a[1010][1010], sa[1010][33], gl[1010][1010], gr[1010][1010], g[33][1010][1010];
//a[i][j]表示第i行的前j个和 sa[i][j]表示从i行其前i行间距为j的和
//gl[i][j]表示以(i,j)为边界的左三角形和 gr表示右三角形和 两者相减为g
char ch;
void work() {
int ans = 0;
for (int i = x; i > 0; i -= d) {
int L = max(1, y - x + i), R = min(m, y + x - i);
ans += a[i][R] - a[i][L - 1];
}
printf("%d\n", ans);
}
void solve() {
B = sqrt(0.5 + n);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= B; ++j) {
if (i < j) sa[i][j] = a[i][m];
else sa[i][j] = sa[i - j][j] + a[i][m];
}
for (int k = 1; k <= B; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
//gl
if (i <= k || j <= k) gl[i][j] = a[i][j];
else gl[i][j] = gl[i - k][j - k] + a[i][j];
//gr
if (i <= k) gr[i][j] = a[i][j];
else if (j + k > m) gr[i][j] = sa[i - k][k] + a[i][j];
else gr[i][j] = gr[i - k][j + k] + a[i][j];
//g
g[k][i][j] = gr[i][j] - gl[i][j - 1];
}
}
}
}
char str[1111];
int main() {
while(~scanf("%d%d%d", &n, &m, &q)) {
for (int i = 1; i <= n; ++i) {
scanf("%s", str + 1);
a[i][0] = 0;
for (int j = 1; j <= m; ++j) {
a[i][j] = a[i][j - 1];
if (str[j] == 'X') ++a[i][j];
}
}
solve();
while(q--) {
scanf("%d%d%d", &x, &y, &d);
if (d > B) work();
else printf("%d\n", g[d][x][y]);
}
}
return 0;
}