水印检查

GitHub跳转原题关系图 Canvas 关系图返回列表

把每个 5x9 窗口转成阈值区间，用差分数组合并所有能呈现 CSP 水印的阈值。

OJ: shumeng

题目 ID: CSP202509B

难度:普及-

标签:枚举差分二维数组

日期: 2026-07-31 16:21

形式化题目

给定 $n \times n$ 灰度图，灰度值在 $[0, L-1]$ 。对阈值 $k$ ，灰度 $\ge k$ 的像素视为白色，否则黑色。求所有能在一个 $5 \times 9$ 子矩阵中呈现固定 CSP 图案的阈值 $k$ ，从小到大输出。

思路

先看最直接的做法：对每个阈值、每个窗口逐一比对。

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-07-31 16:21
 * update_at: 2026-08-17 23:00
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

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

    int n, limit;
    cin >> n >> limit;
    vector<vector<int> > image(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> image[i][j];
    }

    int pattern[5][9] = {
        {1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 1, 0, 1},
        {1, 0, 0, 1, 1, 1, 1, 1, 0},
        {1, 0, 0, 0, 0, 1, 1, 0, 0},
        {1, 1, 1, 1, 1, 1, 1, 0, 0},
    };
    // 朴素做法：对每个阈值 k 逐窗口检查是否匹配水印图案，适合小数据对拍
    for (int k = 0; k < limit; k++) {
        bool found = false;
        for (int top = 0; top + 5 <= n && !found; top++) {
            for (int left = 0; left + 9 <= n && !found; left++) {
                bool valid = true;
                for (int i = 0; i < 5 && valid; i++) {
                    for (int j = 0; j < 9; j++) {
                        bool white = image[top + i][left + j] >= k;
                        if ((int)white != pattern[i][j]) {
                            valid = false;
                            break;
                        }
                    }
                }
                if (valid) found = true;
            }
        }
        if (found) cout << k << '\n';
    }
    return 0;
}

关键观察：阈值形成连续区间

固定一个 $5 \times 9$ 窗口，图案中的白色位置必须满足 $A \ge k$ ，黑色位置必须满足 $A < k$ 。因此该窗口能呈现水印的阈值是一个整数区间：

\max(\text{黑色位置灰度}) + 1 \le k \le \min(\text{白色位置灰度})

差分合并

每个窗口只贡献一个区间。枚举所有窗口，用差分数组合并这些区间，最后扫描 $0..L-1$ 输出覆盖次数大于 0 的阈值即可。

代码

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 23:00
 */
#include <bits/stdc++.h>
using namespace std;

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

    int n, limit;
    cin >> n >> limit;
    vector<vector<int> > image(n, vector<int>(n)); // 灰度图像
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> image[i][j];
    }

    // CSP 水印图案：1 表示白色(灰度>=k)，0 表示黑色(灰度<k)
    int pattern[5][9] = {
        {1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 1, 0, 1},
        {1, 0, 0, 1, 1, 1, 1, 1, 0},
        {1, 0, 0, 0, 0, 1, 1, 0, 0},
        {1, 1, 1, 1, 1, 1, 1, 0, 0},
    };

    // 差分数组：difference[k] 表示阈值 k 的覆盖次数变化量
    vector<int> difference(limit + 2, 0);
    for (int top = 0; top + 5 <= n; top++) {
        for (int left = 0; left + 9 <= n; left++) {
            // 该窗口能呈现水印的阈值区间：[黑色位置最大灰度+1, 白色位置最小灰度]
            int minimum_white = limit;
            int maximum_black = -1;
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 9; j++) {
                    if (pattern[i][j] == 1) {
                        minimum_white = min(minimum_white, image[top + i][left + j]);
                    } else {
                        maximum_black = max(maximum_black, image[top + i][left + j]);
                    }
                }
            }
            int lower = maximum_black + 1;
            int upper = minimum_white;
            if (lower <= upper) {
                difference[lower]++;
                difference[upper + 1]--;
            }
        }
    }

    // 前缀和求每个阈值被覆盖的次数，大于 0 即可检测出水印
    int active = 0;
    for (int k = 0; k < limit; k++) {
        active += difference[k];
        if (active > 0) cout << k << '\n';
    }
    return 0;
}

复杂度

窗口数为 $O(n^2)$ ，每个窗口检查固定 45 个格子，总时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2 + L)$ 。

总结

阈值对固定窗口形成一个连续区间，先求区间再统一差分，比逐阈值检查每个窗口快得多。本题也可以先对所有窗口收集区间，再用扫描线求并，差分是最简单的实现。

题目来自第 39 次 CSP 认证 T2，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

一幅长宽分别为 $n$ 个像素和 $m$ 个像素的灰度图像可以表示为一个 $n \times m$ 大小的矩阵 $A$ 。其中每个元素 $A_{i,j}$ （ $1 \leq i \leq n,1 \leq j \leq m$ ）是一个 $[0, L-1]$ 范围内的整数，表示对应位置像素的灰度值。具体来说，一个 $8$ 比特的灰度图像中每个像素的灰度范围是 $[0, 255]$ 。

题目描述

小 P 在学习了数字图像处理后，设计了一种形如 CSP 的水印。具体来说，若想检测出水印，需选定一个阈值参数 $k$ ，然后将图像二值化：

灰度值大于等于 $k$ 的像素变为白色；

灰度值小于 $k$ 的像素变为黑色。

然后检查图像中是否有 $5 \times 9$ 的区域如下所示（为方便展示用绿色替代白色）：

即呈现出 CSP 三个字母的形状。

该水印较为简单，无需考虑旋转、翻转等复杂情况；只需检查灰度图像 $A$ 是否包含一个大小为 $5 \times 9$ 的子矩阵 $A_{i,j} \cdots A_{i+4,j+8}$ ，其中大于等于阈值 $k$ 和小于的像素分布与上图完全一致。

对于给定的 $n \times n$ 大小的灰度图像 $A$ ，试计算出所有能检查出水印 CSP 的阈值 $k$ 。

输入格式

从标准输入读入数据。

输入的第一行包含由空格分隔的两个正整数 $n$ 和 $L$ ，表示图像的大小和像素灰度值的范围。

接下来 $n$ 行输入矩阵 $A$ ，其中第 $i$ 行（ $1 \leq i \leq n$ ）包含用空格分隔的 $n$ 个整数，依次为 $A_{i,1}, A_{i,2}, \cdots, A_{i,n}$ 。

输出格式

输出到标准输出。

输出若干行，每行包含一个整数，表示一个可以检查出水印 CSP 的阈值 $k$ 。 $[0, L-1]$ 范围内所有可行阈值 $k$ 按从小到大顺序输出。

input1

1
2
3
4
5
6
7
8
9
109 256
9 9 8 8 9 9 9 8 255
9 0 0 8 0 0 7 0 8
9 0 0 8 7 9 7 7 5
9 0 0 0 0 8 7 0 0
7 7 8 7 7 8 8 6 5
6 2 2 5 1 1 5 1 6
6 2 2 6 6 6 7 5 3
6 2 2 2 1 5 8 1 1
7 7 8 7 7 8 8 2 3

output1

样例 1 解释

$k=4$ 或 $5$ 时图像如下所示，其中 * 和 - 分别表示白色和黑色，水印出现在后五行：

plain

1
2
3
4
5
6
7
8
9* * * * * * * * *
* - - * - - * - *
* - - * * * * * *
* - - - - * * - -
* * * * * * * * *
* - - * - - * - *
* - - * * * * * -
* - - - - * * - -
* * * * * * * - -

$k=7$ 时图像如下所示，容易发现前五行（ $A_{1,1} \cdots A_{5,9}$ ）显现出水印 CSP：

plain

1
2
3
4
5
6
7
8
9* * * * * * * * *
* - - * - - * - *
* - - * * * * * -
* - - - - * * - -
* * * * * * * - -
- - - - - - - - -
- - - - - - * - -
- - - - - - * - -
* * * * * * * - -

子任务

$80\%$ 的测试点满足： $n \leq 50,L=256$ ；

全部的测试点满足： $9 \leq n \leq 200,L \in \{256, 65536\}$ ，像素值均在 $[0, L-1]$ 范围内，且保证至少存在一个阈值可以检测出水印 CSP。

水印检查

目录

形式化题目

思路

关键观察：阈值形成连续区间

差分合并

代码

复杂度

总结