第39次CCF CSP认证一结束关于第二题“水印检查”的讨论就炸了有人欢喜有人愁。欢喜的是它本质上还是一道模拟题暴力也能得分愁的是这道题的题面绕来绕去很多人读完根本不知道要输出“损坏块数”还是“完好块数”。这篇文章就以我个人的考场实战为例把这题的读题、思路、代码、踩坑一次性讲清楚顺便聊聊CSP前两题到底该怎么准备。不管你是第一次考还是已经二战三战只要想把第39次这道水印检查吃透这篇应该能帮上忙。CSP认证的前两题向来是“送分题”但送分并不等于躺平。第39次的第二题考了个图像水印校验的场景背景包装得花里胡哨剥开之后核心就是一个矩阵分块加特征值比对。难吗不难。可就是这种题最容易在“统计对象”“下标换算”“特征值顺序”这些细节上翻车。我出考场后跟几个同学对答案发现至少有一半人把输出方向搞反了还有人读错了水印矩阵的遍历顺序。所以不要小看它我把它从头到尾拆开讲一遍。1. 先读懂水印检查第39次CSP第二题到底在问什么1.1 图像分块与水印校验的现实原型先别管比赛我们把场景落到现实里。数字图像可以看作一个很大的像素矩阵每个像素是一个灰度值。为了防止图片被篡改可以在图像里嵌入水印把图片切成很多个固定大小的小块然后在某些块里写入校验信息。别人拿到图片后重新计算这些块的校验值和原始水印比对就能知道哪些区域被动过手脚。这道题就是把这个过程简化成一次上机考试。给定一张 n×n 的灰度图用 b×b 的尺寸把它切成若干互不重叠的方块再把其中一部分方块作为水印区域。水印区域是一块 m×m 的“块矩阵”每个块有一个特征值这个特征值来自原始图像里对应方块的内容。我们拿到的输入是“当前这幅图”和“原始水印特征值表”要做的就是把当前图的水印区域重新提取出来逐一比对看哪些块对不上了。这样理解之后题目就不再是“看不懂的文字游戏”而是一个很标准的校验流程分块、算特征、比对、统计。只是考场上时间紧很多人被题面里的“水印”“篡改”“覆盖”这些词绕晕了反而忘了它只是一道二维数组模拟题。1.2 回忆版题面输入输出到底长什么样CCF赛后不公布原题以下是我根据考场回忆和常见题面整理出的版本核心算法不变个别细节比如水印区域是否左上角对齐如果和官方题面有出入请以自己考场看到的提示为准。输入大概是这样的第一行给三个整数 n、b、mn 是图片边长b 是分块边长m 是水印矩阵的行列块数。接着是 n 行 n 列的像素值每个像素值是 0 到 255 之间的整数。之后是 m 行 m 列的水印矩阵每个元素是某个“特征值”。在这个版本里水印区域位于图片左上角从第 1 行第 1 列开始一共覆盖 m×m 个 b×b 的方块。做法就是把图片左上角 m×m 个方块里的像素取出来按同样顺序计算特征值和输入的水印矩阵逐位比较统计不一致的方块数量。官方题面里既可能问“被篡改的块数”也可能问“完好保留的块数”。我下面的代码默认统计“不一致的块数”如果是另一种问法把最终输出改成 m×m 减去这个数就行。这个细节我会在后面单独开一节讲因为它是全场翻车率最高的一个坑。1.3 水印检查的考点定位为什么说它是良心模拟题从考点看这道题考察的东西非常朴素二维数组的读取与遍历、分块坐标换算、按位异或或求和作为特征值、以及边界处理。前两题之所以普遍被认为“可以暴力”是因为数据范围通常不会卡到让人非要写高级数据结构不可。即便这道题要求的不是异或前缀和直接对每个块重新遍历像素总访问量也就是 n² 个像素完全能过。但“能做”和“能拿满”是两回事。CSP的题向来喜欢在输入输出语义上设小陷阱水印检查就是典型。很多人代码写对了最后输出反了或者水印矩阵的遍历顺序反了白白丢分。所以我的建议是拿到题先别急着敲代码花三分钟把题面逐句读透尤其是“输出损坏数量”还是“输出未损坏数量”这个动作能帮你省下后面调试的时间。这题不是不会做而是没读明白。2. 解题思路从直接模拟到二维异或前缀和2.1 直接暴力模拟的复杂度分析最直观的做法是三重循环外层枚举水印块的行列坐标内层枚举该块内的 b×b 个像素累加或异或得到特征值。因为图片被划分成互不重叠的块每个像素恰好被访问一次总复杂度是 O(n²)。在 n 不超过 1000 到 2000 的范围内C完全扛得住。那么有没有必要优化说实话没有也能过。但既然这是一篇讲“水印检查”的博文我建议顺手把二维异或前缀和学掉。原因有几个第一万一官方数据范围开得大暴力容易超时第二前缀和这种思路在后续的第四题第五题里经常作为基础工具出现第三学会异或版本的容斥你对“前缀和”这个概念的理解会深一层下次见到类似题就不会慌。暴力写法唯一要注意的是块坐标和像素坐标之间的换算第 i 个块的行起点是 i*b终点是 (i1)*b-1下标从 0 开始的话换算成 1-based 下标还要再处理一次。很多人的 bug 就出在边界上多算了最后一行块或者漏掉了最右侧一列块。我比较建议统一把数组开成 n1 大小下标从 1 开始这样前缀和和块的起点终点都比较好写。2.2 二维异或前缀和异或版的容斥原理如果你熟悉普通二维前缀和那么异或前缀和其实就是把加减法换成异或。普通二维前缀和 pre[i][j] 表示从矩阵左上角到 (i,j) 的所有元素之和异或版本里 pre[i][j] 表示从左上角到 (i,j) 的所有元素异或起来的结果构建公式是pre[i][j] pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1] ^ a[i][j]求某一块 [x1..x2] 行、[y1..y2] 列的子矩阵异或和公式是val pre[x2][y2] ^ pre[x1-1][y2] ^ pre[x2][y1-1] ^ pre[x1-1][y1-1]这里的逻辑是二维前缀和的容斥公式是“相加再减掉重叠部分”而异或的逆运算就是它自己所以原本的“减去”直接变成“异或”重叠的部分异或两次会被消掉。你可以把异或理解成二进制下的“加减法不分家”。这个技巧的收益是每查询一个块的异或和从 O(b²) 变成 O(1)整体复杂度由 O(n²) 降为 O(n² m²)。虽然对这道题来说暴力已经够用但多掌握一个工具以后遇到“多次询问矩形异或和”的题目时你能直接从模板思路迁移过去省下大量思考时间。2.3 特征值用异或和还是求和从网络热词“异或和csp”也能看出来很多人考完都会讨论这道题的特征值到底用什么。我印象里这道题用的就是异或和每块内所有像素灰度值按位异或后得到一个 0 到 255 之间的数。为什么用异或而不是求和首先是数值范围稳定256 以内的像素值异或后仍在 0 到 255 之间不容易溢出其次是异或对“单个像素变化”比求和更敏感一张块里改掉一个像素异或结果大概率会变更适合做篡改检测。但要注意异或校验有一个本质弱点如果两个像素同时被改成“成对异或为 0”的组合块内异或值可能不变这就产生漏检。这是哈希校验类算法的通病竞赛题不会拿这种极端反例来卡你但写博客的时候我必须提醒你别把特征值校验当成绝对可靠的防篡改机制实际工程里通常还要叠加更复杂的哈希。考试嘛题目说用异或就用异或别自己改成求和或者其他自定义规则免得和样例输出对不上。3. 完整代码与逐段讲解可以直接抄作业3.1 数据结构、读入与预处理我下面的代码以 C17 为例因为CSP官方支持 C14/17用 bits/stdc.h 在绝大部分评测环境都能过。如果你的编译器不支持这个万能头就手动包含 iostream 和 vector。第一步是读入 n、b、m然后开一个 (n1)×(n1) 的二维 vector 存图片下标从 1 开始这样后续前缀和不用额外判边界。读图片时用 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 提速这一行对大数据输入帮助很大。接着读 m×m 的水印矩阵存成一个二维 vector保持输入顺序后面比对时按同样顺序遍历。这里有个容易犯的错很多人把水印矩阵当图片去读结果 cin 顺序错乱后面的数据全部错位。建议把读图片和读水印矩阵分开两个双重循环并在代码注释里标明“当前在读什么”。CSP前两题的输入量不大正常 cin 就能过但ios::sync_with_stdio(false)这个习惯建议从一开始就养成。3.2 二维异或前缀和实现构建前缀和数组时用我刚才说的公式pre[i][j] pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1] ^ a[i][j];这一行就是整道题的算法核心。你可以先构建 a 数组再算 pre也可以在读入时就边读边构建效果一样。要注意的是异或运算的优先级低于加法不对异或的优先级比赋值高比算术低所以最稳妥的写法是带有括号的显式写法不要省括号。比如写成pre[i][j] pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ a[i][j];就行。千万别写成连加不加括号很容易出优先级问题。构建完成后就可以通过 O(1) 查询任意矩形块的异或和。对于水印第 i 行第 j 列的块下标从 0 开始它在图片中的行范围是x1 i * b 1到x2 (i 1) * b列范围是y1 j * b 1到y2 (j 1) * b。这里的换算建议先写在草稿纸上推一遍再写代码能省下大量调试时间。3.3 可直接运行的完整C代码下面这份代码是我按“水印区域在左上角、输出损坏块数”的版本写的。如果你拿到的题面是“输出完好块数”把最后一句改成cout m * m - bad endl;即可。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, b, m; cin n b m; vectorvectorint a(n 1, vectorint(n 1, 0)); for (int i 1; i n; i) { for (int j 1; j n; j) { cin a[i][j]; } } vectorvectorint w(m, vectorint(m, 0)); for (int i 0; i m; i) { for (int j 0; j m; j) { cin w[i][j]; } } vectorvectorint pre(n 1, vectorint(n 1, 0)); for (int i 1; i n; i) { for (int j 1; j n; j) { pre[i][j] pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ a[i][j]; } } int bad 0; for (int i 0; i m; i) { int x1 i * b 1; int x2 (i 1) * b; for (int j 0; j m; j) { int y1 j * b 1; int y2 (j 1) * b; int cur pre[x2][y2] ^ pre[x1 - 1][y2] ^ pre[x2][y1 - 1] ^ pre[x1 - 1][y1 - 1]; if (cur ! w[i][j]) { bad; } } } cout bad \n; return 0; }这段代码在样例上的表现很稳先把水印矩阵里每一个块对应的图片区域切出来计算异或和再与水印矩阵里的特征值比对。i 和 j 的循环顺序与水印矩阵输入顺序完全一致不会出现“转置”导致的错位。如果题目要求的是“图片中完整保留的水印块数量”就改成输出m * m - bad其它逻辑不用动。3.4 如果水印区域带偏移坐标怎么办有些同学回忆说原题里水印区域不一定在左上角而是给了一个起始位置。这种情况也很常见比如输入里额外给出水印区域左上角的块坐标或者给出像素坐标偏移量。遇到这种变体只需要把查询范围的起点加上偏移量就行。假设水印区域左上角对应的像素坐标是 (ox, oy)那么原代码里的x1 ox i * bx2 ox (i 1) * b - 1y1 oy j * by2 oy (j 1) * b - 1。我建议在读入阶段就把 ox 和 oy 存下来然后直接套公式不要在循环里临时算偏移容易乱。无论水印位置在哪核心思路不变任何一个块只要知道它在图片中的像素起始行列就能用二维异或前缀和 O(1) 算出特征值。4. 考场失误实录这些坑我替你踩过了4.1 坑一把“损坏块数”数成“完好块数”这是水印检查这道题最大的坑没有之一。我考场上写完代码样例过了自以为稳了交卷后对答案才发现大家讨论的全是“你到底输出的哪个数”。原来原题问的是“水印区域中受到影响的块的数量”我下意识输出的是“完好块数”直接反了。这给我的教训是CSP前两题读题时一定要把“输出什么”圈出来最好心里默念两遍。如果题目里有“未被篡改”“受保护”“完好”“损坏”这些词先确认统计口径再写代码。像水印检查这种题就一个数字的事改一行就能拿满分可是一旦方向反了代码写得再漂亮也是零分。考场时间紧但读题的时间绝对不能省。4.2 坑二块索引和像素坐标的换算错位第二个常见问题是下标换算。很多同学从 i0 枚举块算像素坐标时忘了加 1导致整块区域往左上角平移了一个像素。比如第 0 个块的行范围应该是 1 到 b他写成了 0 到 b-1最后算出来的异或值全都不对。我自己调试时的习惯是随意挑一个小数据手推一遍。比如 n4, b2, m2图片左上角四个 2×2 块手动按公式算一遍异或值再对着代码的中间变量检查。这比盯着屏幕空想要快得多。另一个好办法是在代码里临时打印x1, x2, y1, y2确认每个块的区间是不是想要的。检查完再删掉调试输出提交前一定要记得清理。4.3 坑三快速读入与多组样例CSP的题基本都是单组测试但偶尔会有多组。水印检查这道题我没遇到多组但保险起见可以在读入失败时直接结束也就是while (cin n b m) { ... }这样的写法。不过要注意的是如果题面明确说只有一个测试点写了 while 也没什么坏处只是多一层结构反过来如果题面有多组你不写 while 就会只处理第一组然后 WA这种失误太冤了。ios::sync_with_stdio(false); cin.tie(nullptr);这两行是 C 选手的标配。我在考场上会先写好这两行再加算法代码省去输入量稍大时的 IO 性能焦虑。使用 getchar 手写快读在 CSP 前两题完全没必要cin 开了开关足够快别给自己增加出错可能。4.4 坑四样例全过但WA问题在哪儿如果你样例全过但还是 WA先别怀疑人生按优先级检查三件事第一输出的是不是题面要求的那个统计量第二水印矩阵的遍历顺序是不是按输入顺序第三块边界是不是有越界。其中“遍历顺序”尤其阴险有些题的水印矩阵可能按行主序给出但实际校验时按列主序要求一旦顺序搞错特征值全对不上。再有就是异或值的类型问题。像素值范围是 0 到 255异或结果也在 0 到 255 之间用 int 完全够。但如果你图省事用了 char读入时可能会被当成 ASCII 符号导致数据错乱。我的建议是全程用 intvector 不要用 short 或者 char 存像素。竞赛环境里内存管够不需要在这些小地方抠。5. 同类题扩展与复习建议5.1 矩阵分块题的通用套路水印检查这道题属于一个更大的题型矩阵区域统计。无论题目包装成“水印检查”“农田灌溉”“区域求和”还是“异或校验”核心都是给你一个二维数组要求频繁查询某个子矩阵的某种汇总值。这种题的通用解法就是二维前缀和家族求和用普通前缀和求异或用异或前缀和求最大值可以用二维 RMQ求平均值也离不开前缀和。建议你在赛后把这道题和以下变体一起练给一个 n×n 矩阵m 次询问某个子矩阵的元素之和再练一个“子矩阵异或和”版本如果还想加难度可以试试“子矩阵内是否有重复值”这类题目。你会发现底层结构都是类似的熟练之后一眼就能看穿题面包装直接进入算法设计阶段。这就是为什么我说水印检查是“良心模拟题”它不考偏题怪题考的是基础工具迁移能力。5.2 从这题看CSP前两题的命题规律复盘第39次CSP前两题第一题是直观的几何计算第二题是分块模拟整体难度在逐年微调但大方向稳定第一题考“能不能动手算”第二题考“能不能把题面翻译成循环”。所以准备前两题的重点不是刷难题而是练读题准确度和边界处理能力。像水印检查这种题认认真真读懂题面半小时内写完代码是正常水平。现在CSP考试的报名人数越来越多像一些考区比如2026年贵州考区的报考人数也在涨以后前两题大概率还是会保持这种“包装复杂、内核简单”的风格。你可以提前熟悉一些常见包装词汇水印、校验、加密、评分、排序。看到这些词第一反应不是害怕而是问自己四个问题输入格式是什么要输出什么数据范围多大能不能直接模拟这四个问题回答完题基本就做了一半。5.3 考场上如何安排时间CSP 4小时5道题前两题是保底分。我的建议是前两题一共控制在 50 到 60 分钟以内能写多快写多快但不要为了快牺牲读题。写完样例立刻检查一眼输出项和边界再做第三题。如果第二题是我这种“读完就懂但细节多”的模拟题我会在草稿纸上把块坐标换算的例子先推一遍再开始敲代码宁可多花三分钟也不要调试半小时。最后分享一个个人习惯水印检查这类题写完代码后我会人为构造一个 n2, b1, m2 的最小样例手算验证。b1 时每个块只有一个像素异或值就是像素本身整个过程退化成最朴素的矩阵比对逻辑对错一眼就能看出来。这个“降维测试法”帮我抓到过好多次下标漏洞你也可以试试。用它确认核心逻辑无误后再换大一点的样例验证块划分基本上就能安心提交了。