画 - 题目列表

形式化题目

给定 $n \times m$ 的像素矩阵（ $n, m$ 均为 3 的倍数），每个像素为 R/G/B 三色之一。把矩阵按行列各等分为 $3 \times 3$ 的若干小矩阵（行分 $n/3$ 块、列分 $m/3$ 块），对全部 $\frac{nm}{9}$ 个小矩阵去重，求不同小矩阵的数量。

等价表述：给定来自集合 $\{R,G,B\}^{9}$ 的 $\frac{nm}{9}$ 个元素（按行优先排布），求其中不同元素的个数。

思路

一句话本质：3x3 小矩阵一共只有 $3^9 = 19683$ 种可能形态，把每块压缩成一个三进制整数、用 bool 数组标记，就能 $O(1)$ 去重计数。

问题？ 怎样判断两个 3x3 小矩阵是否相同？

两个小矩阵相同当且仅当 9 个位置的字符一一对应相同。最字面的做法是把 9 个字符拼成一个字符串存进 set<string> 自动去重，但字符串比较与分配有额外开销。

先看这个直接按题意写的朴素解：

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/**
 * 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 23:40
 * update_at: 2026-08-28 23:40
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 直接按题意把每个 3x3 小矩阵存成 9 个字符的 string，用 set<string> 去重。
// string 比较和 set 操作开销大，只适合 n,m 很小的数据（这里按 n,m <= 30 使用）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;   // 小数据：n,m <= 30

int n, m;
string g[MAXN];      // 像素矩阵的每一行
set<string> blocks;  // 收集所有不同的 3x3 小矩阵，自动去重

// 提取左上角为 (x, y) 的 3x3 小矩阵，按行优先拼成 9 个字符的字符串。
string get_block(int x, int y) {
    string s;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            s.push_back(g[x + i][y + j]);
        }
    }
    return s;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];

    blocks.clear();
    // 横向 n/3 块、纵向 m/3 块；块 (bi, bj) 的左上角是 (bi*3, bj*3)。
    for (int bi = 0; bi < n / 3; bi++) {
        for (int bj = 0; bj < m / 3; bj++) {
            blocks.insert(get_block(bi * 3, bj * 3));
        }
    }
    cout << blocks.size() << '\n';
}

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

    solve();
    return 0;
}

问题？ 暴力里"9 个字符的字符串"能不能压得更紧？

每个格子只有 3 种颜色，正好对应三进制的一位：R=0、G=1、B=2。把 9 个格子按行优先顺序逐位拼起来，就是 9 位三进制数。例如一个块的行优先颜色序列是 R G B G R B B G R，编码就是 012102210（三进制）：

行优先位置	1	2	3	4	5	6	7	8	9
颜色	R	G	B	G	R	B	B	G	R
三进制位	0	1	2	1	0	2	2	1	0

表头三行分别是从左到右的行优先位置、该位置的字符、对应的三进制位；同一列上下对应一格。

因为编码顺序对所有块固定，两个块相同 ⇔ 编码相同，所以"不同的块" ⇔ “不同的编码”，问题变成整数去重。

问题？ 编码范围有多大？用什么去重？

$3^9 = 19683$ ，编码只落在 $[0, 19683)$ 。直接用 bool seen[19683] 标记：第一次遇到某编码就计数 +1 并打标记。不需要排序，也不需要哈希表。

问题？ 分块怎么遍历？

$n, m$ 都是 3 的倍数：横向 $n/3$ 块、纵向 $m/3$ 块。块 $(bi, bj)$ 的左上角是 $(bi \times 3, bj \times 3)$ ，取它右下的 3x3 即可。编码时 code = code * 3 + 颜色位，逐格拼接。

代码

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
61
62
63
64/**
 * 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 23:40
 * update_at: 2026-08-28 23:40
 */
// main.cpp：把每个 3x3 小矩阵编码成一个 9 位三进制数（R=0, G=1, B=2），
// 用 bool seen[19683] 标记出现过的编码，统计不同小矩阵的数量。
// 复杂度 O(nm)：每个像素恰好被扫一次。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;      // n <= 3000
const int MAXCODE = 19683;  // 3^9：9 个格子每格取 R/G/B 之一，共 3^9 种小矩阵

int n, m;
string g[MAXN];      // 像素矩阵的每一行
bool seen[MAXCODE];  // seen[x] = true 表示编码为 x 的 3x3 小矩阵已出现过

// 把颜色字符映射成三进制位：R -> 0，G -> 1，B -> 2。
int color_id(char c) {
    if (c == 'R') return 0;
    if (c == 'G') return 1;
    return 2; // 'B'
}

// 提取左上角为 (x, y) 的 3x3 小矩阵，按行优先顺序拼成三进制数。
// 逐位 code = code * 3 + 当前颜色，编码唯一落在 0..19682。
int encode(int x, int y) {
    int code = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            code = code * 3 + color_id(g[x + i][y + j]);
        }
    }
    return code;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];

    int ans = 0;
    // 横向 n/3 块、纵向 m/3 块；块 (bi, bj) 的左上角是 (bi*3, bj*3)。
    for (int bi = 0; bi < n / 3; bi++) {
        for (int bj = 0; bj < m / 3; bj++) {
            int code = encode(bi * 3, bj * 3);
            if (!seen[code]) {
                seen[code] = true;
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

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

    solve();
    return 0;
}

复杂度

每个像素恰好被扫一次，块数 $\frac{nm}{9}$ 、每块 9 格，总时间复杂度 $O(nm)$ ；空间 $O(nm)$ 存矩阵 + $O(3^9)$ 标记数组。 $n = m = 3000$ 时约 $9 \times 10^6$ 次操作，实测 < 0.1s。

总结

本题的本质是有限状态去重：去重对象的总形态数 $3^9$ 是固定常数，且远小于块数上限 $10^6$ ，所以"枚举全部可能形态 + 标记"天然优于"通用集合"。三进制压缩把 9 字符的块变成整数下标，bool 数组做到 $O(1)$ 去重。

三个要点：

双射编码——行优先顺序固定，块 ⇔ 三进制数一一对应，去重语义不变；
状态空间小—— $3^9 = 19683$ 直接开 bool 数组，比 set/排序都简单；
暴力与正解同构——brute.cpp 用 set<string> 存完整字符串，main.cpp 用 seen[code] 存压缩整数，分块遍历完全一致，二者对拍 200 组全部一致。

"把有限状态压成整数下标"的思想在棋盘状态、方向组合、排列压缩等问题里反复出现，是竞赛中高频的建模手段。

画

目录

形式化题目

思路

代码

复杂度

总结