CCF-CSP 39-2 水印检查（watermark)【C++】

题目https://sim.csp.thusaac.com/contest/39/problem/1https://sim.csp.thusaac.com/contest/39/problem/1思路参考80分暴力求解遍历所有可能的k检验是否满足条件可得80分时间复杂度O(L*n^2)粗略估计计算次数65536*200*200*5*9#includebits/stdc.h using namespace std; #define endl\n const int N205; int a[N][N], t[N][N]; //白0黑色1 int csp[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 n,l; bool check() { for(int i0;i4n;i) for(int j0;j8n;j) { int f11; for(int i10;i15;i1) for(int j10;j19;j1) { if(t[ii1][jj1]!csp[i1][j1]) { f10; break; } } if(f11) return true; } return false; } void solve() { cinnl; for(int i0;in;i) for(int j0;jn;j) cina[i][j]; for(int k1;kl;k) { for(int i0;in;i) for(int j0;jn;j) { if(a[i][j]k) t[i][j]0;//白0黑色1 else t[i][j]1; } if(check()) coutkendl; } } int main() { ios::sync_with_stdio(0),cin.tie(0); solve(); return 0; }100分核心思想对于阈值参数灰度值大于等于 k 的像素变为白色灰度值小于 k 的像素变为黑色。枚举左上角每块5 x 9区域中找对应“CSP”中白色像素位置的最小值mn作为可行解的上界找对应“CSP”中黑色像素位置的最大值mx作为可行解的下界取不到因为k要大于mx可行解为mxmn]将mx1到mn存入set自动去重且从小到大最后输出即可时间复杂度O(n^2)粗略估计计算次数200×200×5×91800000可以再让AI总结一下代码逻辑在输入的 n×n 像素矩阵中用一个固定的 5×9 二值模板csp0 表示白色区域1 表示黑色区域进行滑动匹配。对每个可能的窗口位置找出模板中白色区域0对应位置的最小像素值→mn找出模板中黑色区域1对应位置的最大像素值→mx若存在整数阈值 k 满足 mxk≤mn 则该 k 能使当前窗口按模板正确二值化黑区 ≥ k白区 k视为可行解。将所有窗口产生的可行 k 值加入集合ans自动去重并排序最后按升序输出。#includebits/stdc.h using namespace std; #define endl \n const int N205; int a[N][N]; int csp[5][9]{//白0黑色1 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 }; void solve() { int n,l; cinnl; setintans; for(int i0;in;i) for(int j0;jn;j) cina[i][j]; for(int i0;in-5;i) for(int j0;jn-9;j){ int mn0x3f3f3f3f; //白色区域的最小值 0 int mx0;//黑色区域的最大值 1 for(int x0;x5;x) for(int y0;y9;y) { if(csp[x][y]0) mnmin(mn,a[ix][jy]); else mxmax(mx,a[ix][jy]); } //可行解为 (mx, mn] for(int kmx1;kmn;k) ans.insert(k); } for(auto k:ans) coutkendl; } int main() { ios::sync_with_stdio(0),cin.tie(0); solve(); return 0; }