CSP202509B. 水印检查 满分题解

大家好，今天我们来看CSP202509B. 水印检查这道题目

题目要求在一幅 n×n 的灰度图像中，找出所有可能的阈值 k（0 到 L-1 之间的整数），使得按这个阈值二值化后，图像中存在一个 5×9 的子区域，其黑白像素分布与给定的 CSP 水印模板完全一致。最后按从小到大的顺序输出所有符合条件的 k。

80分题解

我们遍历从0到L-1的所有整数k，对每个整数k，我们判断此时的矩阵是否存在一个5×9的子区域与模板匹配，时间复杂度O(n²L)，代码如下：

#include <bits/stdc++.h> using namespace std; int match[5][9] = { {0,0,0,0,0,0,0,0,0}, {0,1,1,0,1,1,0,1,0}, {0,1,1,0,0,0,0,0,1}, {0,1,1,1,1,0,0,1,1}, {0,0,0,0,0,0,0,1,1} }; int a[205][205]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, L; cin >> n >> L; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } for (int k = 0; k < L; k++) { bool found = false; for (int i = 0; i <= n - 5 && !found; i++) { for (int j = 0; j <= n - 9 && !found; j++) { bool ok = true; for (int x = 0; x < 5 && ok; x++) { for (int y = 0; y < 9 && ok; y++) { if (match[x][y] == 1) { if (a[i+x][j+y] >= k) ok = false; } else { if (a[i+x][j+y] < k) ok = false; } } } if (ok) found = true; } } if (found) printf("%d\n", k); } return 0; }

这段代码只能得到80分，因为当L取65536时数量级达到了10¹¹，考虑优化

优化思路

在刚才的代码中，我们发现L是导致时间复杂度过大的重要因素，考虑消除掉L的方法。

我们发现对于每个5×9的子区域，黑色位<k，白色位≥k，所以对任意一个5×9的子区域来说，只要k比最大的黑色位大，同时小于等于最小的白色位，k都是有效的

令最大的黑色位对应值为mx,最小的白色位对应值为mn

我们就得到了这样一段有效的答案区间：（mx,mn]

这样，问题就转换成了给定n²段区间，从小到大输出区间内所有整数

如果你在这段输出使用暴力遍历，那么你又会得到80分，因为暴力需要O（L）的枚举，结合n²段区间，时间复杂度再次来到O（n²L）

我们可以维护一段长为L差分数组diff

对每段的起点diff[mx+1]++,表示覆盖数+1

每段的终点diff[mn]--，表示覆盖数-1

处理完所有区间后，我们从0到L-1遍历，维护一个cnt表示被多少个区间覆盖，每到一个k，先执行cnt+=diff[k]，如果cnt>0，说明有区间覆盖，输出k

这样只需要O（L）扫一遍，输出diff>0的位置即可，总时间复杂度为O（n²+L）

代码如下：

#include <bits/stdc++.h> using namespace std; int match[5][9] = { {0,0,0,0,0,0,0,0,0}, {0,1,1,0,1,1,0,1,0}, {0,1,1,0,0,0,0,0,1}, {0,1,1,1,1,0,0,1,1}, {0,0,0,0,0,0,0,1,1} }; int a[205][205]; int diff[70000]; // 差分数组 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, L; cin >> n >> L; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } for (int i = 0; i <= n - 5; i++) { for (int j = 0; j <= n - 9; j++) { int mx = 0; // 黑色最大值 int mn = INT_MAX; // 白色最小值 for (int x = 0; x < 5; x++) { for (int y = 0; y < 9; y++) { if (match[x][y] == 1) { mx = max(mx, a[i+x][j+y]); } else { mn = min(mn, a[i+x][j+y]); } } } if (mx + 1 <= mn) { diff[mx + 1]++; if (mn + 1 < L) { diff[mn + 1]--; // 差分处理 } } } } int cnt = 0; for (int k = 0; k < L; k++) { cnt += diff[k]; if (cnt > 0) { printf("%d\n", k); } } return 0; }

这道题的核心技巧在于把"每个 k 去匹配窗口"反转成"每个窗口能匹配哪些 k"，然后用差分数组高效统计区间覆盖，将 L 的因子从乘法降为加法，从而把复杂度从 O(n²L) 降到 O(n²+L)。这是一种典型的离线区间统计技巧，在很多题目中都有应用。

感谢阅读，欢迎在评论区留言讨论！

转载请标明出处