每次打 AtCoder 的 ABC总有一些题让我觉得“这题我能写一篇笔记”B - Bingo 就是其中之一。题目本身不难属于典型的新手友好型模拟题但里面涉及到的二维数组操作、标记状态、八方向判定这些套路在后续很多题目里都会反复出现。我这次把这道题从题意到代码完整地拆一遍把自己当时踩过的坑和后来复盘时想到的优化细节都写出来给刚开始刷 AtCoder 的朋友做个参考。1. 题目背景与题意拆解1.1 比赛场景与难度定位ABC157 是 AtCoder Beginner Contest 的第 157 场B 题固定在 200 分档位考察的是最基础的数组模拟能力。这个分数段的题目一般不会涉及复杂算法更多是看你能不能把一个直观的过程用代码准确翻译出来。Bingo 这题就是这么个定位规则人人都会关键是编码时别漏判、别越界、别搞反行列。对于刚开始打 AtCoder 的人来说B 题是必须稳定拿下的分数。如果你连 B 题都还在挣扎那问题大概率不在算法思维而是对数组遍历、条件判断这些基本功还不够熟练。所以这篇笔记我写得比较啰嗦把每个分支都拆开讲就是为了让基础薄弱的朋友也能一步不差地跟下来。1.2 题面逐句解读这道题的输入分三部分。先给一个 3 行 3 列的矩阵每个格子是一个整数。然后给一个整数 N代表接下来要读出 N 个数字。最后是 N 个整数表示这次抽选会念出来的号码。游戏的规则跟现实里玩宾果完全一致每念到一个数字如果这个数字出现在了 3x3 的卡片上就把对应格子标记为“已被叫到”。你不需要考虑卡片上没有的数字也不需要考虑数字重复被念到的情况说白了就是两张表对一对命中就划掉。全部念完之后判断卡片上是否有某一行、某一列或者某一条对角线上的三个格子都被标记了如果存在输出Yes否则输出No。这里有个小细节值得注意对角线不只是从左上到右下那一条另一条从右上到左下的对角线也要判断。很多人第一次写这题只判了主对角线结果提交之后挂掉就是这个原因。1.3 为什么这道题值得写一篇笔记我知道肯定有人会觉得B 题有什么好写的不就是暴力模拟吗但恰恰是这种“简单题”最能暴露编码习惯的问题。比如变量命名、循环边界的写法、判断条件的组织方式这些在简单题里打个好基础后面做复杂题的时候会省很多事。另外一个原因是B 题虽然简单但它浓缩了一个很重要的套路把现实规则翻译成状态存储。你需要在内存里维护一个“哪些格子被标记过”的状态然后基于这个状态做判定。这个思维模型在后面很多搜索题、状压题里都能看到影子只是形式更复杂罢了。所以把这题的思路吃透练的不只是这道题本身。2. 核心思路从“人眼判断”到“程序模拟”2.1 为什么选择朴素模拟而不是直接判定拿到这题第一反应就是照着题目描述一步一步来读入卡片读入号码标记命中格子最后检查胜出条件。这是一种最“笨”但最不容易出错的做法我强烈建议初学者优先选这种方案。可能有人会想能不能不建标记数组直接对每个号码判断它是否在某一行/列/对角线上然后累加命中次数理论上可以但实现起来反而绕。因为你需要维护 8 条线的命中计数还要处理同一个格子同时属于行和列的情况容易重复计算。更麻烦的是如果号码重复计数逻辑还得去重。相比之下建一个 3x3 的布尔数组把状态先写清楚再做 8 条线的检查逻辑清晰得多。这个选择背后是一个很实用的原则在数据规模足够小的前提下3x3 的矩阵、最多 100 个号码模拟是最可靠、最好调试的方案。先保证正确再考虑花活。竞赛里很多题不是你不会而是想太多把简单问题复杂化了。2.2 标记状态如何设计标记数组用 bool 类型就够了true表示该格子已被叫到false表示未被叫到。数组的大小跟卡片保持一致也就是3x3。下标设计成marked[i][j]对应原卡片第i行第j列的格子。标记的过程就是遍历所有叫到的号码对每个号码都去卡片里找一遍。由于卡片只有 9 个格子这里完全不需要做任何优化两层循环蛮力搜索即可。每找到一个匹配的格子就把marked[i][j]设为true。需要注意的是同一个号码可能同时多次出现在卡片里这不会造成问题因为标记操作是幂等的反正都是设成true。可能有人会问如果 N 个号码里有重复的会不会影响不会。因为标记状态是布尔量重复叫同一个号码第二次相当于白叫。这也是为什么模拟方案简单的原因之一你不需要专门处理重复。2.3 胜出条件的判定方式标记做完之后重点就到了判定环节。需要检查的线一共有 8 条第 0 行、第 1 行、第 2 行共 3 条行线第 0 列、第 1 列、第 2 列共 3 条列线主对角线左上角到右下角副对角线右上角到左下角每条线的判定就是检查该线上 3 个格子的marked值是否都为true。只要有一条线满足条件就可以提前结束直接输出Yes。如果所有线都查完仍然没有满足的则输出No。实现的时候建议把行检查和列检查分开写两个循环各做各的不要硬合在一起。虽然合并写法代码更短但可读性会下降。竞赛代码首先要保证你自己能一眼看明白其次才是精简。对角线判定因为只有两条直接写四个格子的条件表达式就可以了没必要循环。3. 完整代码实现与细节说明3.1 C 参考实现我平时用 C 刷 AtCoder 比较多先贴一版我当时的写法。代码不算最短但每一步都对应到题面上的一个动作看代码就能还原整个流程。#include bits/stdc.h using namespace std; int main() { // 读入 3x3 卡片 vectorvectorint a(3, vectorint(3)); for (int i 0; i 3; i) { for (int j 0; j 3; j) { cin a[i][j]; } } // 读入号码数量 N int n; cin n; // 逐个读入号码并即时更新标记 vectorvectorbool marked(3, vectorbool(3, false)); for (int k 0; k n; k) { int x; cin x; for (int i 0; i 3; i) { for (int j 0; j 3; j) { if (a[i][j] x) { marked[i][j] true; } } } } // 检查胜出条件 bool ok false; // 行检查 for (int i 0; i 3; i) { if (marked[i][0] marked[i][1] marked[i][2]) { ok true; } } // 列检查 for (int j 0; j 3; j) { if (marked[0][j] marked[1][j] marked[2][j]) { ok true; } } // 主对角线 if (marked[0][0] marked[1][1] marked[2][2]) { ok true; } // 副对角线 if (marked[0][2] marked[1][1] marked[2][0]) { ok true; } cout (ok ? Yes : No) \n; return 0; }这个版本我在本地跑了几个用例都能正确输出。有两点我觉得值得说明一是vectorvectorbool这种二维数组的初始化方式二是边读号码边更新标记的做法省去了单独存号码数组的空间。后者在数据规模小的时候无所谓但这种写法更紧凑。3.2 Python 参考实现Python 版的思路跟 C 完全一致只是语法上有差异。主要区别是二维 list 的初始化和all()函数的用法。# 读入卡片 a [list(map(int, input().split())) for _ in range(3)] # 读入号码并标记 n int(input()) marked [[False] * 3 for _ in range(3)] for _ in range(n): x int(input()) for i in range(3): for j in range(3): if a[i][j] x: marked[i][j] True # 判定 ok False for i in range(3): if all(marked[i][j] for j in range(3)): ok True for j in range(3): if all(marked[i][j] for i in range(3)): ok True if marked[0][0] and marked[1][1] and marked[2][2]: ok True if marked[0][2] and marked[1][1] and marked[2][0]: ok True print(Yes if ok else No)Python 的all()函数在这里特别好用它接收一个可迭代对象如果所有元素都为真就返回True。用生成器表达式把一行或一列的值传进去比手写三个and要清爽。不过要注意marked[i][j] for j in range(3)这种写法在列表推导式里会生成一个布尔序列性能上对 3 个元素来说完全不用操心。另外提醒一个 Python 新手容易犯的错二维 list 初始化不要写成[[False] * 3] * 3这样每一行其实是同一个对象的引用改一格会连带改三格。正确写法是[[False] * 3 for _ in range(3)]保证每一行都是独立的新列表。3.3 关键分支的逐段解释很多人在写判定的时候喜欢把所有条件堆在一个巨大的if里比如if (r0 r1 r2) ok true;这种。这没问题但当你检查漏了某一条线时这种写法不容易发现问题。我的习惯是行、列、对角线和主对角线分开写每条检查都是一段独立的代码块中间用空行隔开。这样做的好处是当输出跟预期不符时可以快速定位是哪个方向的判定出了问题。比如样例挂了但挂得很奇怪那我就会在行检查、列检查、对角线检查之间分别加输出语句看看到底哪一条线的状态不对。分块写还有一个好处方便扩展。假设题目以后改成 5x5 的卡片、或者要你输出是哪条线赢了你只需要在每个分支里补充相应逻辑就行不用改动其他部分。4. 踩坑记录与常见错误排查4.1 最常见的 WA 原因漏判副对角线我在文章开头就提到了副对角线是最容易漏掉的一条线。原因也很简单我们从小到大接触的矩阵题提到对角线脑子里默认就是左上到右下那一条很容易忽略右上到左下这条。AtCoder 的出题人显然很清楚这个心理所以测试数据里大概率会覆盖副对角线获胜的情况。我当时第一次提交就挂了本地自测时用的用例也都只覆盖了行和列。后来我拿了一组副对角线全标记的数据一跑果然输出No问题一下子就定位了。所以大家在自测的时候建议刻意构造 8 个方向的测试用例不要只测一行或者一列对角线尤其要测。4.2 别把行和列的循环变量搞混行检查时外层循环变量是i内层取的是marked[i][0]、marked[i][1]、marked[i][2]这表示固定行、遍历列。列检查时外层循环变量是j取的是marked[0][j]、marked[1][j]、marked[2][j]这表示固定列、遍历行。这两个循环的写法特别容易在复制粘贴的时候搞混。比如把行检查复制一份改列检查结果忘了把里层的下标位置调换最后查的就是同一组数据自然怎么测都错。这种错误找起来很费眼神建议写完代码后先静态检查一遍再上测试数据。4.3 号码读取格式的坑AtCoder 的输入格式里N 个号码可能是每行一个也可能是一行多个全看题目怎么定义。ABC157 这题里 N 个号码是每个号独占一行所以用cin x连续读就行。但有些题的输入是一行内空格分隔这时候如果你用了类似getline的方式去处理很容易因为换行符没吃掉而读串。我的建议是除了第一次读 N 之前可能需要处理换行以外后续读取统一用cin x或input().split()这种方式它会自动跳过空白字符包括空格和换行不会受到换行符影响。C 的cin默认就跳过空白Python 的split()也天然处理好了没必要自己手动清空缓冲区。4.4 边界条件的自测清单掌握一道题最好的方式就是在提交前自己构造几组边界测试。针对 Bingo 这题我一般会跑这么几组所有格子都没被标记期望输出No只有一行被标记期望输出Yes只有一列被标记期望输出Yes只有主对角线被标记期望输出Yes只有副对角线被标记期望输出Yes恰好全部被标记期望当然也是YesN 为最小值 0 时如果题目允许期望输出No卡片上的数字与叫到的号码没有任何交集期望输出No把这 8 个用例全部跑通这道题基本就十拿九稳了。不要觉得构造测试用例浪费时间实际调试中它比反复猜测哪里出错要高效得多。我在做题时有个习惯代码写完先不急着提交先在本地把这组边界用例过一遍确认没问题再上 OJ。虽然 AtCoder 的反馈很快但反复提交错误答案会扣罚时本地多做一点功课永远是划算的。4.5 数值范围与数据类型的注意事项ABC157 B 题的格子数字范围是 1 到 100N 的范围是 1 到 100。这个范围用int完全足够不需要任何特殊处理。但如果把这道题的约束放大比如数字范围到 10 的 9 次方或者 N 大到 10 的 5 次方那就需要考虑用set或者unordered_map来优化查找了。对于当前题目的规模最简单遍历策略已经可以轻松跑在 O(N x 9) 的复杂度下也就是最多 900 次比较耗时可忽略不计。这类“先看范围再选算法”的意识很重要很多选手在简单题上反而过度设计写了一个 100 行的复杂解法只为了处理根本不存在的性能瓶颈。5. 复杂度分析与可扩展的思路5.1 时空复杂度到底是多少这个解法的时间复杂度主要由两部分组成标记阶段和判定阶段。标记阶段对 N 个号码逐个扫描 9 个格子比较次数为 N x 9判定阶段固定检查 8 条线每次检查 3 个格子所以是常数时间。整体时间复杂度为 O(N)因为 N 最大是 100实际开销非常小。空间复杂度方面除了输入的 3x3 卡片外只额外开了一个 3x3 的布尔数组所以是 O(9)也就是常数空间。这题无论时间复杂度还是空间复杂度都非常优秀放到任何评价体系下都是满分答案。这也是为什么我建议初学者从模拟入手的原因在数据范围允许的情况下模拟往往就是最优解不需要强行套用更复杂的算法。5.2 如果 N 大到 100000 怎么优化假如我们把题目改成号码数量 N 可能达到 10 的 5 次方卡片仍然只有 3x3。这时候原来的遍历方案仍然能过因为 100000 x 9 900000 次比较对现代 CPU 来说依然是毫秒级。但如果卡片也跟着变大比如变成一个 1000x1000 的矩阵那每次扫描全部格子就会变成 10 的 6 次方量级再乘上 N 就不可接受了。这时候就需要换思路先把卡片上的每个数字与其坐标存进哈希表然后对每个号码只需在哈希表里查一次 O(1) 的命中再更新对应坐标的标记状态。这种方式的时间复杂度就从 O(N x M) 降到了 O(N M)。竞赛里有一个很通用的手段叫“反向索引”说的就是这种把“找某个值在不在数组里”的代价提前摊到建索引阶段的做法。虽然这道题用不上但如果你能从这道 3x3 的 Bingo 想到这一层说明你已经具备了优化意识这是很宝贵的。5.3 类似的题型如何举一反三Bingo 这类“标记状态 条件判定”的题目在 AtCoder 里非常多。ABC 的 B 题和 C 题里经常出现类似模式比如给你一个矩阵依次执行若干操作最后询问某个属性是否成立。解题流程都是三步读入初始数据模拟操作过程按条件输出结果。具体来说ABC096 B 题是判断三个数字能否通过翻倍达到目标ABC113 B 题是找最接近目标温度的地点ABC122 B 题是统计最长连续匹配长度。这些题考察的都是基础的状态维护和条件判断能力跟 Bingo 的底层思维是一致的。你可以把这些题拿来当配套练习巩固同一个套路。另外Bingo 本身还有很多变体。比如变成 4x4 卡片或者要求输出是哪个方向的线获胜或者要求统计获胜时的最大连击数。遇到这种变体题底层的标记数组思路完全不变变的只是判定逻辑里多了几个方向参数而已。如果你能把 Bingo 的代码写得足够模块化这些变体题在你眼里基本就是改几个常量的功夫。竞赛里有一句经验说得很对简单题的目的是让你在高压环境下形成条件反射。当你的手指不需要思考就能写出正确的 Bingo 判定时你才有精力在 C 题和 D 题上集中注意力思考算法。这道题值得反复写几遍直到你能闭着眼睛快速完成二维标记和八向判定为止。最后分享一个我个人的小技巧每次复盘简单题的时候我会故意把自己的解法删掉然后用另一种方式重新实现一遍。比如这题我第一次是用二维数组写的复盘时我尝试用一维数组加坐标映射来实现虽然代码变长了但对“行、列、对角线”这三种关系在内存中如何表达的理解更深入了。当你发现能用多种方式表达同一个状态时说明这道题才真正变成你自己的东西了。