1. 题目速览与核心考点信息学奥赛一本通里的1123题“图像相似度”在OpenJudge NOI题库中的编号是1.8的06题。如果你正在刷一本通或者OpenJudge的题单大概率会在这个位置碰到它。这道题属于“二维数组”章节的入门题目核心任务是给定两个同样尺寸的黑白图像用0和1构成的矩阵表示让你计算它们的相似度也就是相同位置上像素值相同的比例。最终输出一个百分数保留两位小数。题目本身不复杂但作为入门二维数组的经典练习题它的价值远不止“能过评测”这么简单。这里我会从题目解读到代码实现再到常见坑点完整地拆一遍——尤其是那些“为什么这么写”的关键点我会尽量讲透。因为很多新手写这道题代码能ACAccepted但说不清细节这对后面的矩阵类题目如旋转、翻转、边界处理是很不利的。1.1 题目原文再理解先明确题目的输入输出格式。输入第一行是两个整数n和m表示图像的行数和列数。接下来会有 2 * n 行数据每行 m 个整数——前 n 行是第一个图像矩阵后 n 行是第二个图像矩阵。比如说下面这组数据3 3 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 0两个矩阵都是3行3列。第一个图像是1 0 1 0 1 0 1 1 0第二个图像是1 0 0 0 1 0 1 1 0逐个位置比较两个矩阵中一共有8个位置的数值相同从左到右、从上到下逐格看只有第一行第三列不同一个是1一个是0总共有 3 * 3 9 个像素点所以相似度就是 8.0 / 9.0 * 100 88.89%。这里就涉及第一个易错点读入的时候不要把它当成一个连续的矩阵来处理。它实际上是依次读入两个独立的矩阵而不是一个跑完再处理另一个。很多新手会试图用一个二维数组一口气存下 2*n 行数据然后再用中间行号切开——这样做能实现但容易引入判断逻辑错误。更稳妥的方式就是老老实实定义两个数组分别存储。1.2 数据范围与时空限制题目给出的数据范围通常是 n, m ≤ 100也就是最多 10000 个像素点。这个规模很小用暴力枚举的方式完全没问题。时间复杂度 O(nm)空间复杂度 O(nm)如果你开两个数组或者 O(1)如果采用边读边比的策略但这个后面再说因为需要设计好读入顺序。在NOI / OpenJudge这类评测环境中这个题目的时间限制通常是 1000ms内存限制 65536KB64MB。就算你开两个 100x100 的 int 数组每个才 4 字节 * 10000 40KB两个也才 80KB完全不用担心内存问题。2. 核心算法思路拆解这一节重点说清楚两件事第一这道题“应该”怎么想第二为什么这个思路是最合理的有没有其他思路。2.1 暴力枚举的思路为什么合理图像相似度的计算本质就是“逐像素比较”。这不需要任何高级的算法技巧双重循环遍历矩阵中每个坐标 (i, j)比较 image1[i][j] 和 image2[i][j] 是否相等即可。用一个计数器累加相同个数。为什么暴力枚举在这里是最优解因为题目要求比较所有位置没有任何信息可以跳过某些区域的比较——除非两个图像之前已经有某种索引或哈希预处理。但对于这种 n,m≤100 的规模预处理反而更慢、更复杂。程序员经常犯的错误在这里刚好是反的——不是想不出暴力而是总觉得“这题应该有什么高深解法”非要自己绕远路。这道题要教你的核心只有一个二维数组怎么遍历、怎么比较、怎么统计。它不像后续某些题目需要优化到 O(n log n) 甚至更优这一题 O(n*m) 已经天花板了因为每个像素必须比较一次。2.2 读入时的坑到底要开几个数组我见过很多学生在做这题时写出类似这样的代码int a[105][105], b[105][105]; for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, a[i][j]); for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, b[i][j]);这是最标准、最不会出错的写法先完整读入第一个矩阵再完整读入第二个矩阵。有的同学想省数组试图边读第一个矩阵边读第二个矩阵的对应行int a[105][105]; for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, a[i][j]); int cnt 0; for (int i 0; i n; i) { int x; for (int j 0; j m; j) { scanf(%d, x); if (x a[i][j]) cnt; } }这个也能过因为输入格式决定第二个矩阵一定跟在第一个矩阵后面你可以边读边比。这种写法在竞赛中叫做“在线处理”好处是省了一个数组的空间坏处是代码可读性稍差而且如果以后题目改成先输入两个矩阵再让你做其他操作这种边读边比的模式就不能复用了。我的建议是新手阶段老老实实开两个数组把读入和计算拆开。理由有三个。第一逻辑清晰。读入是一回事计算是另一回事两者混在一起会增加心智负担。 第二调试方便。如果你发现结果不对可以单独输出两个矩阵的内容人工检查是否读入正确。 第三比赛的惯例。NOI系列竞赛中很多题目读入后还需要多次访问矩阵数据你不可能总是把“读入”和“处理”绑在一起。尽早养成“先完整存储、后统一处理”的习惯后面做矩阵旋转、转置、连通块等题目会顺很多。2.3 相似度计算的数学表达公式是相似度 (相同像素个数 / 总像素个数) × 100%这个公式本身不难但真正容易出错的地方是总像素个数和相同像素个数的类型转换。总像素个数是 n * m其中 n 和 m 都是 int 类型相乘结果也是 int。相同像素个数 cnt 也是 int。如果你写double ans cnt * 100.0 / (n * m);整除的问题就避免了因为乘以了 100.0 这个 double 类型的常量。关键点在这里一定不能让整数除以整数否则发生整数除法截断比如 8 / 9 0再乘以100还是0答案就变成 0.00 了。虽然你这么写会得到一个“精确”但错误的整数0评测系统毫无疑问会判定Wrong Answer。所以我写这道题时固定会用double ans cnt * 100.0 / (n * m);或者更稳妥double ans cnt * 100.0 / (1.0 * n * m);后者是把所有量都显式转成 double彻底避免整型溢出的歧义。对于这个数据范围来说 n*m 最大不过10000int 完全够用但养成“计算时用 double 接住”这种习惯绝对不吃亏。2.4 双重循环的两种方向实现双重循环时外层循环一般用 i 遍历行0 到 n-1内层用 j 遍历列0 到 m-1这是最自然的方式因为输入也是逐行给出的。for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] b[i][j]) { cnt; } } }反过来用外层循环遍历列、内层遍历行也是可以的结果不变。但在大多数竞赛题里图像数据的索引方式是“先行后列”也就是行优先。这种遍历顺序和存储顺序一致在C的二维数组中还涉及缓存局部性的问题——按行遍历比按列遍历命中缓存更高。虽然在这个数据规模下完全无所谓但如果你以后做高性能计算或图像处理行优先遍历是很重要的基础概念。3. 从思路到代码两种实现风格3.1 C风格实现用 scanf / printf这种写法适合一本通和OpenJudge的默认环境也是老选手最常用的#include cstdio int a[105][105], b[105][105]; int main() { int n, m; scanf(%d%d, n, m); for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, a[i][j]); for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, b[i][j]); int cnt 0; for (int i 0; i n; i) for (int j 0; j m; j) if (a[i][j] b[i][j]) cnt; double ans cnt * 100.0 / (n * m); printf(%.2lf\n, ans); return 0; }把数组定义放在 main 函数外面也就是作为全局变量。这样做的好处是全局变量会被自动初始化为0而且在竞赛环境中全局变量分配到静态存储区不容易因为递归或大型局部变量导致栈溢出。虽然这里用不到这些特性但这是一个好习惯。输出格式中的%.2lf表示保留两位小数输出 double。注意你输出的百分号不需要额外转义因为在 printf 的格式串中%不是特殊字符只有%d、%f这种组合才表示格式占位符。如果你要输出一个普通的百分号字符才需要写%%。回到这道题如果你直接输出88.888889而不是88.89会被判为 Wrong Answer。所以%.2lf是必须的。3.2 C风格实现用 cin / cout用 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 cnt 0; for (int i 0; i n; i) for (int j 0; j m; j) if (a[i][j] b[i][j]) cnt; double ans cnt * 100.0 / (n * m); cout fixed setprecision(2) ans endl; return 0; }fixedsetprecision(2)的作用是固定小数点后输出两位。如果你只写setprecision(2)而不加fixed它表示有效数字位数而不是小数位数结果可能变成88.9这种一位小数的形式一样会WA。这个坑在后面很多输出题里都会遇到早点记住。两种风格对比一下对比项scanf/printfcin/cout输入输出速度快默认较慢但本题规模影响不大格式化控制%.2lf直观需要fixedsetprecision配合代码风格C语言传统C风格适合STL配套使用易错点容易忘记类型符容易漏写fixed个人建议在NOI系列的评测环境中cin和cout通常已经够用但在有些OJ在线评测系统上数据量一旦上十万级cin不开同步关闭的话可能会超时。这里有个小金句竞赛不是考你用什么语言风格而是考你能不能稳定AC。如果对输入输出流的性能没把握直接上 scanf/printf 最稳妥。3.3 完整样例验算用上面那个样例跑一遍两个矩阵第一个1 0 1 0 1 0 1 1 0第二个1 0 0 0 1 0 1 1 0逐行逐列比对第0行11001!0 → 相同2个第1行001100 → 相同3个第2行111100 → 相同3个合计 cnt 2 3 3 8。总像素数 3 * 3 9。相似度 8 * 100.0 / 9 88.8888...保留两位小数输出 88.89。这就是标准答案。4. 输出格式与填坑指南这一节专门讲那些让新手“百思不得其解”的格式问题因为这类题目对输出格式的严格程度往往比算法本身更让学生抓狂。4.1 百分号要不要转义很多学生第一次做这道题时会想着输出一个百分号 “%” 在数字后面。比如写成printf(%.2lf%%\n, ans);如果题目明确要求输出“88.89%”这样写是对的%%表示一个普通的百分号字符。但如果题目只要求“88.89”多输出一个%就是画蛇添足绝对判错。请仔细阅读题目原文。我印象中一本通1123和OpenJudge 1.8 06题的要求是输出百分数但括号里通常会写明“输出一个实数表示相似度保留两位小数”或者“输出百分号”不同平台描述可能略有差异。如果题目没写要带 %就不要输出%如果写了要带 %就用%%转义。网上很多题解里给的代码并没有输出 %是因为他们测试的OJ数据格式恰好不需要。保险起见按你的评测平台要求来。4.2 浮点数精度问题8.0 / 9.0 * 100在计算机里存储时是 88.88888888888889二进制小数近似保留两位小数会四舍五入为 88.89。C语言的printf浮点数格式化采用的是“四舍六入五成双”还是“四舍五入”取决于底层实现但绝大多数情况下都是按四舍五入处理。这里不会出现边界上的奇怪偏差因为题目样例和测试数据不会设那种故意卡浮点数精度的极端值。不过如果你担心精度问题也可以不直接算百分比而是输出cnt * 10000 / (n*m) / 100.0这种整数运算后转浮点的方式。但这就属于过度设计了完全没有必要。4.3 输出样例对照法自测时最有效的方法是先运行程序输出结果再用样例输入核对。但光靠样例还不够因为你不知道隐藏测试点长什么样。这里分享一个我自己常用的“自造数据法”。故意构造两组极端数据第一组两个矩阵完全相同。2 2 1 0 0 1 1 0 0 1相似度应该是 100.00。如果你算出来不是100那说明计数器或格式有问题。第二组两个矩阵完全不同。2 2 1 0 0 1 0 1 1 0相似度应该是 0.00。同样任何非零输出都说明比较逻辑有误。第三组大小为 1 行 n 列例如1 5 1 0 1 0 1 1 1 0 0 1逐位比较相同位置为 第0位(11)、第3位(00)、第4位(11)所以 cnt3总像素5相似度 60.00。这种单行数据最容易暴露数组下标或循环边界问题。用这三组数据测过基本能确定代码逻辑正确。5. 常见错误与调试心得5.1 数组越界n, m≤100时很多人喜欢定义int a[100][100]。问题是如果 n 和 m 恰好等于100下标访问范围是 0 到 99那么a[99][99]是合法的但a[100][100]就越界了。有的直接定义a[105][105]或者a[101][101]多留几个单位的空间就是为了一劳永逸避免这个问题。在NOI系列题目中给数组“多开5个”是标准习惯例如数据范围是100就开105数据范围是1000就开1005。这不是洁癖是为了对付边界情况。5.2 计数器类型用错有人把 cnt 定义成 double这是没必要的而且会导致判断if (a[i][j] b[i][j])时 cnt 的行为没有任何不同但后面计算就麻烦了。最稳妥的做法是 cnt 用 int计算时乘以 100.0 来隐式转成 double。如果你把 cnt 定义成 double也不是不行但在某些复杂场景下浮点数循环累加会产生精度漂移。既然这里可以用整数何必自找麻烦5.3 忘记处理 n 或 m 为 0 的边界题目一般会保证 n, m 1但作为程序员的严谨性来说如果遇到 n0 或 m0你的代码会不会崩不会崩但可能会除零错误。竞赛题目里通常不会出现这种情况不过一旦出现程序就会Runtime Error。我在平时练习时会顺手加一行判断if (n 0 || m 0) { printf(0.00\n); return 0; }各自取舍不加也行因为题面不会出现这种数据。但对边界情况的敏感度是区分“能用”和“稳健”的分水岭。5.4 调试技巧打印中间结果很多新手一提交Wrong Answer就直接懵了不知道是读入错了、比较错了还是输出格式错了。我建议在调试时先打印中间结果for (int i 0; i n; i) { for (int j 0; j m; j) printf(%d , a[i][j]); printf(\n); } printf(cnt %d\n, cnt);确认 cnt 值和两个矩阵读入正确后再去检查输出格式。如果 cnt 正确但答案不对那就是输出格式或类型转换的问题如果 cnt 都不对那就检查读入逻辑。这个“先定位再修复”的思路比盲目改代码高效得多。提交前记得把所有调试用的 printf 去掉或者注释掉。我见过太多人AC的代码里留着调试语句好在不影响答案但如果是输出调试信息到标准输出一定会WA。所以调试要改代码测试完要还原。6. 题目之外的延伸思考这道题虽然简单但“图像相似度”这个概念在整个计算机领域无处不在。理解这个基础版本后可以帮你想通很多后续问题的本质。6.1 从像素相等到数值接近在实际图像处理中两张图片几乎不可能每个像素值完全相同——因为噪声、光照、压缩损失都会改变像素值。所以工业界常用的相似度计算通常不是“完全相等”而是“差值绝对值小于某个阈值”就算相似。用代码表示就是if (abs(a[i][j] - b[i][j]) 10) cnt;这里的 10 就是容差threshold。你在后续题目中可能会碰到类似“如果两个像素点的差值不超过20则认为这两个像素点相同”的描述。原理和本题一模一样只是把换成了abs(u-v)t。6.2 不只是百分比从相似度到匹配严格来说这道题算的是“一致率”或“重合率”不是广泛意义上的“相似度指标”。在计算机视觉中还有一种更常用的指标叫SSIM结构相似性指数它在亮度、对比度、结构三个维度上比较图像结果比像素重合率更符合人眼感知。SSIM的计算涉及均值、方差、协方差需要遍历图像两次甚至三次复杂度约 O(3nm)。虽然比本题复杂得多但核心思想都是从逐像素统计出发。如果以后你做到“矩阵匹配”“子图像查找”例如在大的图像矩阵里找一个小的模板矩阵那就要用到滑窗遍历相似度/距离计算核心思路会从“遍历全图”变成“遍历所有可能的左上角位置”然后同样用双重循环比较子区域。这些题目的一维基础就是这道1123题给你打的底子。6.3 二维前缀和能优化什么如果你在思考“能不能更快”可以提一个进阶概念假设我们要统计一个矩阵里“有多少个 1”比起每次用双重循环数可以先做二维前缀和然后 O(1) 查询任意矩形区域内 1 的个数。但本题要比较两张图的差异前缀和只能加速“统计区域内的值”不能加速“逐点比较”因为比较必须知道每个位置的具体值。所以这道题用前缀和没有意义。但有一些变种题比如“统计某个区域内有几个像素不同”可以通过分别对每个矩阵做前缀和再比较区域和的差值来快速判断是否可能不同。这时你就需要掌握前缀和这个工具了。这些都是后续的话题这里先留个钩子等你刷到二维前缀和的题目再回头理解会自然很多。6.4 一个刷题心态建议我发现有些读者看到这种“简单题”就直接跳过觉得“我一定会”。但在竞赛中真正决定成绩的往往不是难题而是简单题的手速和准确率。图像相似度这道题最典型的陷阱就是浮点输出格式。我见过太多水平不错的学生在这道题上因为输出88.888889而不是88.89被卡了好几次。这种问题在真正的竞赛中不会给你重测的机会一次提交就决定了分数。所以哪怕题目再简单也要亲手写一遍、提交一遍、跑满边界数据一遍。这种“不因简单而轻视”的态度是练习信息学奥赛最宝贵的财富之一。就我这些年的刷题和教学经验来看能把每道入门题都做到满分AC、代码清晰简洁、边界测试齐全的人后面学数据结构和算法时的爆发力往往远超那些“眼高手低”的学生。
图像相似度问题：二维数组遍历与逐像素比较的经典入门题
1. 题目速览与核心考点信息学奥赛一本通里的1123题“图像相似度”在OpenJudge NOI题库中的编号是1.8的06题。如果你正在刷一本通或者OpenJudge的题单大概率会在这个位置碰到它。这道题属于“二维数组”章节的入门题目核心任务是给定两个同样尺寸的黑白图像用0和1构成的矩阵表示让你计算它们的相似度也就是相同位置上像素值相同的比例。最终输出一个百分数保留两位小数。题目本身不复杂但作为入门二维数组的经典练习题它的价值远不止“能过评测”这么简单。这里我会从题目解读到代码实现再到常见坑点完整地拆一遍——尤其是那些“为什么这么写”的关键点我会尽量讲透。因为很多新手写这道题代码能ACAccepted但说不清细节这对后面的矩阵类题目如旋转、翻转、边界处理是很不利的。1.1 题目原文再理解先明确题目的输入输出格式。输入第一行是两个整数n和m表示图像的行数和列数。接下来会有 2 * n 行数据每行 m 个整数——前 n 行是第一个图像矩阵后 n 行是第二个图像矩阵。比如说下面这组数据3 3 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 0两个矩阵都是3行3列。第一个图像是1 0 1 0 1 0 1 1 0第二个图像是1 0 0 0 1 0 1 1 0逐个位置比较两个矩阵中一共有8个位置的数值相同从左到右、从上到下逐格看只有第一行第三列不同一个是1一个是0总共有 3 * 3 9 个像素点所以相似度就是 8.0 / 9.0 * 100 88.89%。这里就涉及第一个易错点读入的时候不要把它当成一个连续的矩阵来处理。它实际上是依次读入两个独立的矩阵而不是一个跑完再处理另一个。很多新手会试图用一个二维数组一口气存下 2*n 行数据然后再用中间行号切开——这样做能实现但容易引入判断逻辑错误。更稳妥的方式就是老老实实定义两个数组分别存储。1.2 数据范围与时空限制题目给出的数据范围通常是 n, m ≤ 100也就是最多 10000 个像素点。这个规模很小用暴力枚举的方式完全没问题。时间复杂度 O(nm)空间复杂度 O(nm)如果你开两个数组或者 O(1)如果采用边读边比的策略但这个后面再说因为需要设计好读入顺序。在NOI / OpenJudge这类评测环境中这个题目的时间限制通常是 1000ms内存限制 65536KB64MB。就算你开两个 100x100 的 int 数组每个才 4 字节 * 10000 40KB两个也才 80KB完全不用担心内存问题。2. 核心算法思路拆解这一节重点说清楚两件事第一这道题“应该”怎么想第二为什么这个思路是最合理的有没有其他思路。2.1 暴力枚举的思路为什么合理图像相似度的计算本质就是“逐像素比较”。这不需要任何高级的算法技巧双重循环遍历矩阵中每个坐标 (i, j)比较 image1[i][j] 和 image2[i][j] 是否相等即可。用一个计数器累加相同个数。为什么暴力枚举在这里是最优解因为题目要求比较所有位置没有任何信息可以跳过某些区域的比较——除非两个图像之前已经有某种索引或哈希预处理。但对于这种 n,m≤100 的规模预处理反而更慢、更复杂。程序员经常犯的错误在这里刚好是反的——不是想不出暴力而是总觉得“这题应该有什么高深解法”非要自己绕远路。这道题要教你的核心只有一个二维数组怎么遍历、怎么比较、怎么统计。它不像后续某些题目需要优化到 O(n log n) 甚至更优这一题 O(n*m) 已经天花板了因为每个像素必须比较一次。2.2 读入时的坑到底要开几个数组我见过很多学生在做这题时写出类似这样的代码int a[105][105], b[105][105]; for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, a[i][j]); for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, b[i][j]);这是最标准、最不会出错的写法先完整读入第一个矩阵再完整读入第二个矩阵。有的同学想省数组试图边读第一个矩阵边读第二个矩阵的对应行int a[105][105]; for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, a[i][j]); int cnt 0; for (int i 0; i n; i) { int x; for (int j 0; j m; j) { scanf(%d, x); if (x a[i][j]) cnt; } }这个也能过因为输入格式决定第二个矩阵一定跟在第一个矩阵后面你可以边读边比。这种写法在竞赛中叫做“在线处理”好处是省了一个数组的空间坏处是代码可读性稍差而且如果以后题目改成先输入两个矩阵再让你做其他操作这种边读边比的模式就不能复用了。我的建议是新手阶段老老实实开两个数组把读入和计算拆开。理由有三个。第一逻辑清晰。读入是一回事计算是另一回事两者混在一起会增加心智负担。 第二调试方便。如果你发现结果不对可以单独输出两个矩阵的内容人工检查是否读入正确。 第三比赛的惯例。NOI系列竞赛中很多题目读入后还需要多次访问矩阵数据你不可能总是把“读入”和“处理”绑在一起。尽早养成“先完整存储、后统一处理”的习惯后面做矩阵旋转、转置、连通块等题目会顺很多。2.3 相似度计算的数学表达公式是相似度 (相同像素个数 / 总像素个数) × 100%这个公式本身不难但真正容易出错的地方是总像素个数和相同像素个数的类型转换。总像素个数是 n * m其中 n 和 m 都是 int 类型相乘结果也是 int。相同像素个数 cnt 也是 int。如果你写double ans cnt * 100.0 / (n * m);整除的问题就避免了因为乘以了 100.0 这个 double 类型的常量。关键点在这里一定不能让整数除以整数否则发生整数除法截断比如 8 / 9 0再乘以100还是0答案就变成 0.00 了。虽然你这么写会得到一个“精确”但错误的整数0评测系统毫无疑问会判定Wrong Answer。所以我写这道题时固定会用double ans cnt * 100.0 / (n * m);或者更稳妥double ans cnt * 100.0 / (1.0 * n * m);后者是把所有量都显式转成 double彻底避免整型溢出的歧义。对于这个数据范围来说 n*m 最大不过10000int 完全够用但养成“计算时用 double 接住”这种习惯绝对不吃亏。2.4 双重循环的两种方向实现双重循环时外层循环一般用 i 遍历行0 到 n-1内层用 j 遍历列0 到 m-1这是最自然的方式因为输入也是逐行给出的。for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] b[i][j]) { cnt; } } }反过来用外层循环遍历列、内层遍历行也是可以的结果不变。但在大多数竞赛题里图像数据的索引方式是“先行后列”也就是行优先。这种遍历顺序和存储顺序一致在C的二维数组中还涉及缓存局部性的问题——按行遍历比按列遍历命中缓存更高。虽然在这个数据规模下完全无所谓但如果你以后做高性能计算或图像处理行优先遍历是很重要的基础概念。3. 从思路到代码两种实现风格3.1 C风格实现用 scanf / printf这种写法适合一本通和OpenJudge的默认环境也是老选手最常用的#include cstdio int a[105][105], b[105][105]; int main() { int n, m; scanf(%d%d, n, m); for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, a[i][j]); for (int i 0; i n; i) for (int j 0; j m; j) scanf(%d, b[i][j]); int cnt 0; for (int i 0; i n; i) for (int j 0; j m; j) if (a[i][j] b[i][j]) cnt; double ans cnt * 100.0 / (n * m); printf(%.2lf\n, ans); return 0; }把数组定义放在 main 函数外面也就是作为全局变量。这样做的好处是全局变量会被自动初始化为0而且在竞赛环境中全局变量分配到静态存储区不容易因为递归或大型局部变量导致栈溢出。虽然这里用不到这些特性但这是一个好习惯。输出格式中的%.2lf表示保留两位小数输出 double。注意你输出的百分号不需要额外转义因为在 printf 的格式串中%不是特殊字符只有%d、%f这种组合才表示格式占位符。如果你要输出一个普通的百分号字符才需要写%%。回到这道题如果你直接输出88.888889而不是88.89会被判为 Wrong Answer。所以%.2lf是必须的。3.2 C风格实现用 cin / cout用 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 cnt 0; for (int i 0; i n; i) for (int j 0; j m; j) if (a[i][j] b[i][j]) cnt; double ans cnt * 100.0 / (n * m); cout fixed setprecision(2) ans endl; return 0; }fixedsetprecision(2)的作用是固定小数点后输出两位。如果你只写setprecision(2)而不加fixed它表示有效数字位数而不是小数位数结果可能变成88.9这种一位小数的形式一样会WA。这个坑在后面很多输出题里都会遇到早点记住。两种风格对比一下对比项scanf/printfcin/cout输入输出速度快默认较慢但本题规模影响不大格式化控制%.2lf直观需要fixedsetprecision配合代码风格C语言传统C风格适合STL配套使用易错点容易忘记类型符容易漏写fixed个人建议在NOI系列的评测环境中cin和cout通常已经够用但在有些OJ在线评测系统上数据量一旦上十万级cin不开同步关闭的话可能会超时。这里有个小金句竞赛不是考你用什么语言风格而是考你能不能稳定AC。如果对输入输出流的性能没把握直接上 scanf/printf 最稳妥。3.3 完整样例验算用上面那个样例跑一遍两个矩阵第一个1 0 1 0 1 0 1 1 0第二个1 0 0 0 1 0 1 1 0逐行逐列比对第0行11001!0 → 相同2个第1行001100 → 相同3个第2行111100 → 相同3个合计 cnt 2 3 3 8。总像素数 3 * 3 9。相似度 8 * 100.0 / 9 88.8888...保留两位小数输出 88.89。这就是标准答案。4. 输出格式与填坑指南这一节专门讲那些让新手“百思不得其解”的格式问题因为这类题目对输出格式的严格程度往往比算法本身更让学生抓狂。4.1 百分号要不要转义很多学生第一次做这道题时会想着输出一个百分号 “%” 在数字后面。比如写成printf(%.2lf%%\n, ans);如果题目明确要求输出“88.89%”这样写是对的%%表示一个普通的百分号字符。但如果题目只要求“88.89”多输出一个%就是画蛇添足绝对判错。请仔细阅读题目原文。我印象中一本通1123和OpenJudge 1.8 06题的要求是输出百分数但括号里通常会写明“输出一个实数表示相似度保留两位小数”或者“输出百分号”不同平台描述可能略有差异。如果题目没写要带 %就不要输出%如果写了要带 %就用%%转义。网上很多题解里给的代码并没有输出 %是因为他们测试的OJ数据格式恰好不需要。保险起见按你的评测平台要求来。4.2 浮点数精度问题8.0 / 9.0 * 100在计算机里存储时是 88.88888888888889二进制小数近似保留两位小数会四舍五入为 88.89。C语言的printf浮点数格式化采用的是“四舍六入五成双”还是“四舍五入”取决于底层实现但绝大多数情况下都是按四舍五入处理。这里不会出现边界上的奇怪偏差因为题目样例和测试数据不会设那种故意卡浮点数精度的极端值。不过如果你担心精度问题也可以不直接算百分比而是输出cnt * 10000 / (n*m) / 100.0这种整数运算后转浮点的方式。但这就属于过度设计了完全没有必要。4.3 输出样例对照法自测时最有效的方法是先运行程序输出结果再用样例输入核对。但光靠样例还不够因为你不知道隐藏测试点长什么样。这里分享一个我自己常用的“自造数据法”。故意构造两组极端数据第一组两个矩阵完全相同。2 2 1 0 0 1 1 0 0 1相似度应该是 100.00。如果你算出来不是100那说明计数器或格式有问题。第二组两个矩阵完全不同。2 2 1 0 0 1 0 1 1 0相似度应该是 0.00。同样任何非零输出都说明比较逻辑有误。第三组大小为 1 行 n 列例如1 5 1 0 1 0 1 1 1 0 0 1逐位比较相同位置为 第0位(11)、第3位(00)、第4位(11)所以 cnt3总像素5相似度 60.00。这种单行数据最容易暴露数组下标或循环边界问题。用这三组数据测过基本能确定代码逻辑正确。5. 常见错误与调试心得5.1 数组越界n, m≤100时很多人喜欢定义int a[100][100]。问题是如果 n 和 m 恰好等于100下标访问范围是 0 到 99那么a[99][99]是合法的但a[100][100]就越界了。有的直接定义a[105][105]或者a[101][101]多留几个单位的空间就是为了一劳永逸避免这个问题。在NOI系列题目中给数组“多开5个”是标准习惯例如数据范围是100就开105数据范围是1000就开1005。这不是洁癖是为了对付边界情况。5.2 计数器类型用错有人把 cnt 定义成 double这是没必要的而且会导致判断if (a[i][j] b[i][j])时 cnt 的行为没有任何不同但后面计算就麻烦了。最稳妥的做法是 cnt 用 int计算时乘以 100.0 来隐式转成 double。如果你把 cnt 定义成 double也不是不行但在某些复杂场景下浮点数循环累加会产生精度漂移。既然这里可以用整数何必自找麻烦5.3 忘记处理 n 或 m 为 0 的边界题目一般会保证 n, m 1但作为程序员的严谨性来说如果遇到 n0 或 m0你的代码会不会崩不会崩但可能会除零错误。竞赛题目里通常不会出现这种情况不过一旦出现程序就会Runtime Error。我在平时练习时会顺手加一行判断if (n 0 || m 0) { printf(0.00\n); return 0; }各自取舍不加也行因为题面不会出现这种数据。但对边界情况的敏感度是区分“能用”和“稳健”的分水岭。5.4 调试技巧打印中间结果很多新手一提交Wrong Answer就直接懵了不知道是读入错了、比较错了还是输出格式错了。我建议在调试时先打印中间结果for (int i 0; i n; i) { for (int j 0; j m; j) printf(%d , a[i][j]); printf(\n); } printf(cnt %d\n, cnt);确认 cnt 值和两个矩阵读入正确后再去检查输出格式。如果 cnt 正确但答案不对那就是输出格式或类型转换的问题如果 cnt 都不对那就检查读入逻辑。这个“先定位再修复”的思路比盲目改代码高效得多。提交前记得把所有调试用的 printf 去掉或者注释掉。我见过太多人AC的代码里留着调试语句好在不影响答案但如果是输出调试信息到标准输出一定会WA。所以调试要改代码测试完要还原。6. 题目之外的延伸思考这道题虽然简单但“图像相似度”这个概念在整个计算机领域无处不在。理解这个基础版本后可以帮你想通很多后续问题的本质。6.1 从像素相等到数值接近在实际图像处理中两张图片几乎不可能每个像素值完全相同——因为噪声、光照、压缩损失都会改变像素值。所以工业界常用的相似度计算通常不是“完全相等”而是“差值绝对值小于某个阈值”就算相似。用代码表示就是if (abs(a[i][j] - b[i][j]) 10) cnt;这里的 10 就是容差threshold。你在后续题目中可能会碰到类似“如果两个像素点的差值不超过20则认为这两个像素点相同”的描述。原理和本题一模一样只是把换成了abs(u-v)t。6.2 不只是百分比从相似度到匹配严格来说这道题算的是“一致率”或“重合率”不是广泛意义上的“相似度指标”。在计算机视觉中还有一种更常用的指标叫SSIM结构相似性指数它在亮度、对比度、结构三个维度上比较图像结果比像素重合率更符合人眼感知。SSIM的计算涉及均值、方差、协方差需要遍历图像两次甚至三次复杂度约 O(3nm)。虽然比本题复杂得多但核心思想都是从逐像素统计出发。如果以后你做到“矩阵匹配”“子图像查找”例如在大的图像矩阵里找一个小的模板矩阵那就要用到滑窗遍历相似度/距离计算核心思路会从“遍历全图”变成“遍历所有可能的左上角位置”然后同样用双重循环比较子区域。这些题目的一维基础就是这道1123题给你打的底子。6.3 二维前缀和能优化什么如果你在思考“能不能更快”可以提一个进阶概念假设我们要统计一个矩阵里“有多少个 1”比起每次用双重循环数可以先做二维前缀和然后 O(1) 查询任意矩形区域内 1 的个数。但本题要比较两张图的差异前缀和只能加速“统计区域内的值”不能加速“逐点比较”因为比较必须知道每个位置的具体值。所以这道题用前缀和没有意义。但有一些变种题比如“统计某个区域内有几个像素不同”可以通过分别对每个矩阵做前缀和再比较区域和的差值来快速判断是否可能不同。这时你就需要掌握前缀和这个工具了。这些都是后续的话题这里先留个钩子等你刷到二维前缀和的题目再回头理解会自然很多。6.4 一个刷题心态建议我发现有些读者看到这种“简单题”就直接跳过觉得“我一定会”。但在竞赛中真正决定成绩的往往不是难题而是简单题的手速和准确率。图像相似度这道题最典型的陷阱就是浮点输出格式。我见过太多水平不错的学生在这道题上因为输出88.888889而不是88.89被卡了好几次。这种问题在真正的竞赛中不会给你重测的机会一次提交就决定了分数。所以哪怕题目再简单也要亲手写一遍、提交一遍、跑满边界数据一遍。这种“不因简单而轻视”的态度是练习信息学奥赛最宝贵的财富之一。就我这些年的刷题和教学经验来看能把每道入门题都做到满分AC、代码清晰简洁、边界测试齐全的人后面学数据结构和算法时的爆发力往往远超那些“眼高手低”的学生。
