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

AT_arc089_b.[ABC086D] Checker

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

シカ的 AtCoDeer 君想要用边长为 KK 的“市松模様”来涂满一张无限大的二维网格。其中，边长为 KK 的“市松模様”是指将网格以白色和黑色交替着色，且每种颜色的每个连通块恰好是 K×KK \times K 的正方形。例如，下面就是边长为 33 的“市松模様”的一个例子。

cba927b2484fad94fb5ff7473e9aadef.png

AtCoDeer 君有 NN 个愿望。第 ii 个愿望用 xi,yi,cix_i, y_i, c_i 表示。如果 cic_i 是 B，表示希望 (xi,yi)(x_i, y_i) 这个格子被涂成黑色；如果 cic_i 是 W，表示希望它被涂成白色。请你计算，最多能同时满足多少个愿望。

输入格式

输入以以下格式从标准输入读入。

N KN\ K
x1 y1 c1x_1\ y_1\ c_1
x2 y2 c2x_2\ y_2\ c_2
⋮\vdots
xN yN cNx_N\ y_N\ c_N

输出格式

输出能同时满足的愿望数量的最大值。

输入输出样例

  • 输入#1

    4 3
0 1 W
1 2 W
5 3 B
5 4 B

    输出#1

    4

  • 输入#2

    2 1000
0 0 B
0 1 W

    输出#2

    2

  • 输入#3

    6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

    输出#3

    4

说明/提示

限制条件

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤K≤10001 \leq K \leq 1000
  • 0≤xi≤1090 \leq x_i \leq 10^9
  • 0≤yi≤1090 \leq y_i \leq 10^9
  • 如果 i≠ji \neq j，则 (xi,yi)≠(xj,yj)(x_i, y_i) \neq (x_j, y_j)
  • cic_i 为 B 或 W
  • N,K,xi,yiN, K, x_i, y_i 都是整数

样例解释 1

像上面给出的例子那样去涂色，可以同时满足所有的愿望。

由 ChatGPT 5 翻译

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

首页