Alexandra and COS

Time Limit: 8000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 379    Accepted Submission(s): 85


Problem Description Alexandra and her little brother are playing a game called "Clash of Submarines" (COS, for short). In this game, one can build so many(about 100,000) submarines, and detect and collect underwater treasures.
A submarine use radar to detect treasures. Alexandra's submarines are all face north. For each submarine, its radar can detect treasures between northwest and northeast. For example, the "S" is the submarine, and the "+" is a grid which the submarine can detect, and the "-" is which it cannot detect:
++++-
+++--
-S---
-----
Note: the submarine can also detect the grid it occupies.
To simplify the problem, we build coordinate system on the map. X-axis goes from north to south, and Y-axis from west to east. We define the distance between two points (x1,y1) and (x2,y2) to be max(abs(x1-x2),abs(y1-y2)).
There is something special with the radar. Each submarine has a value D. The submarine can only detect a treasure, if D is a divisor of the distance between the submarine and the treasure. Don't forget any D is a divisor of 0.
Here comes the problem: Given the map of size N*M, and Q submarines' position and D, for each submarine please output the number of treasures it can detect.
Note: in this problem, we only detect treasures and won't collect them, so the submarines don't affect each other.  
Input There are multiple test cases (no more than 30).
For each case, the first line is three positive integers N, M and Q.
Next N lines is a map of size N*M. "X" means treasure and "." means no treasure.
Next Q lines, each line is the description of a submarine. There are three positive integers X, Y, D, which means its position is (X,Y), and its value is D.
1≤N,M≤1000.
1≤Q≤500,000.
1≤X≤N,1≤Y≤M.
1≤D≤1000.
Number of cases with max(N∗M,Q)>1,000 is no more than 3.
Huge data. Fast I/O may be needed.  
Output For each case, output Q lines, each line contains the number of treasures that the current submarine can detect.  
Sample Input 4 5 3 ..... XXXXX XXXXX XXXXX 4 3 1 4 3 2 4 3 3 1 1 1 X 1 1 1  
Sample Output 9 6 1 1  
Source BestCoder Round #19




老周的代码，前缀和！@#￥￥%%%…………&




S： // main.cpp // hdu5110 // // Created by eycia on 14/11/25. // Copyright (c) 2014年 eycia. All rights reserved. // #include #include #include #include using namespace std; int f[36][1005][1005]; int d[1005][1005]; int n, m; inline void init() { int sq = sqrt(n+0.0) + 1; for (int k = 1; k <= sq; k++) { for (int i = 1; i <= n; i++) { if (i-k <= 0) { for (int j = 1; j <= m; j++) { f[k][i][j] = d[i][j] - d[i][j-1]; } continue; } if (i-2*k > 0) { for (int j = 1; j <= k; j++) { if (j+k <= m) { f[k][i][j] = f[k][i-k][j+k] + d[i-k][j+k-1] + d[i-2*k][j-1]; } else { f[k][i][j] = d[i-k][m] + d[i-2*k][m] + f[k][i-2*k][j] - d[i-2*k][j] + d[i-2*k][j-1]; } f[k][i][j] += d[i][j] - d[i][j-1]; } for (int j = k+1; j <= m; j++) { if (j+k <= m) { f[k][i][j] = f[k][i-k][j-k] + f[k][i-k][j+k] - f[k][i-2*k][j] - d[i-k][j-k] + d[i-k][j+k-1]; } else { f[k][i][j] = f[k][i-k][j-k] + d[i-k][m] - d[i-k][j-k] + d[i-2*k][m] - d[i-2*k][j]; } f[k][i][j] += d[i][j] - d[i][j-1]; } } else { for (int j = 1; j <= k; j++) { if (j+k <= m) { f[k][i][j] = f[k][i-k][j+k] + d[i-k][j+k-1]; } else { f[k][i][j] = d[i-k][m]; } f[k][i][j] += d[i][j] - d[i][j-1]; } for (int j = k+1; j <= m; j++) { if (j+k <= m) { f[k][i][j] = f[k][i-k][j-k] + f[k][i-k][j+k] - d[i-k][j-k] + d[i-k][j+k-1]; } else { f[k][i][j] = f[k][i-k][j-k] + d[i-k][m] - d[i-k][j-k]; } f[k][i][j] += d[i][j] - d[i][j-1]; } } } } } int main(int argc, const char * argv[]) { int q; int x, y, dd; char line[1005]; while (scanf("%d %d %d", &n, &m, &q) != EOF) { getchar(); for (int i = 1; i <= n; i++) { gets(line); d[i][0] = 0; for (int j = 1; j <= m; j++) { d[i][j] = d[i][j-1] + (line[j-1] == 'X'); } } init(); for (int i = 0; i < q; i++) { scanf("%d %d %d", &x, &y, &dd); if (dd <= sqrt(n+0.0)) { printf("%d ", f[dd][x][y]); } else { int res = 0; for (int i = 0; x - i * dd > 0; i++) { res = res - d[x - i * dd][max(y - i * dd - 1, 0)] + d[x - i * dd][min(y + i * dd, m)]; } printf("%d ", res); } } } }