大家好今天我们来看CSP202509B. 水印检查这道题目题目要求在一幅 n×n 的灰度图像中找出所有可能的阈值 k0 到 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[ix][jy] k) ok false; } else { if (a[ix][jy] 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分因为暴力需要OL的枚举结合n²段区间时间复杂度再次来到On²L我们可以维护一段长为L差分数组diff对每段的起点diff[mx1],表示覆盖数1每段的终点diff[mn]--表示覆盖数-1处理完所有区间后我们从0到L-1遍历维护一个cnt表示被多少个区间覆盖每到一个k先执行cntdiff[k]如果cnt0说明有区间覆盖输出k这样只需要OL扫一遍输出diff0的位置即可总时间复杂度为On²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[ix][jy]); } else { mn min(mn, a[ix][jy]); } } } 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)。这是一种典型的离线区间统计技巧在很多题目中都有应用。感谢阅读欢迎在评论区留言讨论转载请标明出处
