有经验的刷题人通常会有一种感觉越是放在 ABC 前两题的“简单题”越容易在细节上翻车。2021年10月29日我重刷 AtCoder Beginner Contest 157 的 B 题 Bingo 时又一次验证了这句话。Bingo 这道题从模型上看就是一个三行三列的标记游戏难度不高但它同时涉及二维数组的读入、条件标记、八条线的枚举以及 AtCoder 严格的大小写输出要求。对刚接触竞赛编程的新手来说这是一道非常合适的“综合小题”对老手来说复盘这道题也能提醒自己别把简单题想简单。我之所以单独把 ABC157——B - Bingo 拎出来写一篇不是因为它难而是因为它“麻雀虽小五脏俱全”。如果你能完全靠自己的思路一次性通过这道题说明你对数组下标、布尔状态和分支判断已经建立了不错的直觉如果你在某个隐蔽角落卡住了这篇文章正好可以把那些坑一个个摊开。1. 为什么一道“看完就会写”的Bingo题还值得复盘1.1 先把题目场景还原一遍Bingo 游戏大家都听过。你手里有一张卡片主持人在台上喊数字如果你的卡片上有这个数字就给这个格子做个记号。当卡片上出现了一整行、一整列或者一条对角线都被标记时你就可以喊一句“Bingo”宣告胜利。AtCoder ABC157 的 B 题做的事情就是把这个过程抽象成一道编程题。输入会给你一个 3x3 的网格里面每个格子放着一个整数。接下来输入一个整数 N然后输入 N 个整数表示主持人喊出的数字。每当喊出的数字和网格中某个位置上的数字相等时那个位置就算是“被打上标记”。最终你需要判断这张 3x3 的卡片上是否已经出现了一整行、一整列或者一条对角线上的三个格子全部被标记。如果存在这样的直线输出Yes否则输出No。题目最友好的地方在于3x3 是固定的。这意味着不存在读入边长的问题也不需要做动态二维数组的分配。也就是说这道题没有复杂的算法所有的难点都集中在“你能否完整地处理标记和判断”。N 的最大值只有 10网格也只有 9 个格子所以即便是最粗糙的暴力写法也只需要几十次比较。换句话说这道题完全不需要优化也不需要数据结构考察的就只是你打代码的基本功。1.2 拿到题目后我习惯先拆成四个动作我刷题有一个习惯不管题目多简单先不急着写代码而是在草稿纸上把“要做什么”拆成几个动作。这样能避免写着写着漏掉一步。这道题可以拆成这样读入 3x3 网格存到二维数组里。读入 N 和 N 个数字每读入一个数字就在网格里找有没有相等的格子。如果找到相等的格子就把那个格子对应的“标记状态”置为 true。最后检查 3 行、3 列、2 条对角线看是否存在一条线全部被标记。前两步是模拟第三步是判断思路非常直白。这里有一个小建议在草稿纸上把“行、列、对角线”这八条线都写出来再去写代码。不要只在脑子里想因为二维数组的下标非常容易看走眼。后面我会把八条线具体坐标列出来。2. “标记格子”这一步藏着所有后续判断的基础2.1 最朴素的标记方式恰恰是最稳的标记格子听起来很简单但新手经常犯一个错误试图用“原始数字网格”本身来记录标记状态。比如有人会想把被喊到的数字直接改成 0表示这个格子已经被标记。这种方法不是不行但后患无穷。因为题目只要求判断是否存在完整的线并不需要记录格子原来的值可一旦你直接把数组改成 0万一后面有别的数字要和原数组比较就再也比不出来了。更清晰的思路是单独开一个二维布尔数组marked[3][3]专门记录每个格子是否被标记。标记过程也很直白每读入一个数字 b就两层循环遍历整个 3x3 网格如果a[i][j] b就把marked[i][j]置为 true。有人可能会问这样不会太暴力吗每次遍历 9 个格子N 最大 10一共也就 90 次比较。这个开销小到完全不需要考虑。为什么我不推荐一上来就建哈希表因为题目中的数字范围不大而且输入规模非常小哈希表带来的常数开销反而比朴素遍历更大。更关键的是如果网格里出现了两个相同的数字如果你用简单的“数字到坐标”映射来存后一个位置会把前一个位置覆盖。到时候喊出这个数字你只能标记到最后一个匹配位置前面的那个格子就会漏掉。所以在这个数据规模下最朴素的双层循环比较才是真正的“最优解”。它不是性能最优而是正确性最稳。2.2 标记阶段的代码与初始化细节下面先用 Python 写一个标记阶段的片段a [list(map(int, input().split())) for _ in range(3)] n int(input()) marked [[False] * 3 for _ in range(3)] for _ in range(n): b int(input()) for i in range(3): for j in range(3): if a[i][j] b: marked[i][j] True如果换成 C唯一需要特别注意的是数组初始化int a[3][3]; bool marked[3][3] {};bool marked[3][3] {};会把所有元素初始化为 false。如果你只写bool marked[3][3];那么数组里可能是一些随机值后面判断时会出现“明明没有标记却显示为 true”的诡异情况。这个坑是用 C 刷题时特别值得警惕的。标记阶段结束后marked数组就代表了一张“被打过孔”的卡片。接下来的问题就变成了如何判断卡片上有没有一条完整的线。3. 八条线的判断从“手写枚举”到“循环统一”3.1 把八条线用坐标表格列出来3x3 的卡片上一共有八条可能的获胜线三条行线、三条列线、两条对角线。把这八条线的坐标列出来代码就会写得非常有底气。线型坐标第 0 行(0,0), (0,1), (0,2)第 1 行(1,0), (1,1), (1,2)第 2 行(2,0), (2,1), (2,2)第 0 列(0,0), (1,0), (2,0)第 1 列(0,1), (1,1), (2,1)第 2 列(0,2), (1,2), (2,2)主对角线(0,0), (1,1), (2,2)副对角线(0,2), (1,1), (2,0)这张表就是整道题的核心。判断是否存在一条完整线本质就是把上面八条线“翻译”成代码里的条件表达式。最直接的方法是手写八个 if。这样写比较啰嗦但不容易出错。比如判断主对角线只需要检查marked[0][0] marked[1][1] marked[2][2]判断副对角线则是marked[0][2] marked[1][1] marked[2][0]这种写法的好处是清晰每一行对应现实中的一条线想漏都难。坏处是代码有些重复尤其是判断三条行线和三条列线时可以用循环压缩。3.2 两种判断写法的对比我推荐的写法是“循环判断行和列单独判断对角线”。行线和列线具有很强的规律性。三行分别对应i 0, 1, 2三列分别对应j 0, 1, 2。所以可以用一个循环同时检查行和列for (int i 0; i 3; i) { if (marked[i][0] marked[i][1] marked[i][2]) { cout Yes\n; return 0; } if (marked[0][i] marked[1][i] marked[2][i]) { cout Yes\n; return 0; } }这段代码里第一个 if 检查的是第 i 行的三个格子第二个 if 检查的是第 i 列的三个格子。两条对角线不具备这种循环结构单独写两个 if 就好。也有一种更统一的做法把八条线的坐标预先存到一个数组里再统一遍历。比如int lines[8][3][2] { {{0,0},{0,1},{0,2}}, {{1,0},{1,1},{1,2}}, {{2,0},{2,1},{2,2}}, {{0,0},{1,0},{2,0}}, {{0,1},{1,1},{2,1}}, {{0,2},{1,2},{2,2}}, {{0,0},{1,1},{2,2}}, {{0,2},{1,1},{2,0}} };然后用一个双重循环去遍历每条线、每个点。这样做的好处是代码更“通用”如果以后要扩展到 N x N 网格只需要修改 lines 的生成方式即可。但话说回来本题只有八条线数据规模又极小选择哪种写法的唯一标准是“你自己看得懂”。不要在比赛里追求代码的优雅而放弃熟练度。3.3 完整参考代码下面给出一份完整的 C 参考代码#include bits/stdc.h using namespace std; int main() { int a[3][3]; for (int i 0; i 3; i) { for (int j 0; j 3; j) { cin a[i][j]; } } int n; cin n; bool marked[3][3] {}; for (int k 0; k n; k) { int b; cin b; for (int i 0; i 3; i) { for (int j 0; j 3; j) { if (a[i][j] b) { marked[i][j] true; } } } } for (int i 0; i 3; i) { if (marked[i][0] marked[i][1] marked[i][2]) { cout Yes\n; return 0; } if (marked[0][i] marked[1][i] marked[2][i]) { cout Yes\n; return 0; } } if (marked[0][0] marked[1][1] marked[2][2]) { cout Yes\n; return 0; } if (marked[0][2] marked[1][1] marked[2][0]) { cout Yes\n; return 0; } cout No\n; return 0; }Python 版本可以这样写a [list(map(int, input().split())) for _ in range(3)] n int(input()) marked [[False] * 3 for _ in range(3)] for _ in range(n): b int(input()) for i in range(3): for j in range(3): if a[i][j] b: marked[i][j] True ok False for i in range(3): if all(marked[i][j] for j in range(3)): ok True if all(marked[j][i] for j in range(3)): ok True if all(marked[i][i] for i in range(3)): ok True if all(marked[i][2 - i] for i in range(3)): ok True print(Yes if ok else No)这段 Python 代码里用到了all()它接收一个可迭代对象只有当所有元素都为 true 时才返回 true。用在这里非常合适。复杂度方面标记阶段是 O(9N)判断阶段是 O(8)空间是 O(9) 的布尔矩阵。因为 N 最大只有 10实际执行的比较次数不超过 100 次运行时间几乎为 0。4. 我在提交时踩过的坑以及如何一次通过4.1 输出不是“YES”而是“Yes”这是 AtCoder 新手最容易踩的坑之一。AtCoder 的输出判定是严格区分大小写的题目要求输出Yes就必须是Yes。如果你习惯性地写成了全大写的YES或者写成了yes哪怕你的逻辑完全正确最后也一定是 WA。我见过不少参赛者在简单题上翻车原因不是算法不会而是输出格式差了一个字母。最稳妥的做法是从题目描述里把输出格式抄下来或者从样例输出里复制。不要凭感觉写。4.2 布尔数组忘了初始化开场就翻车如果你用 C 写这道题声明bool marked[3][3];之后不做任何初始化那么这个数组里存的值是未定义的。局部变量的初始值可能是 0也可能是任意非 0 值。这意味着某个格子明明没有被标记但marked[i][j]可能为 true最后可能错误地输出Yes也可能恰好输出No但已经不符合逻辑。解决办法就是在声明时写 {}bool marked[3][3] {};这个语法会把整个数组的所有元素都初始化为 false。你也可以用memset(marked, 0, sizeof(marked));但更推荐前者简洁且不容易写错。4.3 用哈希表记录数字位置时可能被重复值坑到这道题的数据范围很小所以我前面一直推荐直接遍历比较。但我在交流群里看到过不少同学会选择“建立数字到坐标的映射”也就是mapint, pairint,int pos; for (int i 0; i 3; i) { for (int j 0; j 3; j) { pos[a[i][j]] {i, j}; } }这段代码初看没问题但如果 3x3 网格里出现了两个相同的数字pos只会保留最后一次出现的坐标。等主持人喊出这个数字时另一个相同数字所在的格子就不会被标记。原题并没有要求我们利用数字的唯一性来做任何优化所以直接遍历是最安全的。如果你喜欢用哈希表至少也要用mapint, vectorpairint,int把同一个数字出现的所有坐标都存下来。可这样反而把事情变复杂了完全没有必要。4.4 提前输出后忘了 return代码会“说话”在 C 代码中如果你在判断出行线存在后直接cout Yes\n;却没有写return 0;程序不会停下来而是会继续往下执行。如果后面的某个条件也成立可能会再输出一次Yes如果后面的条件不成立最后可能输出一个No。这样输出结果会变成两行第一行Yes第二行No。AtCoder 的判定器拿到多行输出后大概率判你 WA。所以一旦找到一条获胜线务必在输出后立即终止程序。上面给出的 C 代码中每个cout Yes\n;后面都跟了return 0;就是为了避免这个问题。5. 从3x3的Bingo出发还能延展成哪些题型5.1 扩大到 N x N 网格的判定既然 3x3 的 Bingo 会判断八条线那么如果题目变成 N x N 网格判断方式其实也没有本质变化。行和列的判断可以这样写for (int i 0; i n; i) { bool row_ok true; bool col_ok true; for (int j 0; j n; j) { if (!marked[i][j]) row_ok false; if (!marked[j][i]) col_ok false; } if (row_ok || col_ok) return true; }对角线判断则要检查两条bool diag1 true, diag2 true; for (int i 0; i n; i) { if (!marked[i][i]) diag1 false; if (!marked[i][n - 1 - i]) diag2 false; } if (diag1 || diag2) return true;这种扩展在题目中很常见。如果你能把 3x3 版本吃透N x N 版本只是多加一个循环而已。5.2 用位运算状态压缩写出更紧凑的判断再往后走一步如果网格始终是 3x3我们可以用 9 个二进制位表示标记状态。每一个格子对应一位该位为 1 表示被标记为 0 表示未被标记。假设格子的编号从左到右、从上到下依次是 0 到 8那么第 i 行第 j 列的格子对应的二进制位就是1 (i * 3 j)每次标记格子时做一次按位或运算state | 1 (i * 3 j);然后预先把八条线的掩码存下来int win[8] { 0b111000000, // 第 0 行 0b000111000, // 第 1 行 0b000000111, // 第 2 行 0b100100100, // 第 0 列 0b010010010, // 第 1 列 0b001001001, // 第 2 列 0b100010001, // 主对角线 0b001010100 // 副对角线 };判断是否存在 Bingo 的思路是for (int i 0; i 8; i) { if ((state win[i]) win[i]) { cout Yes\n; return 0; } }(state win[i]) win[i]的含义是win[i] 中为 1 的那些位在 state 中必须全部为 1。这和逐个判断marked数组是等价的但代码更紧凑。这种位运算技巧在很多状态压缩题目里都会用到。它不需要二维数组只用两个 int 型变量就能搞定是很好的思维训练。5.3 再进一步任意方向K连子判定如果题目从“整行整列”变成“只要在任意方向上连续 K 个就算赢”那就更像五子棋或者井字棋的变种。这种情况下固定枚举所有行、列、对角线就不够用了。常见做法是枚举每个格子作为起点然后向上下左右、四个斜方向一共八个方向扩展统计连续被标记的格子数量。方向可以预先用方向数组表示int dx[8] {1, -1, 0, 0, 1, 1, -1, -1}; int dy[8] {0, 0, 1, -1, 1, -1, 1, -1};然后从一个起点出发沿着某个方向走 K 步看看每一步是否都在棋盘内且被标记。这样做的好处是通用坏处是常数比较大但通常数据范围不大时也够用。如果你掌握了从“枚举固定线”到“方向扩展”的转变你对搜索题的理解也会上一个台阶。6. 重刷这道简单题我最大的三个收获第一简单题的答案往往不是“用高级技巧”而是“把基本动作做对”。ABC157 的 B - Bingo 不需要任何优化也不需要高级数据结构。只要二维数组读入正确、标记正确、八条线枚举完整就能通过。很多时候我们 WA不是因为不会难题而是因为在最简单的步骤上手滑了。第二草稿纸上的表格比脑子里的想象可靠。我在写这道题时把八条线的坐标列成表格然后照着表格写判断条件。这个过程看起来很笨但能有效减少下标错误。第三一次通过的秘诀就是提前想好所有边界。每次提交前我会在样例之外再构造几个用例。比如全部标记、没有任何标记、只差一个格子就 Bingo、副对角线恰好成立。这组用例跑下来基本可以覆盖所有分支。2021年10月29日那天我用最朴素的写法把这道题一次 AC。现在回头看它仍然是我愿意推荐给新手的题目之一不靠奇技淫巧纯粹考察你能不能把一句话描述的问题变成一段不会出错的代码。
简单题不简单：AtCoder ABC157 B题Bingo的二维数组模拟与复盘
有经验的刷题人通常会有一种感觉越是放在 ABC 前两题的“简单题”越容易在细节上翻车。2021年10月29日我重刷 AtCoder Beginner Contest 157 的 B 题 Bingo 时又一次验证了这句话。Bingo 这道题从模型上看就是一个三行三列的标记游戏难度不高但它同时涉及二维数组的读入、条件标记、八条线的枚举以及 AtCoder 严格的大小写输出要求。对刚接触竞赛编程的新手来说这是一道非常合适的“综合小题”对老手来说复盘这道题也能提醒自己别把简单题想简单。我之所以单独把 ABC157——B - Bingo 拎出来写一篇不是因为它难而是因为它“麻雀虽小五脏俱全”。如果你能完全靠自己的思路一次性通过这道题说明你对数组下标、布尔状态和分支判断已经建立了不错的直觉如果你在某个隐蔽角落卡住了这篇文章正好可以把那些坑一个个摊开。1. 为什么一道“看完就会写”的Bingo题还值得复盘1.1 先把题目场景还原一遍Bingo 游戏大家都听过。你手里有一张卡片主持人在台上喊数字如果你的卡片上有这个数字就给这个格子做个记号。当卡片上出现了一整行、一整列或者一条对角线都被标记时你就可以喊一句“Bingo”宣告胜利。AtCoder ABC157 的 B 题做的事情就是把这个过程抽象成一道编程题。输入会给你一个 3x3 的网格里面每个格子放着一个整数。接下来输入一个整数 N然后输入 N 个整数表示主持人喊出的数字。每当喊出的数字和网格中某个位置上的数字相等时那个位置就算是“被打上标记”。最终你需要判断这张 3x3 的卡片上是否已经出现了一整行、一整列或者一条对角线上的三个格子全部被标记。如果存在这样的直线输出Yes否则输出No。题目最友好的地方在于3x3 是固定的。这意味着不存在读入边长的问题也不需要做动态二维数组的分配。也就是说这道题没有复杂的算法所有的难点都集中在“你能否完整地处理标记和判断”。N 的最大值只有 10网格也只有 9 个格子所以即便是最粗糙的暴力写法也只需要几十次比较。换句话说这道题完全不需要优化也不需要数据结构考察的就只是你打代码的基本功。1.2 拿到题目后我习惯先拆成四个动作我刷题有一个习惯不管题目多简单先不急着写代码而是在草稿纸上把“要做什么”拆成几个动作。这样能避免写着写着漏掉一步。这道题可以拆成这样读入 3x3 网格存到二维数组里。读入 N 和 N 个数字每读入一个数字就在网格里找有没有相等的格子。如果找到相等的格子就把那个格子对应的“标记状态”置为 true。最后检查 3 行、3 列、2 条对角线看是否存在一条线全部被标记。前两步是模拟第三步是判断思路非常直白。这里有一个小建议在草稿纸上把“行、列、对角线”这八条线都写出来再去写代码。不要只在脑子里想因为二维数组的下标非常容易看走眼。后面我会把八条线具体坐标列出来。2. “标记格子”这一步藏着所有后续判断的基础2.1 最朴素的标记方式恰恰是最稳的标记格子听起来很简单但新手经常犯一个错误试图用“原始数字网格”本身来记录标记状态。比如有人会想把被喊到的数字直接改成 0表示这个格子已经被标记。这种方法不是不行但后患无穷。因为题目只要求判断是否存在完整的线并不需要记录格子原来的值可一旦你直接把数组改成 0万一后面有别的数字要和原数组比较就再也比不出来了。更清晰的思路是单独开一个二维布尔数组marked[3][3]专门记录每个格子是否被标记。标记过程也很直白每读入一个数字 b就两层循环遍历整个 3x3 网格如果a[i][j] b就把marked[i][j]置为 true。有人可能会问这样不会太暴力吗每次遍历 9 个格子N 最大 10一共也就 90 次比较。这个开销小到完全不需要考虑。为什么我不推荐一上来就建哈希表因为题目中的数字范围不大而且输入规模非常小哈希表带来的常数开销反而比朴素遍历更大。更关键的是如果网格里出现了两个相同的数字如果你用简单的“数字到坐标”映射来存后一个位置会把前一个位置覆盖。到时候喊出这个数字你只能标记到最后一个匹配位置前面的那个格子就会漏掉。所以在这个数据规模下最朴素的双层循环比较才是真正的“最优解”。它不是性能最优而是正确性最稳。2.2 标记阶段的代码与初始化细节下面先用 Python 写一个标记阶段的片段a [list(map(int, input().split())) for _ in range(3)] n int(input()) marked [[False] * 3 for _ in range(3)] for _ in range(n): b int(input()) for i in range(3): for j in range(3): if a[i][j] b: marked[i][j] True如果换成 C唯一需要特别注意的是数组初始化int a[3][3]; bool marked[3][3] {};bool marked[3][3] {};会把所有元素初始化为 false。如果你只写bool marked[3][3];那么数组里可能是一些随机值后面判断时会出现“明明没有标记却显示为 true”的诡异情况。这个坑是用 C 刷题时特别值得警惕的。标记阶段结束后marked数组就代表了一张“被打过孔”的卡片。接下来的问题就变成了如何判断卡片上有没有一条完整的线。3. 八条线的判断从“手写枚举”到“循环统一”3.1 把八条线用坐标表格列出来3x3 的卡片上一共有八条可能的获胜线三条行线、三条列线、两条对角线。把这八条线的坐标列出来代码就会写得非常有底气。线型坐标第 0 行(0,0), (0,1), (0,2)第 1 行(1,0), (1,1), (1,2)第 2 行(2,0), (2,1), (2,2)第 0 列(0,0), (1,0), (2,0)第 1 列(0,1), (1,1), (2,1)第 2 列(0,2), (1,2), (2,2)主对角线(0,0), (1,1), (2,2)副对角线(0,2), (1,1), (2,0)这张表就是整道题的核心。判断是否存在一条完整线本质就是把上面八条线“翻译”成代码里的条件表达式。最直接的方法是手写八个 if。这样写比较啰嗦但不容易出错。比如判断主对角线只需要检查marked[0][0] marked[1][1] marked[2][2]判断副对角线则是marked[0][2] marked[1][1] marked[2][0]这种写法的好处是清晰每一行对应现实中的一条线想漏都难。坏处是代码有些重复尤其是判断三条行线和三条列线时可以用循环压缩。3.2 两种判断写法的对比我推荐的写法是“循环判断行和列单独判断对角线”。行线和列线具有很强的规律性。三行分别对应i 0, 1, 2三列分别对应j 0, 1, 2。所以可以用一个循环同时检查行和列for (int i 0; i 3; i) { if (marked[i][0] marked[i][1] marked[i][2]) { cout Yes\n; return 0; } if (marked[0][i] marked[1][i] marked[2][i]) { cout Yes\n; return 0; } }这段代码里第一个 if 检查的是第 i 行的三个格子第二个 if 检查的是第 i 列的三个格子。两条对角线不具备这种循环结构单独写两个 if 就好。也有一种更统一的做法把八条线的坐标预先存到一个数组里再统一遍历。比如int lines[8][3][2] { {{0,0},{0,1},{0,2}}, {{1,0},{1,1},{1,2}}, {{2,0},{2,1},{2,2}}, {{0,0},{1,0},{2,0}}, {{0,1},{1,1},{2,1}}, {{0,2},{1,2},{2,2}}, {{0,0},{1,1},{2,2}}, {{0,2},{1,1},{2,0}} };然后用一个双重循环去遍历每条线、每个点。这样做的好处是代码更“通用”如果以后要扩展到 N x N 网格只需要修改 lines 的生成方式即可。但话说回来本题只有八条线数据规模又极小选择哪种写法的唯一标准是“你自己看得懂”。不要在比赛里追求代码的优雅而放弃熟练度。3.3 完整参考代码下面给出一份完整的 C 参考代码#include bits/stdc.h using namespace std; int main() { int a[3][3]; for (int i 0; i 3; i) { for (int j 0; j 3; j) { cin a[i][j]; } } int n; cin n; bool marked[3][3] {}; for (int k 0; k n; k) { int b; cin b; for (int i 0; i 3; i) { for (int j 0; j 3; j) { if (a[i][j] b) { marked[i][j] true; } } } } for (int i 0; i 3; i) { if (marked[i][0] marked[i][1] marked[i][2]) { cout Yes\n; return 0; } if (marked[0][i] marked[1][i] marked[2][i]) { cout Yes\n; return 0; } } if (marked[0][0] marked[1][1] marked[2][2]) { cout Yes\n; return 0; } if (marked[0][2] marked[1][1] marked[2][0]) { cout Yes\n; return 0; } cout No\n; return 0; }Python 版本可以这样写a [list(map(int, input().split())) for _ in range(3)] n int(input()) marked [[False] * 3 for _ in range(3)] for _ in range(n): b int(input()) for i in range(3): for j in range(3): if a[i][j] b: marked[i][j] True ok False for i in range(3): if all(marked[i][j] for j in range(3)): ok True if all(marked[j][i] for j in range(3)): ok True if all(marked[i][i] for i in range(3)): ok True if all(marked[i][2 - i] for i in range(3)): ok True print(Yes if ok else No)这段 Python 代码里用到了all()它接收一个可迭代对象只有当所有元素都为 true 时才返回 true。用在这里非常合适。复杂度方面标记阶段是 O(9N)判断阶段是 O(8)空间是 O(9) 的布尔矩阵。因为 N 最大只有 10实际执行的比较次数不超过 100 次运行时间几乎为 0。4. 我在提交时踩过的坑以及如何一次通过4.1 输出不是“YES”而是“Yes”这是 AtCoder 新手最容易踩的坑之一。AtCoder 的输出判定是严格区分大小写的题目要求输出Yes就必须是Yes。如果你习惯性地写成了全大写的YES或者写成了yes哪怕你的逻辑完全正确最后也一定是 WA。我见过不少参赛者在简单题上翻车原因不是算法不会而是输出格式差了一个字母。最稳妥的做法是从题目描述里把输出格式抄下来或者从样例输出里复制。不要凭感觉写。4.2 布尔数组忘了初始化开场就翻车如果你用 C 写这道题声明bool marked[3][3];之后不做任何初始化那么这个数组里存的值是未定义的。局部变量的初始值可能是 0也可能是任意非 0 值。这意味着某个格子明明没有被标记但marked[i][j]可能为 true最后可能错误地输出Yes也可能恰好输出No但已经不符合逻辑。解决办法就是在声明时写 {}bool marked[3][3] {};这个语法会把整个数组的所有元素都初始化为 false。你也可以用memset(marked, 0, sizeof(marked));但更推荐前者简洁且不容易写错。4.3 用哈希表记录数字位置时可能被重复值坑到这道题的数据范围很小所以我前面一直推荐直接遍历比较。但我在交流群里看到过不少同学会选择“建立数字到坐标的映射”也就是mapint, pairint,int pos; for (int i 0; i 3; i) { for (int j 0; j 3; j) { pos[a[i][j]] {i, j}; } }这段代码初看没问题但如果 3x3 网格里出现了两个相同的数字pos只会保留最后一次出现的坐标。等主持人喊出这个数字时另一个相同数字所在的格子就不会被标记。原题并没有要求我们利用数字的唯一性来做任何优化所以直接遍历是最安全的。如果你喜欢用哈希表至少也要用mapint, vectorpairint,int把同一个数字出现的所有坐标都存下来。可这样反而把事情变复杂了完全没有必要。4.4 提前输出后忘了 return代码会“说话”在 C 代码中如果你在判断出行线存在后直接cout Yes\n;却没有写return 0;程序不会停下来而是会继续往下执行。如果后面的某个条件也成立可能会再输出一次Yes如果后面的条件不成立最后可能输出一个No。这样输出结果会变成两行第一行Yes第二行No。AtCoder 的判定器拿到多行输出后大概率判你 WA。所以一旦找到一条获胜线务必在输出后立即终止程序。上面给出的 C 代码中每个cout Yes\n;后面都跟了return 0;就是为了避免这个问题。5. 从3x3的Bingo出发还能延展成哪些题型5.1 扩大到 N x N 网格的判定既然 3x3 的 Bingo 会判断八条线那么如果题目变成 N x N 网格判断方式其实也没有本质变化。行和列的判断可以这样写for (int i 0; i n; i) { bool row_ok true; bool col_ok true; for (int j 0; j n; j) { if (!marked[i][j]) row_ok false; if (!marked[j][i]) col_ok false; } if (row_ok || col_ok) return true; }对角线判断则要检查两条bool diag1 true, diag2 true; for (int i 0; i n; i) { if (!marked[i][i]) diag1 false; if (!marked[i][n - 1 - i]) diag2 false; } if (diag1 || diag2) return true;这种扩展在题目中很常见。如果你能把 3x3 版本吃透N x N 版本只是多加一个循环而已。5.2 用位运算状态压缩写出更紧凑的判断再往后走一步如果网格始终是 3x3我们可以用 9 个二进制位表示标记状态。每一个格子对应一位该位为 1 表示被标记为 0 表示未被标记。假设格子的编号从左到右、从上到下依次是 0 到 8那么第 i 行第 j 列的格子对应的二进制位就是1 (i * 3 j)每次标记格子时做一次按位或运算state | 1 (i * 3 j);然后预先把八条线的掩码存下来int win[8] { 0b111000000, // 第 0 行 0b000111000, // 第 1 行 0b000000111, // 第 2 行 0b100100100, // 第 0 列 0b010010010, // 第 1 列 0b001001001, // 第 2 列 0b100010001, // 主对角线 0b001010100 // 副对角线 };判断是否存在 Bingo 的思路是for (int i 0; i 8; i) { if ((state win[i]) win[i]) { cout Yes\n; return 0; } }(state win[i]) win[i]的含义是win[i] 中为 1 的那些位在 state 中必须全部为 1。这和逐个判断marked数组是等价的但代码更紧凑。这种位运算技巧在很多状态压缩题目里都会用到。它不需要二维数组只用两个 int 型变量就能搞定是很好的思维训练。5.3 再进一步任意方向K连子判定如果题目从“整行整列”变成“只要在任意方向上连续 K 个就算赢”那就更像五子棋或者井字棋的变种。这种情况下固定枚举所有行、列、对角线就不够用了。常见做法是枚举每个格子作为起点然后向上下左右、四个斜方向一共八个方向扩展统计连续被标记的格子数量。方向可以预先用方向数组表示int dx[8] {1, -1, 0, 0, 1, 1, -1, -1}; int dy[8] {0, 0, 1, -1, 1, -1, 1, -1};然后从一个起点出发沿着某个方向走 K 步看看每一步是否都在棋盘内且被标记。这样做的好处是通用坏处是常数比较大但通常数据范围不大时也够用。如果你掌握了从“枚举固定线”到“方向扩展”的转变你对搜索题的理解也会上一个台阶。6. 重刷这道简单题我最大的三个收获第一简单题的答案往往不是“用高级技巧”而是“把基本动作做对”。ABC157 的 B - Bingo 不需要任何优化也不需要高级数据结构。只要二维数组读入正确、标记正确、八条线枚举完整就能通过。很多时候我们 WA不是因为不会难题而是因为在最简单的步骤上手滑了。第二草稿纸上的表格比脑子里的想象可靠。我在写这道题时把八条线的坐标列成表格然后照着表格写判断条件。这个过程看起来很笨但能有效减少下标错误。第三一次通过的秘诀就是提前想好所有边界。每次提交前我会在样例之外再构造几个用例。比如全部标记、没有任何标记、只差一个格子就 Bingo、副对角线恰好成立。这组用例跑下来基本可以覆盖所有分支。2021年10月29日那天我用最朴素的写法把这道题一次 AC。现在回头看它仍然是我愿意推荐给新手的题目之一不靠奇技淫巧纯粹考察你能不能把一句话描述的问题变成一段不会出错的代码。
