很多刷《信息学奥赛一本通》的同学做到1123题“图像相似度”的时候看到题目名字多少会有点发怵——图像是不是要处理灰度、颜色直方图甚至卷积其实这道题被收录在“多维数组”章节本质就是二维数组的遍历与逐元素比较和你在学校做的矩阵加法、矩阵乘法是一个路数。题目在OpenJudge NOI 1.8编程基础之多维数组里对应第6题名字也叫“图像相似度”。不管是准备NOIP、CSP-J还是学校的信息课期末考试这道题都属于必须稳稳拿分的类型。这篇文章我把题意拆解、算法思路、完整代码和几个最容易翻车的细节一次讲透看完你可以直接照着写也能理解每一步为什么这么写。1. 题目拆解这道“图像题”到底在考什么1.1 题面解读与输入输出格式先别急着写代码把题面彻底读懂永远是第一步。题目把图像抽象成了由0和1组成的矩阵0代表白色像素1代表黑色像素。输入分三部分第一行两个整数n和m代表图像的行数和列数紧接着n行每行m个整数是第一幅图像的像素值再接着n行每行m个整数是第二幅图像的像素值。输出要求输出一个实数表示两幅图像的相似度保留两位小数后面带一个百分号“%”。这里有两个信息容易被忽略。第一像素值只有0和1这意味着我们判断“相同”的时候只需要关心两个数字等不等不需要考虑任何颜色空间或者阈值问题。第二输出末尾要带百分号这个百分号是实际丢分点之一。很多人算出了66.67却忘了在输出里加“%”直接WA掉。建议读题时养成习惯把输入格式和输出格式两段完整抄到草稿纸上逐字对照尤其是输出格式。1.2 相似度计算的核心公式题面里“相似度”的定义是两幅图像中对应位置像素相同的比例。翻译成人话就是——把两个矩阵叠在一起一个格子一个格子地看数一数有多少个格子里的数一样然后除以总格子数。数学表达式写出来是这样相似度 相同像素个数 / (n × m) × 100%举个例子如果图像是3行3列一共有9个像素其中6个位置相同那么相似度就是6/9×100% 66.67%。题目要求保留两位小数所以输出66.67%。这个公式本身没有任何难点真正的坑藏在后面的代码实现里整数除法的截断、浮点数精度、输出格式控制。我会在第四部分专门讲这里先记住一个原则——计算相似度时一定要让浮点数参与运算否则小数部分会被C直接吃掉。2. 算法设计与复杂度分析从题意到代码只需三步2.1 逐像素对比的朴素思路拿到这道题最忌讳的是想太多。我在群里见过有同学问“要不要先做图像二值化”“是不是得用感知哈希算法”这些都是被“图像”两个字带偏了。信息学奥赛的题目经常用现实场景做包装但考察的就是最基础的数组操作。这道题的算法思路可以压缩成三句话用一个二维数组a读入第一幅图像的像素值。用一个二维数组b读入第二幅图像的像素值。双层for循环遍历所有位置凡满足a[i][j] b[i][j]就计数加一。就这么简单。不需要排序、不需要查找、不需要任何优化技巧就是“暴力模拟”。很多同学会纠结一个问题能不能边读入第一个矩阵边读入第二个矩阵省一次循环千万别这么干。输入数据在文件里是先后排列的第一幅图全部读完之后第二幅图的数据才出现。你要是交错着读读出来的b矩阵就会错位整个相似度计算全部作废。老老实实两个循环分开读代码看起来多几行但逻辑绝对清晰。2.2 时间复杂度与数据范围分析这道题的时间复杂度是O(n×m)。题目给出的n和m通常在100以内那么总共只有1万次比较运行时间用微秒计算都嫌多。哪怕n和m都放大到1000也就100万次操作对计算机来说仍然毫无压力。这里我要多说两句关于数据范围的习惯。信息学竞赛里拿到任何一道题第一步应该是看数据范围因为它直接决定你能用什么算法。看到n×m在百万量级以内就可以放心用最朴素的枚举如果看到n和m到了10的5次方你就要考虑前缀和、差分这类优化手段了。很多选手做题慢、想复杂根源就在于不看数据范围凭感觉选算法。这道题就是练习“估算复杂度”的好素材读完题先算一下确认枚举可行再动手写。3. 完整C实现与关键代码解读3.1 可直接提交的参考代码下面这版代码在OpenJudge NOI 1.8 06号题和《信息学奥赛一本通》1123题下都可以直接AC。我用的是C因为竞赛里C覆盖率最高代码也最直观。#include iostream #include iomanip using namespace std; int a[105][105], b[105][105]; int main() { int n, m; cin n m; // 读入第一幅图像 for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } // 读入第二幅图像 for (int i 0; i n; i) { for (int j 0; j m; j) { cin b[i][j]; } } // 统计相同像素个数 int same 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] b[i][j]) { same; } } } // 计算相似度并输出保留两位小数 double result 100.0 * same / (n * m); cout fixed setprecision(2) result % endl; return 0; }3.2 关于全局数组与循环边界的解释代码里我开了a[105][105]和b[105][105]两个全局数组而不是在main函数里声明局部数组。两个原因第一全局数组会由系统自动初始化为0局部数组如果不手动初始化里面存的是内存残留的随机值虽然这道题里所有数组元素都会被读入覆盖但这个习惯本身值得保持第二在部分竞赛环境中比较大的局部数组可能引起栈溢出而全局数据区的空间要大得多。105这个数字是我习惯性的写法题目范围如果是100就开105留几个单位的余量防止边界判断失误时越界访问。循环边界是二维数组题目的经典坑。数组下标从0开始所以行循环从0到n-1列循环从0到m-1。新手最容易写成i n或者j m一越界本地运行可能一切正常因为编译器没做边界检查但到了OJ上就会以各种奇怪的形式报错——有时候是WA有时候是RE。我自己的习惯是所有循环边界都写成i n这样“左闭右开”的形式并且在心里默念“从0到n-1总共n个”避免思维惯性导致多跑一次循环。3.3 为什么用100.0而不是100计算结果的这一行是整个程序的关键double result 100.0 * same / (n * m);这里的100.0不是随手写的而是故意为之。因为same、n、m都是整数如果在C里写100 * same / (n * m)它会先做整数乘法得到整数再做整数除法结果的小数部分直接被截断。比如100 * 6 / 9整数除法结果是66就算赋给double类型变量得到的也是66.0而不是66.666...写100.0之后100.0是浮点数整个表达式自动提升为浮点运算100.0 * 6 / 9的结果就是66.666...赋给double变量后精度完整保留。这是C面试和竞赛里都常考的“隐式类型转换”知识点在这个题目里以最直观的方式呈现出来。4. 从AC到WA最容易翻车的三个细节4.1 读入顺序两片矩阵不能交错读第一个翻车点是读入顺序。这个坑我在文章第2部分提过但因为它真的特别容易犯值得单独再强调一次。有些同学写代码时想偷懒想用一个双重循环把a和b都读完// 错误示范 for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j] b[i][j]; } }这段代码的问题在于输入文件里前n行全是第一幅图像的数据后n行才是第二幅图像的数据。你这样交错读会把第一幅图像的第1个像素当成b[0][0]第一幅图像的第2个像素当成b[0][1]得到的b矩阵完全错位。更隐蔽的是程序不会报错甚至会正常输出一个“相似度”导致你很难意识到逻辑已经错了。正确的做法就是文章中那种“先完整读a再完整读b”两个独立的双层循环。竞赛里不需要这种“节省一遍循环”的伪优化可读性永远比那几微秒重要。4.2 整数除法陷阱一个小数点引发的血案第二个翻车点是整数除法这个也是“看着简单一提交就WA”的高频原因。我已经提到过100 * same / (n * m)会先做整数乘法再做整数除法结果截断小数点。但还有更隐蔽的写法错误比如有人写成double result same / (n * m) * 100.0;这段代码的问题出在运算顺序上same / (n * m)两个整数相除先执行结果已经是0了比如same6n*m9整数除法6/90再乘100.0还是0。最后输出0.00%你肯定一脸懵觉得公式明明是对的。这提醒我们一个写代码的原则在涉及除法的计算里把浮点数放在最前面参与运算比如写成100.0 * same / (n * m)这样乘法和除法按照从左到右的顺序执行第一步就出现了浮点数后续全是浮点除法万无一失。4.3 输出格式fixed与setprecision必须成对使用第三个翻车点是输出格式。题目要求保留两位小数代码用了cout fixed setprecision(2) result % endl;fixed和setprecision(2)是配合使用的缺一不可。setprecision在单独使用的时候控制的是“有效数字位数”不是“小数位数”。比如result是85setprecision(2)输出的可能是85因为85有两位有效数字而不是85.00如果result是66.666单独用setprecision(2)会输出66.67看起来碰巧对了但遇到整数值就会原形毕露。而fixed的作用是把输出模式切换成“固定小数点表示法”此时setprecision(2)才表示“小数部分保留2位”。两者结合无论结果是整数还是循环小数都能保证输出恰好两位小数。这也是为什么我强调输出格式必须逐字对照题目要求的原因——很多时候你的算法完全正确就输在格式上。5. 自测用例、调试思路与同类题延伸5.1 设计几组自测数据快速验证代码写完不能直接提交先自己造几组数据验证逻辑。我给你准备了三组测试用例覆盖了最常见的情况。第一组完全相同。如果两幅图像一模一样相似度应该是100.00%。3 3 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1第二组完全不同。把第一幅图像里的0全部换成1、1全部换成0相似度应该是0.00%。3 3 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0第三组部分相同。用下面这组数据验证66.67%的输出。3 3 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1我建议你在本地编译器里跑一遍这三组数据确认输出分别是100.00%、0.00%、66.67%。尤其是第三组亲手口算一遍相同位置的个数再对照程序输出能帮你提前发现公式或格式问题省下一次提交WA的等待时间。OJ上的提交次数有时候也影响排名和评判体验能本地排查的问题就不要浪费到线上。5.2 一条临时调试语句的妙用如果程序输出结果和你预期不符最快的定位方式不是盯着代码干瞪眼而是在统计循环后面加一条临时输出cout same same endl;这条语句能直接告诉你在你的输入数据下统计出的相同像素个数是多少。举个例子如果你手算第三组测试数据时得到same6程序却输出4说明比较逻辑或者数组读入有问题这时候再去检查是不是读入顺序错了、是不是数组下标越界方向就非常明确。确认无误后把调试语句删掉再提交。这个小技巧听着简单但对新手来说很实用。很多同学遇到WA就慌了改来改去越改越乱就是因为没有把“中间结果”暴露出来全靠猜。调试的本质就是“定位问题”而定位问题的最好方式就是缩小范围——先确认count对不对再确认double计算对不对再确认输出格式对不对一步一步锁死。5.3 由图像相似度延伸出去的矩阵题把这道题吃透之后可以顺手做几道同类型的题目巩固一下。《信息学奥赛一本通》多维数组章节里的“图像模糊处理”和“矩阵旋转”都是基于二维数组遍历的变形题。图像模糊处理的核心是把每个像素替换成周围像素的平均值相当于在二维数组上进行邻域操作矩阵旋转则需要你找出行列下标之间的映射关系。这些题用到的双重循环、边界控制和类型转换和图像相似度完全同源。另外还可以自己给自己出题比如把图像相似度升级为“找出两幅图像中最大的相同子矩阵”那就要引入枚举起点加逐行比较的算法难度立刻上升一个档次。但不管怎么变二维数组逐元素比较这个基本功是不变的。把简单题做透、做稳比刷十道一知半解的难题有用得多。最后再分享一个我自己的做题习惯凡是涉及二维数组的题我拿到手第一件事就是把样例输入抄在草稿纸上手算一遍预期输出然后再写代码。这道图像相似度题虽然简单但正是这种“先手算、后编码”的习惯能在比赛里帮我省下大量调试时间也避免了因为读错题而浪费整场比赛的尴尬。希望对刷《信息学奥赛一本通》1123的你有所帮助。