当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5110:Alexandra and COS

题目描述
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.
输入解释
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 \leq N,M \leq 1000$.
$1 \leq Q \leq 500,000$.
$1 \leq X \leq N, 1 \leq Y \leq M$.
$1 \leq D \leq 1000$.
Number of cases with $max(N*M,Q) > 1,000$ is no more than 3.
Huge data. Fast I/O may be needed.
输出解释
For each case, output Q lines, each line contains the number of treasures that the current submarine can detect.
输入样例
4 5 3
.....
XXXXX
XXXXX
XXXXX
4 3 1
4 3 2
4 3 3
1 1 1
X
1 1 1
输出样例
9
6
1
1
来自杭电HDUOJ的附加信息
Recommend heyang

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 BestCoder Round #19

源链接: HDU-5110

最后修改于 2020-10-25T23:19:53+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
8000/5000MS(Java/Others) 262144/262144K(Java/Others)