这道题我在考场上花了大概七分钟才完全想明白出来之后和几个同学对答案发现不少人都是直接开二维数组模拟蛇形填数虽然能过样例但心里其实没底。说实话“座位”这道题放在 CSP-J 2025 的卷子里考察的并不是多高深的算法而是你愿不愿意把一个看似“模拟”的问题用数学的方式化简到 O(1) 的程度。这篇文章我就把蛇形矩阵和坐标计算的完整思路拆开讲清楚包括公式怎么推、代码怎么写、考场上哪些坑最容易踩希望能帮后面备考的同学少走弯路。1. 题目全景先读懂“座位”在考什么1.1 场景还原与题目假设“座位”这道题的背景设定大概是这样的某考场里有一排排的座位排列成一个 n 行 m 列的矩形。座位的编号方式比较特殊——不是每一行都从左到右排而是第一行从左到右第二行从右到左第三行又从左到右像蛇一样来回折返。这种排列方式在现实中其实很常见比如一些阶梯教室的座位号、长途大巴的座位编号都会用这种“蛇形”的方式让乘客或考生能更快找到自己的位置。题目会给一个具体的座位编号 k要求你输出这个座位在第几行第几列。有些版本的题目还会反过来给定行列求编号但核心数学结构是一样的。正常情况下n 和 m 的范围不会太大比如 n、m ≤ 1000k ≤ n×m但在最优解法的要求下不管范围多大都应该追求一步算出结果而不是老老实实填表。我第一次看到这个题的时候第一反应是“这不就是二维数组模拟吗”但再一想如果 n、m 特别大开数组倒是没问题可如果题目改成多组询问比如 q 次查询每次给一个 k模拟法的时间复杂度就是 O(q×n×m)很容易超时。即便只有单次询问模拟法也需要 O(n×m) 的时间去生成整个矩阵而数学方法只需要 O(1)。这正是这道题想要考察的你能不能把“蛇形”这个规律抽象成坐标公式。1.2 核心考点拆解从信息学竞赛的角度看这道题至少涉及以下三个核心能力第一是规律提取能力。蛇形矩阵的排列规律并不复杂——奇数行从左往右偶数行从右往左这里的行号从 1 开始但很多人会直接陷入“模拟填充”的思维定式没想过可以用整除和取模直接定位。第二是数学建模能力。把“编号 k 对应第几行第几列”这个问题拆解成两步先确定行再确定列。确定行可以用 (k-1) div m确定列需要根据行号的奇偶性做不同处理。这里面最容易被忽略的是“编号从 1 开始”还是“从 0 开始”的转换几乎所有出错的同学都栽在这里。第三是代码实现与边界处理能力。公式推导出来了写代码只有几行但取模、整除、下标偏移这些细节稍不注意就会差一。考场上时间紧张越简单的题目越容易因为粗心丢分。接下来我就从蛇形矩阵的本质讲起一步步推导坐标公式再给出完整的参考实现和调试心得。2. 蛇形矩阵从遍历方式到填充逻辑2.1 什么是蛇形矩阵蛇形矩阵Snake Matrix是一种常见的矩阵排列方式也叫“回形遍历”的一种变体。标准的蛇形矩阵是指从左上角开始第一行从左到右填充第二行从右到左填充第三行再从左到右如此反复直到填满整个矩阵。举个例子一个 3 行 4 列的蛇形矩阵编号从 1 开始长这样1 2 3 4 8 7 6 5 9 10 11 12注意第二行是从右往左的所以 5 在第二行的最右边6 在倒数第二列7 在第二列8 在第一列。如果你把编号按顺序读出来它的路径就像一条蛇在矩阵里来回游走。这种矩阵有几个直观的性质每一行的编号是连续的一段整数。相邻两行的编号方向相反。行与行之间的编号是首尾相接的即第 i 行的最后一个编号和第 i1 行的第一个编号在数值上相邻比如上图中的 4 和 58 和 9。基于这些性质我们其实不需要真的把矩阵画出来只需要通过数学计算定位任意一个编号的位置。2.2 纯模拟方案的利与弊很多初学者拿到这道题第一反应是写这样的代码int a[1005][1005]; int cnt 1; for (int i 1; i n; i) { if (i % 2 1) { for (int j 1; j m; j) a[i][j] cnt; } else { for (int j m; j 1; j--) a[i][j] cnt; } } // 然后输出 a[(k-1)/m1][?] 或者直接遍历找 k这种方案的优点是思路直观不容易错而且如果题目只要求单次询问n 和 m 在 1000 以内时间和空间都完全够用。但缺点也很明显如果 n、m 达到 10^5 甚至更大二维数组成百上千万甚至上亿的 int 空间就非常紧张如果题目有多次询问每次询问都重新生成矩阵时间开销也不小。更重要的是在 CSP-J 的考场上出题人往往希望你能写出更优的解法。模拟法虽然能拿分但可能不是满分思路的预期方向。尤其当题目描述中提示“n、m 很大”或者“有 q 次询问”时数学方法就成了必须掌握的技能。2.3 坐标计算方案的核心思想坐标计算方案的核心思想就一句话不要生成矩阵直接算位置。我们知道蛇形矩阵中每一行有 m 个位置那么编号 k 所在的行号就是看 k 是第几个“完整行”之后的余数。更严谨地说如果把编号先转换成从 0 开始即 k-1那么行号 (k-1) / m整除行内偏移 (k-1) % m行号从 0 开始计数时第 0 行、第 2 行、第 4 行……是“正向行”从左到右第 1 行、第 3 行、第 5 行……是“反向行”从右到左。对于正向行列号就是行内偏移对于反向行列号是 m-1-offset。这就是整个题目的核心公式。为了让你彻底理解这个公式的来龙去脉下一节我会把它一步步拆开从一维编号到二维坐标的映射关系讲起。3. 坐标公式的完整推导过程3.1 行号确定整除与偏移的配合要确定一个编号 k 在第几行首先要明确“每行有多少个座位”。每行有 m 个座位那么从第 1 行到第 i 行总共能容纳的座位数是 i×m。给定 k我们要找最小的 i使得 i×m ≥ k。这个 i 就是行号从 1 开始计数。如果你熟悉整除运算就会知道 (k-1)/m 1 就是这个 i。为什么用 k-1 而不是 k因为编号从 1 开始如果 k 恰好是 m 的整数倍比如 k8m4直接用 k/m 会得到 2但实际上 8 在第 2 行行号从 1 开始而不是第 3 行。用 k-1 之后8 变成 77/41再加 1 得到 2就对了。计算机里整除是向下取整所以这一套是自洽的。我们定义row0 (k - 1) / m // 0-based 行号 offset (k - 1) % m // 行内偏移0 到 m-1这里的 row0 是“从 0 开始计数的行号”它在后面判断奇偶性时会用到。最终输出的行号从 1 开始是 row0 1。3.2 列号与方向的关系奇偶行的不同处理现在我们已经知道 k 在第 row0 行以及它在行内的偏移量 offset。问题是这一行到底是正向还是反向回到蛇形矩阵的定义行号从 1 开始时奇数行正向偶数行反向。但这里 row0 是从 0 开始的所以row0 为偶数0、2、4...→ 对应实际行号 1、3、5... → 正向行列号 offsetrow0 为奇数1、3、5...→ 对应实际行号 2、4、6... → 反向行列号 m - 1 - offset这样做的原因是正向行的第 offset 个位置从 0 开始就是从左往右数第 offset1 个位置反向行则相反从左往右数第 m-offset 个位置因为 offset0 对应最右边offsetm-1 对应最左边。用代码表示就是int col; if (row0 % 2 0) { col offset 1; // 1-based 列号 } else { col m - offset; // 1-based 列号 }这里要注意输出约定如果题目要求行列都从 1 开始那么行号直接输出 row01列号按上面的公式输出。如果题目要求从 0 开始则相应调整。3.3 边界条件的处理与特殊情况边界条件是这类题目最容易翻车的地方我列几个典型的特殊情况k1row00offset0行号为 1列号为 1。这是最基础的情况一般不会错。km第一行最后一个位置row00offsetm-1行号 1列号 m。也没问题。km1第二行第一个位置即最右边row01offset0第二行是反向行列号 m - 0 m。也就是说编号 m1 在第 2 行第 m 列。这与蛇形矩阵的定义完全一致——第二行从最右边开始填。kn×m最后一个位置row0n-1offsetm-1。如果 n 是奇数row0 为偶数列号为 m如果 n 是偶数row0 为奇数列号为 1。这说明最后一个位置要么在最后一行的最右边要么在最后一行最左边取决于最后一行的方向。还有一种特殊情况是 m1。此时每行只有一个座位所有编号都在第 1 列。套用公式offset 恒为 0反向行的列号 1 - 0 1正向行列号 011完全正确。这提醒我们公式的普适性不需要单独特判。另外要注意输入数据的编号 k 合法性题目一般会保证但如果自己造数据测试建议加一个 if (k 1 || k n*m) 的防御性判断。虽然竞赛中不强制但好的习惯能避免调试时的困惑。4. 代码实现与细节优化4.1 C 参考实现根据上面的推导完整代码如下#include iostream using namespace std; int main() { int n, m, k; cin n m k; // 将编号 k 转为 0-based 来计算行号和行内偏移 int row0 (k - 1) / m; int offset (k - 1) % m; int row row0 1; // 1-based 行号 int col; if (row0 % 2 0) { // 正向行从左到右 col offset 1; } else { // 反向行从右到左 col m - offset; } cout row col endl; return 0; }这个代码的时间复杂度是 O(1)空间复杂度是 O(1)无论 n、m 多大无论有多少次询问每次查询都是常数时间。4.2 关键代码逐行解读让我逐行解释一下为什么这样写int row0 (k - 1) / m;这一行的目的是把“从 1 开始的编号”转换成“从 0 开始的行号”。为什么要从 0 开始因为 C 的整除和取模天然是 0-based 的而且判断奇偶性时0 代表第一行1 代表第二行逻辑更顺畅。int offset (k - 1) % m;offset 表示 k 在它所处行中的位置同样是从 0 开始。offset0 表示该行的第一个位置正向行是最左边反向行是最右边。if (row0 % 2 0)判断当前行是正向还是反向。行号从 0 开始计数偶数即正向。这里不要写成row0 % 2 1来判断反向容易把自己绕晕。列号的计算可以合并为一行int col (row0 % 2 0) ? (offset 1) : (m - offset);很多同学看到反向行的列号m - offset会疑惑offset 是 0 时colmoffset 是 m-1 时col1这不就反过来了吗没错这正是反向行从左往右数时的“倒序”效果。这是一个很常见的思维转换点我当初理解这个公式时也花了点时间。4.3 多种写法的对比与取舍除了上面这种“直接计算”的写法有些同学会倾向于先算出行号再分情况讨论int row (k - 1) / m 1; int col; if (row % 2 1) { col (k - 1) % m 1; } else { col m - (k - 1) % m; }这种写法在数学上等价但要注意row是 1-based 的所以判断正向行要用row % 2 1而不是 0。两种写法都可以但我个人更推荐 0-based 的版本因为可以减少“行号从 1 开始”和“整除从 0 开始”之间的混淆。还有一种写法是用 while 循环逐行减去 m找到行号int row 1; while (k m) { k - m; row; } // 此时 k 是行内位置这种写法虽然也能得到正确结果但时间复杂度是 O(row)最坏情况下是 O(n)不够优。如果 n 很大比如 10^9这种写法就会超时。所以在竞赛中能用 O(1) 的数学方法就不要用循环。5. 常见问题与考场避坑指南5.1 高频错误Top 5根据我和周围同学的实际刷题经历这道题最容易出现以下几个错误错误类型错误示例正确做法编号转换错误直接用 k/m 算行号必须用 (k-1)/m奇偶行判断混淆行号从 1 开始时用 row%20 判断正向0-based 行号偶数正向1-based 行号奇数正向反向行列号公式记错写成 coloffset1反向行应为 colm-offset行列输出顺序颠倒题干要求先列后行仔细读题通常先行后列多组查询未封装每次重复写公式封装成函数calcPos(n,m,k)这里我特别想强调一下“编号转换错误”。很多同学知道要减一但不知道为什么要减一。核心原因在于整除运算在“恰好整除”的时候会得到偏大的结果。比如 k4m4如果用 k/m1意味着第 1 行但实际 4 应该是第 1 行的最后一个不是第 2 行的第一个。k-1 之后变成 3/40行号就是 011正确。同理取模也一样k4 时 k%m0这个 0 表示“第 0 个位置”实际上就是行内最后一个位置配合正向/反向公式就能得到正确的列号。5.2 考场上的推导技巧与心算如果你在考场上忘了公式怎么快速推导我的建议是画一个 3×4 的表格手动填上编号然后观察规律1 2 3 4 8 7 6 5 9 10 11 12比如要查 7 的位置。7 在第二行第四列。套公式k7m4(k-1)/m6/410-based 行号所以是第 2 行(k-1)%m6%42offset因为 row01 是奇数反向行列号 4-22等等4-22但 7 在第二行第四列啊这里哪里出了问题慢着我再仔细算一下。7 在第二行的位置是第四列让我重新看矩阵第1行: 1 2 3 4 第2行: 8 7 6 5 第3行: 9 10 11 127 是第二行的第二个元素从左往右数也就是第四列不对7 在第二行从左往右数是第 2 个位置第 2 列。但行内位置编号从左到右是第 1 行: 1,2,3,4第 2 行从右往左填所以第 2 行的位置从左往右看是 5,6,7,8对应编号 8,7,6,5所以 7 在从左往右第 2 个位置即第 2 列。刚才我说第四列是口误应该是第二列。验证公式k7row06/41offset6%42row0 为奇数列号 col m - offset 4 - 2 2正确第二行第二列。第二个例子k8row07/41offset7%43col 4-31即第二行第一列也对8 在第二行最左边。所以画图验证的时候一定要仔细别自己把自己绕晕。我建议在草稿纸上把编号标好再用公式结果对照心算虽然方便但容易看错位置。5.3 我踩过的坑与最终体会我自己最初写这题时犯过一个特别蠢的错误我把矩阵画成从 0 开始编号然后套公式结果所有列号都差 1。后来我总结出一个经验无论题目怎么描述先决定好内部计算是用 0-based 还是 1-based然后整个流程保持一致。我个人的习惯是计算时统一用 0-based最后输出时加 1这样可以最大程度减少混淆。还有一个细节是输入输出的格式。有些题目要求行和列之间用空格分隔有些要求逗号有些要求输出(row, col)的括号形式。不仔细看题格式错误可能直接导致 0 分。我在模拟赛中就被扣过一次从那以后每次看到输出要求都会画个圈。另外如果你用 Python 答题公式完全一样只是要注意//和%的优先级n, m, k map(int, input().split()) row0 (k - 1) // m offset (k - 1) % m row row0 1 col offset 1 if row0 % 2 0 else m - offset print(row, col)C 和 Python 的整除对负数处理不同但这题所有输入都是正整数不存在负数取模的坑所以两种语言都安全。最后整理一下这道题的知识关联蛇形矩阵本质上是“分段线性映射”你需要把一维的编号通过行宽 m 映射到二维的网格上。这种“整除定位、取模定位、奇偶定向”的三步走思路还能迁移到很多类似的矩阵题中比如螺旋矩阵、锯形访问数组、Z 字形遍历等。把这一道题吃透等于同时掌握了这一类坐标映射题的通用解法。我在后续刷题中遇到“按某种规律排列矩阵然后给定编号求位置”的题基本都能用这套思路快速解决。这也是我这篇文章最想传达给你的东西。如果你在按这个思路实现的过程中发现任何问题或者有其他更好的推导方法欢迎交流。毕竟竞赛题最有趣的地方就在于每个人的思考路径都不太一样。说不定你的视角比我的更简洁。