Color

形式化题目

有一个 $n$ 行 $m$ 列的网格，第 $i$ 行第 $j$ 列的格子编号为 $(i-1)\times m + j$ （官方数据口径；题面原文写 $(i-1)\times n+j$ 为笔误，本解析以官方 std 与数据为准，按行优先理解）。

给定一个长度为 $a$ 的编号数列 $s$ ，把对应格子染红（重复染仍为红）。判断染色后的图形是否关于竖直中线对称——即关于反射变换 $\tau$ ：列 $y \mapsto m-y+1$ （行不变）保持不变。

等价表述：设红格编号集合为 $S$ ，判断 $\tau(S) = S$ 是否成立，其中 $\tau(k)$ 表示编号 $k$ 对应格子的镜像编号。

用 $(x,y)$ 表示第 $x$ 行第 $y$ 列，编号满足 $k=(x-1)\times m+y$ 。把 $k-1$ 对 $m$ 做带余除法：

k-1=q\cdot m+r,\qquad 0\le r<m,

则

k

位于第

q+1

行第

r+1

列，即

x=q+1,\ y=r+1

。翻折后行不变、列

y\mapsto m-y+1=m-r

，所以

\tau(k)=q\cdot m+(m-r)=(x-1)\times m+(m-y+1).

思路

一句话本质：图形对称 $\iff$ 染色集合在镜像变换下封闭——每个红格子的镜像格子也必须被染红，逐个查一次即可。

直接照"图形对称"检查，需要检查哪些格子？

对称意味着图形沿竖直中线翻折后与自身重合，所以每个被染红的格子，它的镜像格子也必须被染红；反过来不需要再查——镜像的镜像还是自己（翻折两次回到原位），从红格子出发查一遍就覆盖了所有必须检查的点。下图是 3×3 的例子，格子 4 与 6 互为镜像（行不变，列 $1 \to 3$ ）：

text

1
2
3
4列:  1  2  3
行1: .  .  .
行2: 4  .  6     ← 4 与 6 互为镜像：行不变，列 1 → 3
行3: .  .  .

从图中可确认两件事：行号完全不变（两个镜像格子都停在行 2）；列号 $y$ 映到 $m-y+1$ （ $m=3$ 时 $1 \to 3$ 、 $3 \to 1$ 、 $2 \to 2$ ）。这正是 $\tau$ 公式的来源——翻折把"第 $y$ 列"送到"倒数第 $y$ 列"，所以镜像编号只需在列偏移上做 $r \to m-1-r$ 的映射。

镜像格子对应的编号怎么算？

为了方便余数的计算，这里统一用 $(0,0)$ 起点（第 0 行、第 0 列）的编号示意。以 $m=5$ 为例，行是行偏移 $q$ 、列是列偏移 $r$ （都从 0 起），格子里的数字是 $q\times m+r$ ，即编号减一 $k-1$ ：

text

1
2
3
4
5
6
7
8
9+---+----+----+----+----+----+
|   |  0 |  1 |  2 |  3 |  4 |   ← 列偏移 r
+---+----+----+----+----+----+
| 0 |  0 |  1 |  2 |  3 |  4 |   ← 行偏移 q
| 1 |  5 |  6 |  7 |  8 |  9 |
| 2 | 10 | 11 | 12 | 13 | 14 |
| 3 | 15 | 16 | 17 | 18 | 19 |
| 4 | 20 | 21 | 22 | 23 | 24 |
+---+----+----+----+----+----+

例如第 2 行第 3 列的格子是 $2\times5+3=13$ ，对应 1 起编号 $k=14$ 。

按行优先编号 $k=(x-1)\times m+y$ ，用带余除法拆出行列： $k-1=q\times m+r$ （ $0\le r<m$ ），其中 $q$ 是行偏移（第 $q+1$ 行）、 $r$ 是列偏移（第 $r+1$ 列）。镜像只改列偏移： $r\to m-1-r$ ，所以镜像编号是 $q\times m+(m-r)$ 。这就是上面形式化题目里的 $\tau$ 。

为什么对 $k-1$ 而不是 $k$ 做带余除法？

编号从 1 开始（第 1 行第 1 列的编号是 1），列号 $y\in[1,m]$ ，而带余除法的余数范围是 $[0,m-1]$ ，所以先减一，把"列号 $1..m$ "平移成"列偏移 $0..m-1$ "才能对上。若直接用 $k$ 除以 $m$ ，当 $y=m$ 时 $k$ 恰好被 $m$ 整除，余数 $0$ 会被误当成"新一行的开头"：比如 $m=3$ 时编号 $3$ 明明是第 1 行第 3 列，但 $3\bmod 3=0$ ，会被拆成第 2 行第 0 列。减一后 $k-1=(x-1)\times m+(y-1)$ ，列偏移 $r=y-1$ 与余数一一对应，拆行（ $q$ ）拆列（ $r$ ）才不错位。

为什么"每个红格的镜像都在集合里"就足以推出整个图形对称？

设红格集合为 $S$ 。检查条件给出 $\tau(S) \subseteq S$ 。对两边再取一次镜像： $\tau(\tau(S)) \subseteq \tau(S)$ ；利用 $\tau$ 是对合（ $\tau(\tau(x)) = x$ ）得到 $S \subseteq \tau(S)$ 。两边一夹就是 $\tau(S) = S$ ，恰好是"图形关于中线对称"的定义。这一步是本题的核心卡点：对合变换下，子集包含就自动升级为集合相等，因此省掉了反向扫描。

$n,m$ 最大 $10^7$ ，网格有 $10^{14}$ 个格子，怎么标记染色？

不需要按格子开数组。真正被染红的只有 $a \leqslant 10^5$ 个格子，用 map<long long, bool> 只存这些编号即可，再对输入的 $a$ 个编号逐个查询镜像是否存在。复杂度与 $n,m$ 无关。下面这个暴力基准 brute.cpp 直接开二维数组标记染色（只能处理 $n,m \leqslant 100$ ），判定逻辑与正解一致，只是存储方式受限：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 19:05
 * update_at: 2026-08-28 19:05
 */

// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 只适用于 n*m 很小的数据（这里限制 n,m <= 100）：
// 直接开二维数组标记每个格子是否被染红，再对每个红格子检查镜像格子是否被染。
// 这是"逐格模拟"的朴素写法；n,m 达到 1e7 时网格无法开数组，就是 main.cpp 要解决的瓶颈。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int a, n, m;
int f[MAXN][MAXN];   // f[x][y] = 1 表示第 x 行第 y 列被染红
int s[10005];

// 把编号 x 转成 (x行, y列)：行优先编号 (x-1)*m + y = 编号。
void decode(long long x, int &row, int &col) {
    row = (int)((x - 1) / m) + 1;
    col = (int)((x - 1) % m) + 1;
}

void solve() {
    cin >> a >> n >> m;
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= a; i++) {
        cin >> s[i];
        int x, y;
        decode(s[i], x, y);
        f[x][y] = 1;
    }
    // 对每个被染红的格子，检查它关于竖直中线（列 y 映到 m-y+1）的镜像是否被染。
    for (int i = 1; i <= a; i++) {
        int x, y;
        decode(s[i], x, y);
        if (f[x][m - y + 1] == 0) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

重复染色怎么办？

重复染红不改变集合，map 赋值与查询天然按集合语义去重，同一编号出现多次没有影响。

边界情况需要注意什么？

$m=1$ 时只有一列，镜像就是自己，任意染色都对称，公式自动给出 Yes，无需特判。 $n=1$ 时公式照常工作（镜像仍按列计算）；注意" $n=1$ 恒对称"的说法只对官方那组全对称构造的数据成立，一般单行染色并不一定对称，所以正解不做任何特判。编号最大 $n\times m \leqslant 10^{14}$ ，超过 int 范围，必须用 long long。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 19:05
 * update_at: 2026-08-28 19:05
 */

// main.cpp：B. Color 最终解。
// 编号公式按官方 std 与数据采用行优先 (i-1)*m + j 理解（题面原文 (i-1)*n+j 为笔误）。
// 对称性等价于：每个红格子的镜像格子也是红的。

#include <bits/stdc++.h>
using namespace std;

const int MAXA = 100005;

int T;
int a;
long long n, m;
long long s[MAXA];               // 输入的染色编号（可能重复）
map<long long, bool> red;        // 被染红的格子集合（重复染色不改变集合）

// 计算格子编号 x 关于竖直中线（列 j 映到 m-j+1）的镜像格子编号。
// 记 x - 1 = t*m + (y-1)，即第 t+1 行第 y 列，则镜像为第 t+1 行第 m-y+1 列。
long long trans(long long x) {
    long long t = (x - 1) / m;          // 所在行（0 起始）
    long long y = x - t * m;            // 所在列（1..m）
    return t * m + (m - y + 1);
}

void solve() {
    red.clear();
    cin >> a >> n >> m;
    for (int i = 1; i <= a; i++) {
        cin >> s[i];
        red[s[i]] = true;
    }
    // 逐点检查：每个红格子的镜像必须也在集合中。
    // trans 是对合（翻两次回到原位），所以只需从红格子出发查一遍。
    for (int i = 1; i <= a; i++) {
        long long mir = trans(s[i]);
        if (!red.count(mir)) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

复杂度

时间：每组 $O(a \log a)$ （map 插入与查询各 $O(\log a)$ ，共 $O(a)$ 次）。
空间： $O(a)$ （map 最多存 $a$ 个不同编号）。
与 $n,m$ 无关， $a \leqslant 10^5$ 、 $T \leqslant 5$ 完全够用。

总结

本题把"图形关于竖直中线对称"翻译成集合问题：染色集合 $S$ 在镜像变换 $\tau$ 下封闭。两个关键点：一是用整除把编号拆回行列，镜像只改列、行不变，得到 $O(1)$ 的 $\tau$ ；二是利用 $\tau$ 是对合的性质，从"每个红格镜像都在集合中"（ $\tau(S)\subseteq S$ ）直接推出 $\tau(S)=S$ ，不需要反向再查一遍。最后用 map 只存 $a$ 个红格子，避开 $10^{14}$ 的全网格数组，得到 $O(a\log a)$ 的解法。

目录

形式化题目

思路

代码

复杂度

总结