坦白说第39次CSP认证的题目一出来我第一时间去看了第二题“水印检查”。这道题给我的第一印象就是典型的“冷静题”场景包装得很贴近实际但底层逻辑仍然是矩阵处理、枚举判断、边界条件管理这一套。只要你能在考场上把它读懂不慌不忙地把数据结构选对满分基本是稳的。很多选手栽在第二题不是不会做而是被题目描述绕晕了或者在某个边界条件上翻车。这篇复盘我就把这道题从读题到实现完整拆开讲一遍重点聊聊为什么这类题要用二维前缀和思想以及“异或”到底在这里扮演了什么角色。先说一个背景CSP认证是很多计算机专业学生和算法爱好者都要经历的一关近几届报名人数一直在涨第二题作为“高分拉开差距”的关键题稳定拿满分的重要性甚至超过第四、第五题的思考深度。为什么因为第一题太简单第三题开始难度跳升第二题就成了绝大多数参赛者分数结构里的“压舱石”。水印检查这道题名称看起来不像算法题实际上考的点非常典型给你一张大图和一个水印模板需要你判断图像里是否存在某块区域与模板匹配。别小看这个匹配动作它可以把暴力枚举、异或前缀和、必要剪枝这些经典技巧全部串起来。1.1 题目本质把“找水印”翻译成矩阵匹配我按考场上最常见的题意描述来还原这道题的核心。题目一般会给一个n行m列的像素矩阵A再给一个大小明显小很多的p行q列水印模板B。你需要从A中找到一个同样大小的区域使得这个区域的“某种一致性指标”和B保持一致从而判断水印是否存在。由于CSP第二题不会真的让你做图像特征提取它考的仍然是离散的数值矩阵所以本质上就是区域匹配。这里有个很容易误解的点题目不一定要求完全相等可能允许一定误差。比如规定某个阈值范围内的差值可以接受或者要求区域内的异或值与模板的异或值相等。这类“放宽条件”的设定正是为了考察你对条件判断的灵活处理。如果你在考场上死记硬背“整块完全一致”的模板解法遇到允许误差的版本就会写崩。所以拿到题目的前两分钟建议把所有条件用表格列出来哪些是硬性条件哪些是带容错的指标再决定算法框架。很多人看到矩阵匹配第一反应是“滑动窗口暴力扫一遍”。这个思路没有错但要注意复杂度。假设n和m最大是1000p和q最大是100那窗口数量大约是(1000-1001)的平方量级每个窗口内部再逐个点比较总操作量会到亿级别。CSP第二题的时限通常不会宽松到让你随便跑所以必须引入剪枝或者预处理。二维前缀异或就是一个非常优雅的预处理方案。1.2 为什么第二题值得专门写一篇复盘网上关于CSP的题解大多是“讲个思路贴个代码”很少解释这个思路是怎么一步步长出来的。我这篇想换个角度把从“看到题目”到“提交满分”的完整心路过程写出来。特别是题目里的“水印”场景很多人被这个词吓住以为需要图像处理知识其实跟图像算法一点关系都没有纯粹是矩阵数值游戏。我相信第二题对那些准备2026年CSP考试的朋友来说是性价比最高的一题值得花时间彻底吃透。第二个原因是这道题在优化路径上非常有代表性。暴力能过吗小数据能过。大数据过不了。怎么优化你可能会想到把每个点哈希成某个值再用哈希前缀和判断区域是否一致但哈希需要取模和乘法容易有冲突和溢出。异或前缀和则完全避开了这些问题它天然满足“可逆操作”同一个数异或两次等于什么都没做。这个性质在做区域比较时非常好用而且写起来极其简洁。不夸张地说如果你把水印检查这道题做透了二维前缀和、异或操作、边界处理这三板斧基本就练熟了后续遇到很多矩阵区域的题目都能顺手用上。2. 从暴力到优化整个思路是怎么一步步长出来的2.1 第一版想法直接滑动窗口逐点比对我拿到题目后第一版想法肯定是最朴素的枚举A中每一个可能的左上角位置然后让B中的所有点逐一对齐去比较。比如图像大小是n×m水印大小是p×q我需要枚举(n-p1)×(m-q1)个位置每个位置内部再比较p×q个值。如果题目限定的数据范围是n,m≤300且p,q≤10那这个暴力完全够跑根本不用优化。但如果数据范围升级到n,m≤3000p,q≤100暴力的总操作量大约就是2910×2910×100×100算下来接近850亿次比较CPU跑一年都跑不完。这时候你就能意识到必须给每个候选窗口找一个O(1)或者O(log)级别的预筛手段。这里的“预筛”不是直接判断整块区域是否匹配而是先算一个“指纹”指纹不一致就pass掉指纹一致再进去逐点核对。这个思路是很多图像检索系统的底层逻辑在大数据场景下先用粗粒度指纹淘汰大量候选再用精确匹配做最后确认。有了这个想法问题就变成“指纹用什么数据结构来算”。比较自然的是二维前缀和把矩阵A和B都各自算出一个二维前缀和然后用容斥公式在O(1)时间内取出任意矩形的和比较和是否相等。如果和不同说明区域百分百不匹配如果和相同也不一定真匹配需要进一步逐点验证。但这里有个小问题前缀和是数值累加如果像素值很大区域和很容易爆int用long long虽然能解决但计算量稍重。如果你只需要一个快速指纹完全可以用异或代替加法。2.2 优化切入点用二维前缀异或先当“探针”这里要解释一下为什么异或适合做区域指纹。异或运算有结合律、交换律并且一个数和自己异或结果为00与任何数异或还是那个数。从数学性质上说异或可以被看作是一种“不带进位且不可逆运算的加法”。如果你用一个区域所有像素的异或结果作为指纹那么两个区域即使数值分布不同也可能碰巧得到相同的异或值比如t和(t3)这种变化但整体来说这个指纹已经能过滤掉绝大多数明显不一致的候选。如果题目考察的恰好就是“区域异或值等于模板异或值”那就更省事了因为异或结果成了题目本身的判定条件而不只是预筛工具。这时候二维异或前缀和几乎就是标准解法。你先把图像A所有元素的二维异或前缀和算出来再把模板B所有元素的异或值算出来然后遍历每个候选区域取出区域异或值跟模板异或值比较。如果不相等直接跳过如果相等再根据题意判断是否需要逐点验证。这一步的复杂度从暴力的“窗口数×区域大小”降到了“窗口数×O(1)”是质的飞跃。可能有人会问为什么不用哈希我个人的经验是哈希做区域等值判断需要设计合适的哈希函数还要处理取模冲突调试起来比较麻烦。而异或运算不需要取模不需要担心溢出代码写出来就是一排位运算跑起来飞快尤其适合CSP这种对稳定性和可读性要求都很高的比赛环境。当然异或的冲突概率比设计良好的哈希要高一些所以需要配合“如果指纹相等再逐点核对”的二次验证否则可能把不匹配的区域误判成水印。2.3 二维前缀异或的下标推导写错的人特别多二维前缀异或的具体写法其实跟二维前缀和一模一样。我们定义pre[i][j]表示从图像左上角(1,1)到(i,j)这个矩形区域所有元素的异或值。递推公式是pre[i][j]pre[i-1][j]^pre[i][j-1]^pre[i-1][j-1]^A[i][j]。为什么要异或pre[i-1][j-1]因为pre[i-1][j]和pre[i][j-1]这两个区域重叠了左上角的(1,1)到(i-1,j-1)那一块那样一块被算了两次异或两次会抵消所以要在式子里再补异或一个pre[i-1][j-1]让它恢复成“只算一次”的状态。取任意矩形区域(r1,c1)到(r2,c2)的异或值时公式是pre[r2][c2]^pre[r1-1][c2]^pre[r2][c1-1]^pre[r1-1][c1-1]。这跟二维前缀和取子矩阵和的容斥公式结构一模一样只是一个用加法一个用异或。很多同学写二维前缀和时容易把这个式子写成“加上左上角”在普通前缀和里加错了可能只是结果偏大在异或里加错了那就是整片区域全乱套。我的建议是不要死记公式而是理解成“用大矩形减掉左边多出来的条减掉上边多出来的条再把重复减掉的左上角补回来”。对异或来说“减”和“补”都对应一次异或操作。还有一个细节下标从1开始还是从0开始。我强烈建议CSP这种比赛里矩阵下标统一从1开始放弃第0行第0列把pre数组第0行第0列全部初始化成0。这样做有两个好处第一递推公式里pre[i-1][j]在i1时访问的是pre[0][j]结果都是0不会越界第二取区域时r1-1和c1-1最小为0依然在数组范围内。如果非要用0下标你就要在每个递推和查询里写if判断又啰嗦又容易错。我的习惯是输入数据在读的时候直接存到下标1到n、1到m的位置第0行第0列留空。3. 代码落地一份能直接跑通的C框架3.1 读入与预处理阶段我平时在CSP考场里习惯用C因为输入输出快而且vector的内存管理比原生数组更安全。水印检查这道题数据范围允许的情况下用vectorvector 存矩阵最稳。代码的第一步是读入n、m、p、q和矩阵A、模板B。这里有个容易忽略的点CSP第二题的数据规模虽然不大但n和m可能不是同一个量级所以开数组时不要拍脑袋开一个固定的MAXN按题目上限来开即可。用vector的好处是动态分配不会因为极限数据开太大而爆内存。读入完成后预处理二维异或前缀和preA。这里我会单独写一个函数输入原始矩阵输出前缀异或矩阵代码结构更清晰。预处理模板B时不需要建二维前缀只需要用一个变量xorB累加B中所有元素。如果你担心后续需要验证模板的内部细节可以另存一份原始模板矩阵方便比较。很多人在这一步犯懒只算了一个异或值后面想逐点核对找不到原数据只能重新读很影响效率。预处理完成之后可以顺手算一下复杂度。假设n、m都是3000p、q都是100窗口总数大约是2910×2910约846万个。每个窗口一次O(1)的异或查询加上可能进入二次验证的少量窗口这个量级在1秒内完全是轻松跑完的。如果你用暴力逐点比较就跑到天荒地老了。这也是为什么这个优化思路在比赛里是“必做”而不是“可做”的原因。3.2 匹配校验函数必要条件与充分条件分开写匹配校验这一步我踩过坑必须重点说。我的建议是写两个职责不同的函数第一个叫fingerprintMatch只比较区域的异或值和模板的异或值是否相等第二个叫fullCheck真正逐点比较区域里每个元素和模板每个元素是否满足题目要求。为什么拆开因为fingerprintMatch会被调用几百万次必须尽可能快里面任何多余的逻辑都会拖慢整体时间而fullCheck只在指纹匹配相等时调用调用次数极少写慢一点完全没关系。如果你的题目判定条件是“区域异或值等于模板异或值”那fullCheck甚至都不需要写指纹就是最终答案。但如果题目要求“区域内每个位置都等于模板对应位置”那fullCheck就是必需品。判断不等时千万别顺手return false要等整块比较完再返回“是否全部匹配”。我最开始写fullCheck时用的是“发现一个不相等就立刻跳出”这没问题后来遇到过反向要求“判断是否存在水印”那就需要所有窗口里只要有一个满足就输出存在这时提前跳出会省时间但逻辑容易写反最好先想清楚是“找到就停”还是“全查完再定”。逐点核对的写法也不复杂取当前窗口左上角在A中的位置是(sx,sy)则A[sxi][syj]与B[i][j]对应。注意这里的i、j从0开始遍历到p-1、q-1别越界。模板B如果是从0开始存的就不用偏移如果是从1开始存的遍历时也要相应错开。这种“坐标平移”问题是第二题最常见的bug来源写完后一定要用小的手动样例自测。3.3 一个带注释的完整可运行框架下面这份C代码是我按“先指纹后验证”的思路整理的框架。它并不针对某个具体的输入格式而是给你一个非常接近考场写法的骨架你需要根据实际题目调整读入和判定逻辑。代码里我特意把注释写得比较细方便你对照上面的讲解理解。#include bits/stdc.h using namespace std; int n, m, p, q; vectorvectorint A, B, preA; // 建立二维异或前缀和preA[i][j]表示(1,1)~(i,j)的异或值 void buildPrefixXor() { preA.assign(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { preA[i][j] preA[i-1][j] ^ preA[i][j-1] ^ preA[i-1][j-1] ^ A[i][j]; } } } // 获取A中以(r1,c1)为左上角、(r2,c2)为右下角的矩形异或值 int getRegionXor(int r1, int c1, int r2, int c2) { return preA[r2][c2] ^ preA[r1-1][c2] ^ preA[r2][c1-1] ^ preA[r1-1][c1-1]; } // 逐点验证A从(sx,sy)开始与B完全匹配 bool fullCheck(int sx, int sy) { for (int i 0; i p; i) { for (int j 0; j q; j) { if (A[sx i][sy j] ! B[i][j]) return false; } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m p q; A.assign(n 1, vectorint(m 1, 0)); B.assign(p, vectorint(q, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { cin A[i][j]; } } for (int i 0; i p; i) { for (int j 0; j q; j) { cin B[i][j]; } } buildPrefixXor(); // 计算模板B整体的异或值 int xorB 0; for (int i 0; i p; i) { for (int j 0; j q; j) { xorB ^ B[i][j]; } } bool found false; // 枚举A中所有大小为p*q窗口的左上角 for (int sx 1; sx p - 1 n; sx) { for (int sy 1; sy q - 1 m; sy) { int ex sx p - 1; int ey sy q - 1; int curXor getRegionXor(sx, sy, ex, ey); if (curXor ! xorB) continue; // 指纹不一致直接跳过 if (fullCheck(sx, sy)) { // 指纹一致进入精确验证 found true; break; } } if (found) break; } if (found) cout Yes\n; else cout No\n; return 0; }这份代码里getRegionXor的调用非常频繁所以我没有在函数里加任何打印和多余判断。fullCheck的实参是窗口左上角在A中的坐标注意A中下标从1开始所以传sx和sy时直接传循环变量。B用0下标存储是因为fullCheck里的i和j从0遍历模板不参与矩阵A的前缀运算0下标读起来更自然。3.4 复杂度估算与提交策略让我们算一笔账。枚举窗口的双重循环一共迭代(n-p1)×(m-q1)次。每个窗口做一次四次异或的查询常数极小。如果nm3000且pq100窗口数大约846万个四次数组访问和三次异或运算总共几千万次操作在C里几十毫秒就跑完了。真正耗时的是进入fullCheck的窗口如果图像中频繁出现与模板异或值相同的区域fullCheck会拖慢速度万一数据刻意构造让几百万个窗口都满足异或相等那复杂度又会退化成暴力级别。应对这种最坏情况我见过两种处理办法。第一种是在指纹的基础上再加一个“行前缀异或”或“列前缀异或”做二级指纹比如对每行算个哈希先比较窗口每行的异或向量是否一致相当于把一次指纹变成多段指纹冲突概率大大降低。第二种是直接放弃指纹改用KMP的思想处理二维字符串匹配但代码复杂度飙升不适合CSP第二题。我的提交策略很务实先写暴力匹配验证正确性用题目给的样例跑通后再升级成指纹校验收尾。如果你一开始就写复杂的指纹逻辑很可能被下标问题搞晕反而不容易过样例。4. 考场上真实踩过的坑4.1 数组越界模板比图像大怎么办我在自测的时候构造了一个极端的casepn且qm也就是模板跟图像一样大。这种case看似无聊但非常能暴露下标问题。比如枚举窗口时如果你写成for (int sx1; sxn-p1; sx)而不是sxp-1n当p0或者pn时就会出问题。虽然题目数据大概率不会出现模板大于图像的情况但你最好在代码开头加一句防御if (pn || qm)直接输出No并return。这一句代码在正常数据下不会被执行却能让你的程序在特殊数据下不崩。另外还有一个很阴间的越界藏在fullCheck里。如果你在枚举窗口时用的是“左上角坐标模板大小”而不是“右下角坐标不超过边界”fullCheck里访问A[sxi][syj]时sxi可能超出n。CSP的测试数据不会允许越界但如果你写错边界自己造数据时又没覆盖提交后可能只是得了部分分却找不到原因。我建议调试阶段还是加上assert或者临时打印确认所有窗口的右下角都在n和m范围内再移除。4.2 异或相等不代表区域相等必要条件的坑这是第二题里最隐蔽的陷阱。指纹匹配只是必要条件不是充分条件。举个例子图像区域里是{1,2,3}模板是{1,3,2}两者的异或值都是1^2^3相等但逐点比对完全不同。如果你看到异或值相等就直接判“有水印”就会被这种构造数据卡掉。在实际比赛中相信命题组不会故意构造大量“异或相同但实际不同”的数据来恶心你但原理上必须做二次验证。我见过一些选手为了省事把fullCheck去掉结果样例全过提交后60分百思不得其解。其实原因就是他们用“异或值相等”替代了“区域相等”把必要条件当成了充分条件。反过来如果你确认题目的判定条件就是“区域异或值等于模板异或值”那fullCheck可以不加但前提是你必须仔细读题不能凭感觉。我个人的检查技巧是自己构造三个小矩阵第一个是完全匹配第二个是异或值相同但个别点不同第三个是彻底不匹配。分别跑一遍程序确认结果分别是Yes、No、No。这个自测过程花不了两分钟但能救命。考试的时候别急着提交至少建立这么一组“最小样本集”把常见bug都过滤掉。4.3 其他细节与常见问题速查表还有一些零碎问题我整理成了一张表方便你考试前扫一眼。这类细节单拿出来都不难但凑在一起很容易让人心态崩溃。问题常见原因解决办法样例能过大样例TLE暴力没剪枝窗口数太大使用二维前缀异或指纹减少逐点比较输出结果全是Yes把必要条件当充分条件漏了fullCheck指纹相等后再逐点核对一次数组越界崩溃下标从0开始或边界判断用了小于号统一从1开始枚举时用sxp-1n答案少找一个窗口枚举终点写错比如漏了最后一个位置手动算小矩阵检查窗口总数是否符合预期图像和模板尺寸很大时内存爆掉开了固定大小的全局数组且过大用vector动态分配按实际n、m申请最后还有一点很多人都忽略就是输入输出的关闭同步。CSP环境里经常用cin和cout如果不加ios::sync_with_stdio(false)和cin.tie(nullptr)遇到数据量稍大的测试点可能被IO卡掉几分。这不是什么高深优化纯粹是比赛习惯。我用C写题永远在第一行加上这两句已经成一个肌肉记忆了。5. 复盘第二题怎样练才能稳定满分5.1 把CSP第二题归类模拟、计数、小规模优化CSP第二题的风格历年都差不多基本就是“给你一个具体业务场景要你实现一个模拟或计数逻辑”。水印检查的核心是区域匹配属于“带条件的枚举”。把它归类后做题就有套路了先把输入和输出格式用草稿纸列清楚把每种条件翻译成代码里的if语句然后选一个在数据范围内不会超时的枚举方式。如果枚举太大就想想能不能用前缀和、差分、指针滑动这类经典技巧降低维度。我个人的经验是第二题的优化方向很少有特别花哨的绝大多数是“枚举所有可能状态但把状态内部的比较从O(k)降到O(1)”。水印检查的异或前缀和就是这个思想的典型代表。你把这个思想吃透以后遇到“统计矩阵中是否存在和为target的子矩阵”“寻找重复二维模式”这类问题思路会顺很多。备赛时不要只盯着题解试着把同一道题用暴力、优化、再优化三种方式分别写过你才真正掌握它。另外如果距离考试还有一段时间建议你把二维前缀和的加法版、异或版、乘法版都写一遍。加法版用来求子矩阵和异或版用来快速比较区域指纹乘法版配合取模做字符串哈希。这三种变体可以互相启发写熟了之后看到任何“某个矩形区域的某种聚合值”你都能条件反射地想到前缀数组。5.2 我自己的备考节奏和对这道题的最终体会我回顾自己备考CSP那阵子一天练两三道第二题专门训练“快速读懂题面一次写对边界”的能力。第一遍不求快做成什么样都行关键是跑通样例第二遍看时间努力在15分钟内写完第三遍直接在脑子里模拟不看编辑器把完整代码口述出来。这个训练对考试很有用因为CSP考场上第二题只要花时间就能做对但你浪费太多时间后面的大题就没得写了。水印检查这道题给我的最终体会是CSP认证更看重“稳定输出”而不是“灵光一现”。你用异或前缀和去优化一个第二题可能会让旁边的人觉得“哇这个选手好厉害”但其实它只是最朴素的空间换时间思路。真正拉开差距的是你能不能在没有调试器辅助、没有参考代码的情况下把下标、边界、必要条件和充分条件这些琐碎事情全部做对。把这道题的完整过程理顺比刷十道水题更有用。如果你现在正准备2026年的CSP考试我建议拿“水印检查”当第二题的专项练习。先自己写一版暴力再改造为异或前缀和最后再尝试扩展成“判断水印出现次数”的变体。这样一题三做你对矩阵匹配类题目的理解会超越大多数只在博客上看过一遍思路的选手。考试前一周把这道题的代码和易错点再过一遍第二题的基本盘就稳了。