题目详情题解（0）讨论（0）提交记录（0）

AT_abc260_g.[ABC260G] Scalene Triangle Area

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 N×NN \times N 的网格，我们称从上往下第 ii 行，从左往右第 jj 列的格子为 (i,j)(i,j)。
每个格子上至多放有 11 个棋子。
网格的状态由 NN 个字符串 SiS_i 给出：

  • 当 SiS_i 的第 jj 个字符为 O 时，表示 (i,j)(i,j) 上有 11 个棋子；
  • 当 SiS_i 的第 jj 个字符为 X 时，表示 (i,j)(i,j) 上没有棋子。

给定整数 MM。对于放在 (s,t)(s,t) 的棋子 PP，定义 PP 能“守护”的格子 (u,v)(u,v) 满足以下所有条件：

  • s≤u≤Ns \le u \le N
  • t≤v≤Nt \le v \le N
  • (u−s)+(v−t)2<M(u-s) + \frac{(v-t)}{2} < M

现在给定 QQ 个格子 (Xi,Yi)(X_i, Y_i)，请你求出每个格子被多少个棋子守护。

输入格式

输入按以下格式从标准输入给出。

NN MM
S1S_1
S2S_2
⋮\vdots
SNS_N
QQ
X1X_1 Y1Y_1
X2X_2 Y2Y_2
⋮\vdots
XQX_Q YQY_Q

输出格式

输出 QQ 行。
第 ii 行输出格子 (Xi,Yi)(X_i, Y_i) 被守护的棋子数量。

输入输出样例

  • 输入#1

    4 2
OXXX
XXXX
XXXX
XXXX
6
1 1
1 4
2 2
2 3
3 1
4 4

    输出#1

    1
1
1
0
0
0

  • 输入#2

    5 10
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
5
1 1
2 3
3 4
4 2
5 5

    输出#2

    1
6
12
8
25

  • 输入#3

    8 5
OXXOXXOX
XOXXOXOX
XOOXOOXO
OXOOXOXO
OXXOXXOX
XOXXOXOX
XOOXOOXO
OXOOXOXO
6
7 2
8 1
4 5
8 8
3 4
1 7

    输出#3

    5
3
9
14
5
3

说明/提示

数据范围

  • N,M,Xi,Yi,QN, M, X_i, Y_i, Q 为整数
  • 1≤N≤20001 \le N \le 2000
  • 1≤M≤2N1 \le M \le 2N
  • SiS_i 只包含 O 和 X
  • 1≤Q≤2×1051 \le Q \le 2 \times 10^5
  • 1≤Xi,Yi≤N1 \le X_i, Y_i \le N

样例解释 1

只有 (1,1)(1,1) 有棋子，该棋子能守护如下用 # 表示的格子：

####
##..
....
....

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页