解法：从数据范围看穿暴力模拟，圈层公式一步定位)
1. 一道普及组第三题为什么不能直接模拟填表P2239 螺旋矩阵是 NOIP 2014 普及组的第三题。题面出奇地简短一个 n 行 n 列的矩阵从左上角 (1,1) 出发按顺时针方向由外向内依次填入 1 到 n²。现在给定 n、i、j 三个整数要求直接输出 (i,j) 这个位置上的数。我当年第一次拿到这题第一反应也是这不就是模拟吗。写个二维数组控制方向碰到边界就右转填完整个矩阵再查表十几分钟就能搞定。但请注意题目里的数据范围n 最大能到 30000。这意味着矩阵最多有 9×10⁸ 个格子也就是九亿个数。这个数字一出来所有模拟方案都得重新掂量。这道题适合两类人仔细看一是正在备战 NOIP/CSP 普及组、想理解数据范围如何决定算法方向的选手二是已经会写模拟、但希望掌握从 O(n²) 优化到 O(1)这一类观察技巧的人。整道题的核心就一句话只给你一个坐标你要在不生成整个矩阵的前提下把这个位置的数直接算出来。1.1 三句话的题面藏着一个 30000 的陷阱先明确题目的输入输出结构参数范围含义n1 ≤ n ≤ 30000矩阵边长i, j1 ≤ i, j ≤ n查询坐标行、列从 1 开始答案最大 n²即 9×10⁸目标位置上的数字n30000 意味着什么先算内存账一个 int 二维数组30000×30000×4 字节大约是 3.6GB。竞赛里常见的限制是 256MB这个量级连边都摸不到直接分配就会被系统按下去。再算时间账就算内存管够把九亿个格子填一遍每填一个还要判断方向是否越界在 1 秒的限制内几乎是必死无疑。所以数据范围这个不起眼的约束其实是出题人埋下的第一道提示常规模拟走不通你要么找规律要么找数学表达式。很多选手栽跟头不是不会写模拟而是压根没把数据范围当回事。1.2 问什么就算什么单点查询的优化直觉换个角度想如果题目要求把整个螺旋矩阵打印出来那模拟完全没毛病因为输出本身就需要 O(n²) 的工作量。但原题只要一个坐标上的值输出规模是 O(1)。这就在提醒我们题目问什么你就只算什么。既然只需要一个点的值那就应该努力找到坐标 → 数值的直接映射而不是去遍历所有不相干的格子。这种思维在算法竞赛里叫观察结构、建立数学模型在工程里叫按需计算本质都是拒绝无脑的全局劳动。好消息是这个映射关系不仅存在而且简单到只需要一次取最小值、一次乘法和几次加法。下面我们一步一步把它扒出来。2. 螺旋矩阵的圈层结构就是解题的钥匙2.1 外圈先填内圈后填矩阵天然分成一层层方框观察螺旋矩阵的填充顺序从 (1,1) 向右走到右上角再向下到右下角再向左到左下角再向上回到第二行附近此时最外圈刚好填满。接着指针进入 (2,2)开始填第二圈如此反复。所以整个矩阵可以看成一层套一层的正方形边框像切洋葱。从外到内每一圈的边长都在缩小第一圈边长 n第二圈 n-2第三圈 n-4……直到最中间。如果 n 是奇数最里面是一个单独的格子如果 n 是偶数最里面是一个 2×2 的小圈。这个圈的概念是整道题的命门。只要确定了目标点在第几圈、在这一圈的哪条边、走了多少步答案就出来了。2.2 一步定位圈号到四条边的最小距离给定坐标 (i,j)它属于第几圈最直观的判断标准是看它到四条边的距离。用 1 索引坐标来说点 (i,j) 到上边的距离是 i-1到下边是 n-i到左边是 j-1到右边是 n-j。这四个距离里的最小值决定了这个点从外往里数在第几层。换算成从 1 开始的圈号k min(i, j, n1-i, n1-j)注意右边用的是 n1-i 和 n1-j而不是 n-i 和 n-j。因为 i、j 是 1 索引对称边要拿 n1 去减才对得上。举个例子n4 时点 (2,2)到上边距离 1到下边 2到左边 1到右边 2最小值 1所以圈号 k2点 (1,1) 到上边距离 0最小值 0加 1 后是 k1在第一圈。这个公式一旦写错后面全盘皆输后面我还会专门强调。2.3 每圈周长是个等差数列求和有公式第 k 圈的边长是多少第一圈是 n第二圈因为上下左右各缩进一格边长是 n-2所以第 k 圈边长m n - 2×(k-1)这一圈实际要填的格子数也就是周长是P 4×(m-1)为什么用 m-1 而不是 m因为正方形的四个角会被四条边重复计数按每条边走 m 格来算四个角各多算一次所以边框格子数是 4m-4 4×(m-1)。验证一下n4 时第一圈边长 4边框格子应该是 12 个4×(4-1)12正好。每一圈的周长会随着 k 增大而等差递减公差是 8。这个等差性质直接让我们能用求和公式快速算出前 k-1 圈一共填了多少个数这正是下一步推导起始值的基础。3. 三条公式把坐标翻译成数字3.1 第 k 圈的起始值 start 是怎么推出来的想知道 (i,j) 在圈里的精确位置得先知道这一圈从哪个数开始填。第 k 圈开始填之前外层的 k-1 圈肯定已经全部填完。把前 k-1 圈的格子总数算出来加 1就是第 k 圈的起始值。前 k-1 圈的周长之和是S Σ(t1 到 k-1) 4×(n-2t1)这是一个等差数列求和。把 4 提出来括号里的项求和S 4 × [(k-1)×(n1) - 2×(12...k-1)] 4 × [(k-1)×(n1) - (k-1)×k] 4×(k-1)×(n1-k)所以第 k 圈的起始值start 4×(k-1)×(n1-k) 1验证一下n4 时k1start1k2start4×1×(41-2)14×3113。看 4×4 螺旋矩阵1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7第二圈确实从 13 开始完全吻合。再多验一个 n5第二圈起始应该是 17公式算出来是 4×1×(51-2)117也对。3.2 上右下左四条边的偏移量怎么加知道起始值后剩下的事就是计算 (i,j) 在它所在圈上走了多少步答案等于 start 加上这个偏移量。以第 k 圈左上角 (k,k) 为起点顺时针走整圈被切成四段上边条件是 i k。从起点 (k,k) 向右走到 (k,j)走了 j-k 步值 start (j-k)。右边条件是 j n-k1。走完上边需要 m-1 步再从上边往下走到 (i, n-k1)又走了 i-k 步值 start (m-1) (i-k)。下边条件是 i n-k1。此时上边和右边都已经走完共 2×(m-1) 步然后从右下角往左走 n-k1-j 步值 start 2×(m-1) (n-k1-j)。左边条件是 j k且点不在最下面一行否则会被下边分支命中。走完三条边一共 3×(m-1) 步再从左下角往上走 n-k1-i 步值 start 3×(m-1) (n-k1-i)。判断顺序固定为先上边、再右边、再下边、最后左边这是有讲究的。四个角上的点同时满足两条边的条件比如左上角 (k,k) 既满足 ik 也满足 jk按这个顺序判断角会归入它遇到的第一条边不会重复也算不错位。你要是把左边的判断放前面四个角的答案全部会乱而且小样本还不一定能测出来。3.3 完整公式速查表把上面所有公式收拢成一张表写代码时直接对照位置条件计算公式i k上边start (j - k)j n-k1右边start (m-1) (i-k)i n-k1下边start 2×(m-1) (n-k1-j)j k左边start 3×(m-1) (n-k1-i)其中 k、m、start 分别按前文的公式计算。整个算法只有常数次运算不管 n 是 30000 还是几百万都是一瞬间出结果。4. 参考实现与逐行验证4.1 20 行 C 代码直接交#include bits/stdc.h using namespace std; int main() { int n, i, j; cin n i j; int k min({i, j, n 1 - i, n 1 - j}); long long start 4LL * (k - 1) * (n 1 - k) 1; int m n - 2 * (k - 1); long long ans; if (i k) { ans start (j - k); } else if (j n - k 1) { ans start (m - 1) (i - k); } else if (i n - k 1) { ans start 2LL * (m - 1) (n - k 1 - j); } else { ans start 3LL * (m - 1) (n - k 1 - i); } cout ans \n; return 0; }几个细节说明。第一start 前面写 4LL强制把乘法提升到 long long防止中间过程溢出。第二min({a,b,c,d}) 是 C11 的 initializer_list 写法老编译器就老老实实嵌套四层 min。第三最后那个 else 不需要再判断 jk因为走到 else 时点既不在上边、右边、下边那必然在左边。4.2 官方样例加上四个角逐一手算核对还是用那张 4×4 的矩阵验证官方两个样例。输入 4 2 3k min(2,3,3,2) 2start 13m 2。先判断 ik22 成立ans 13 (3-2) 14。矩阵里 (2,3) 位置确实是 14通过。输入 4 3 2k min(3,2,2,2) 2start 13m 2。ik 不成立jn-k1 即 23 不成立in-k1 即 33 成立进入下边分支ans 13 2×(2-1) (4-21-2) 1321 16。矩阵里 (3,2) 确实是 16通过。再补测四个角。n4 时 (1,4)k1start1m4ik 成立ans 1(4-1)4正确(4,4)k1ik 不成立j4 成立走右边ans 1(4-1)(4-1)7正确(4,1)依次判断后落到下边分支ans 12×3(4-11-1)10正确。实际矩阵里右上角是 4、右下角是 7、左下角是 10全中。4.3 n1 和 n2 的极端情况也别放过n1 时矩阵只有一个格子答案必然是 1。套公式k min(1,1,1,1)1start4×0×(11-1)11m1。ik 成立ans 1(1-1)1稳。n2 时矩阵是1 2 4 3随便取一个容易被坑的坐标 (2,1)k min(2,1,1,2)1start1m2。ik 不成立jn-k1 即 12 不成立in-k1 即 22 成立ans 12×(2-1)(2-11-1)1214正确。特别留意 m1 的场景此时 m-102×(m-1)、3×(m-1) 都是 0不会产生负数偏移。但前提是分支顺序正确n1 时点只可能落进上边分支不会跑到后面。所以代码里用 if-else 链而不是四个独立 if这个顺序保护是必须的。5. 常见问题与排查技巧实录5.1 样例全过却 WA先检查圈号公式和分支顺序最常见的翻车点就是圈号写错。有人写成 k min(i, j, n-i, n-j)这在很多点上会差 1。比如 n4 的 (4,4)正确 k1错误算出来 min(4,4,0,0)0直接变成第 0 圈后面的 m 和 start 全部乱套。记住1 索引坐标的下边距和右边距是 n-i、n-j但要换算成从 1 开始的圈号必须用 n1-i、n1-j这样第一圈的边界 1 和 n 才是对称的。更隐蔽的问题是分支顺序。如果把左边判断放在下边前面左下角 (n-k1, k) 会被错误归入左边分支因为它的 j 就是 k但它属于下边那段路。我见过有人用四个独立 if 写导致角被算两次或者被错误分支带走。建议死守上→右→下→左的 if-else 链这和顺时针方向一一对应逻辑上最顺。5.2 大数据超时是不是还在老老实实转圈如果你发现 n100 能过、n30000 超时基本可以断定你在填整个矩阵。模拟填表的复杂度是 O(n²)n30000 时就是九亿次操作哪怕每次操作只有几行代码也远超 1 秒限制。反过来如果用本文的 O(1) 算法还超时那就查查读入输出是不是用了 endl 而不是 \nendl 会强制刷新缓冲区在输出量大时拖慢程序。这道题单次查询正解代码运行时间应该在毫秒级。5.3 溢出和类型选择的细节n 最大 30000 时n²9×10⁸答案本身没超过 int 上限 2.1×10⁹所以很多题解用 int 也能过。但注意 start 的计算式里有 4×(k-1)×(n1-k)k 取中间值约 15000 时乘积大约是 4×15000×150009×10⁸也没超 int。真正危险的是你如果临时改公式、或者写了个等价变形中间某个因子可能悄悄超界。竞赛里最省心的做法就是干脆声明 long long几行代码的代价换一晚上不焦虑。5.4 一个自查技巧局部手算对照我常用的自查方法算完答案先别急着交把目标点附近几个已知点一起算一遍。比如 n5 时第一圈起始 1第二圈起始 17第二圈上边的数应该是 17、18、19、20、21。你算 (2,3) 时如果得到 18说明上边分支的偏移方向对了如果得到 20那很可能是把 j-k 写成了 n-k1-j 之类方向反了。这种局部手算对照法能秒杀公式里的符号错误比反复提交试错快得多。6. 从这道题看竞赛思维的养成6.1 普及组第三题真正考的是观察力NOIP 2014 普及组的 T1、T2 是比较直接的模拟和简单枚举到了 T3 突然上强度目的就是把只会写循环和会观察规律的学生区分开。螺旋矩阵这题只要你愿意在草稿纸上画一个 5×5 的矩阵把每圈的起始数标出来n5 时是 1、17、25很快就能发现起始数是外层周长累加的规律。竞赛里相当一部分题都是这样暴力解法一眼可见优化方案藏在数据结构与数学结构里就看你能不能从数据范围里读出警告信号。6.2 同款思维能迁移到哪些题按需计算、避免整体构造的思路在任何涉及大规模枚举的题目里都用得上。比如 P2831NOIP 2016 提高组 愤怒的小鸟暴力枚举所有抛物线组合是阶乘级爆炸正解用状态压缩把枚举降到 O(2ⁿ·n)第一步同样是质疑全枚举是否可行。再比如 25 年 CSP-J 普及组的座位类问题很多也是在考察你能不能把看似需要模拟全局的规则压缩成几个关键变量直接推算。它们的共同套路是先看数据范围再评估模拟可行性不可行就找递推、找公式、找状态压缩。6.3 我的实操体会与刷题建议我第一次做这题时也写过两百行的方向模拟调了半天只拿 40 分小 n 全过、大数据超时。后来静下心画图十分钟就推出了圈号公式。这个经历让我养成了一个习惯见到矩阵、棋盘、排座位这类题先问自己三个问题——数据范围允许整体构造吗问题要的是全局信息还是单个点规律能不能用数学式子表达如果你正在备战 CSP-J/NOIP 普及组建议把这类结构题单独建一个错题本。螺旋矩阵之外还有蛇形矩阵、旋转矩阵、锯齿遍历等变体核心都是坐标系变换和边界控制。每做一道就手写一遍小规模样例的推导过程坚持十几道你对看到数据范围就条件反射地评估算法会变得非常敏感。最后分享一个小习惯我复盘这题时会把 n 从 1 到 6 的螺旋矩阵全部手画一遍然后随机取坐标用公式和手画结果对照。这个方法帮我抓出过不止一次边界分支写反的问题。希望你做完这道题也能体会到公式比模拟更接近问题的本质这种乐趣。
螺旋矩阵O(1)解法：从数据范围看穿暴力模拟，圈层公式一步定位
1. 一道普及组第三题为什么不能直接模拟填表P2239 螺旋矩阵是 NOIP 2014 普及组的第三题。题面出奇地简短一个 n 行 n 列的矩阵从左上角 (1,1) 出发按顺时针方向由外向内依次填入 1 到 n²。现在给定 n、i、j 三个整数要求直接输出 (i,j) 这个位置上的数。我当年第一次拿到这题第一反应也是这不就是模拟吗。写个二维数组控制方向碰到边界就右转填完整个矩阵再查表十几分钟就能搞定。但请注意题目里的数据范围n 最大能到 30000。这意味着矩阵最多有 9×10⁸ 个格子也就是九亿个数。这个数字一出来所有模拟方案都得重新掂量。这道题适合两类人仔细看一是正在备战 NOIP/CSP 普及组、想理解数据范围如何决定算法方向的选手二是已经会写模拟、但希望掌握从 O(n²) 优化到 O(1)这一类观察技巧的人。整道题的核心就一句话只给你一个坐标你要在不生成整个矩阵的前提下把这个位置的数直接算出来。1.1 三句话的题面藏着一个 30000 的陷阱先明确题目的输入输出结构参数范围含义n1 ≤ n ≤ 30000矩阵边长i, j1 ≤ i, j ≤ n查询坐标行、列从 1 开始答案最大 n²即 9×10⁸目标位置上的数字n30000 意味着什么先算内存账一个 int 二维数组30000×30000×4 字节大约是 3.6GB。竞赛里常见的限制是 256MB这个量级连边都摸不到直接分配就会被系统按下去。再算时间账就算内存管够把九亿个格子填一遍每填一个还要判断方向是否越界在 1 秒的限制内几乎是必死无疑。所以数据范围这个不起眼的约束其实是出题人埋下的第一道提示常规模拟走不通你要么找规律要么找数学表达式。很多选手栽跟头不是不会写模拟而是压根没把数据范围当回事。1.2 问什么就算什么单点查询的优化直觉换个角度想如果题目要求把整个螺旋矩阵打印出来那模拟完全没毛病因为输出本身就需要 O(n²) 的工作量。但原题只要一个坐标上的值输出规模是 O(1)。这就在提醒我们题目问什么你就只算什么。既然只需要一个点的值那就应该努力找到坐标 → 数值的直接映射而不是去遍历所有不相干的格子。这种思维在算法竞赛里叫观察结构、建立数学模型在工程里叫按需计算本质都是拒绝无脑的全局劳动。好消息是这个映射关系不仅存在而且简单到只需要一次取最小值、一次乘法和几次加法。下面我们一步一步把它扒出来。2. 螺旋矩阵的圈层结构就是解题的钥匙2.1 外圈先填内圈后填矩阵天然分成一层层方框观察螺旋矩阵的填充顺序从 (1,1) 向右走到右上角再向下到右下角再向左到左下角再向上回到第二行附近此时最外圈刚好填满。接着指针进入 (2,2)开始填第二圈如此反复。所以整个矩阵可以看成一层套一层的正方形边框像切洋葱。从外到内每一圈的边长都在缩小第一圈边长 n第二圈 n-2第三圈 n-4……直到最中间。如果 n 是奇数最里面是一个单独的格子如果 n 是偶数最里面是一个 2×2 的小圈。这个圈的概念是整道题的命门。只要确定了目标点在第几圈、在这一圈的哪条边、走了多少步答案就出来了。2.2 一步定位圈号到四条边的最小距离给定坐标 (i,j)它属于第几圈最直观的判断标准是看它到四条边的距离。用 1 索引坐标来说点 (i,j) 到上边的距离是 i-1到下边是 n-i到左边是 j-1到右边是 n-j。这四个距离里的最小值决定了这个点从外往里数在第几层。换算成从 1 开始的圈号k min(i, j, n1-i, n1-j)注意右边用的是 n1-i 和 n1-j而不是 n-i 和 n-j。因为 i、j 是 1 索引对称边要拿 n1 去减才对得上。举个例子n4 时点 (2,2)到上边距离 1到下边 2到左边 1到右边 2最小值 1所以圈号 k2点 (1,1) 到上边距离 0最小值 0加 1 后是 k1在第一圈。这个公式一旦写错后面全盘皆输后面我还会专门强调。2.3 每圈周长是个等差数列求和有公式第 k 圈的边长是多少第一圈是 n第二圈因为上下左右各缩进一格边长是 n-2所以第 k 圈边长m n - 2×(k-1)这一圈实际要填的格子数也就是周长是P 4×(m-1)为什么用 m-1 而不是 m因为正方形的四个角会被四条边重复计数按每条边走 m 格来算四个角各多算一次所以边框格子数是 4m-4 4×(m-1)。验证一下n4 时第一圈边长 4边框格子应该是 12 个4×(4-1)12正好。每一圈的周长会随着 k 增大而等差递减公差是 8。这个等差性质直接让我们能用求和公式快速算出前 k-1 圈一共填了多少个数这正是下一步推导起始值的基础。3. 三条公式把坐标翻译成数字3.1 第 k 圈的起始值 start 是怎么推出来的想知道 (i,j) 在圈里的精确位置得先知道这一圈从哪个数开始填。第 k 圈开始填之前外层的 k-1 圈肯定已经全部填完。把前 k-1 圈的格子总数算出来加 1就是第 k 圈的起始值。前 k-1 圈的周长之和是S Σ(t1 到 k-1) 4×(n-2t1)这是一个等差数列求和。把 4 提出来括号里的项求和S 4 × [(k-1)×(n1) - 2×(12...k-1)] 4 × [(k-1)×(n1) - (k-1)×k] 4×(k-1)×(n1-k)所以第 k 圈的起始值start 4×(k-1)×(n1-k) 1验证一下n4 时k1start1k2start4×1×(41-2)14×3113。看 4×4 螺旋矩阵1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7第二圈确实从 13 开始完全吻合。再多验一个 n5第二圈起始应该是 17公式算出来是 4×1×(51-2)117也对。3.2 上右下左四条边的偏移量怎么加知道起始值后剩下的事就是计算 (i,j) 在它所在圈上走了多少步答案等于 start 加上这个偏移量。以第 k 圈左上角 (k,k) 为起点顺时针走整圈被切成四段上边条件是 i k。从起点 (k,k) 向右走到 (k,j)走了 j-k 步值 start (j-k)。右边条件是 j n-k1。走完上边需要 m-1 步再从上边往下走到 (i, n-k1)又走了 i-k 步值 start (m-1) (i-k)。下边条件是 i n-k1。此时上边和右边都已经走完共 2×(m-1) 步然后从右下角往左走 n-k1-j 步值 start 2×(m-1) (n-k1-j)。左边条件是 j k且点不在最下面一行否则会被下边分支命中。走完三条边一共 3×(m-1) 步再从左下角往上走 n-k1-i 步值 start 3×(m-1) (n-k1-i)。判断顺序固定为先上边、再右边、再下边、最后左边这是有讲究的。四个角上的点同时满足两条边的条件比如左上角 (k,k) 既满足 ik 也满足 jk按这个顺序判断角会归入它遇到的第一条边不会重复也算不错位。你要是把左边的判断放前面四个角的答案全部会乱而且小样本还不一定能测出来。3.3 完整公式速查表把上面所有公式收拢成一张表写代码时直接对照位置条件计算公式i k上边start (j - k)j n-k1右边start (m-1) (i-k)i n-k1下边start 2×(m-1) (n-k1-j)j k左边start 3×(m-1) (n-k1-i)其中 k、m、start 分别按前文的公式计算。整个算法只有常数次运算不管 n 是 30000 还是几百万都是一瞬间出结果。4. 参考实现与逐行验证4.1 20 行 C 代码直接交#include bits/stdc.h using namespace std; int main() { int n, i, j; cin n i j; int k min({i, j, n 1 - i, n 1 - j}); long long start 4LL * (k - 1) * (n 1 - k) 1; int m n - 2 * (k - 1); long long ans; if (i k) { ans start (j - k); } else if (j n - k 1) { ans start (m - 1) (i - k); } else if (i n - k 1) { ans start 2LL * (m - 1) (n - k 1 - j); } else { ans start 3LL * (m - 1) (n - k 1 - i); } cout ans \n; return 0; }几个细节说明。第一start 前面写 4LL强制把乘法提升到 long long防止中间过程溢出。第二min({a,b,c,d}) 是 C11 的 initializer_list 写法老编译器就老老实实嵌套四层 min。第三最后那个 else 不需要再判断 jk因为走到 else 时点既不在上边、右边、下边那必然在左边。4.2 官方样例加上四个角逐一手算核对还是用那张 4×4 的矩阵验证官方两个样例。输入 4 2 3k min(2,3,3,2) 2start 13m 2。先判断 ik22 成立ans 13 (3-2) 14。矩阵里 (2,3) 位置确实是 14通过。输入 4 3 2k min(3,2,2,2) 2start 13m 2。ik 不成立jn-k1 即 23 不成立in-k1 即 33 成立进入下边分支ans 13 2×(2-1) (4-21-2) 1321 16。矩阵里 (3,2) 确实是 16通过。再补测四个角。n4 时 (1,4)k1start1m4ik 成立ans 1(4-1)4正确(4,4)k1ik 不成立j4 成立走右边ans 1(4-1)(4-1)7正确(4,1)依次判断后落到下边分支ans 12×3(4-11-1)10正确。实际矩阵里右上角是 4、右下角是 7、左下角是 10全中。4.3 n1 和 n2 的极端情况也别放过n1 时矩阵只有一个格子答案必然是 1。套公式k min(1,1,1,1)1start4×0×(11-1)11m1。ik 成立ans 1(1-1)1稳。n2 时矩阵是1 2 4 3随便取一个容易被坑的坐标 (2,1)k min(2,1,1,2)1start1m2。ik 不成立jn-k1 即 12 不成立in-k1 即 22 成立ans 12×(2-1)(2-11-1)1214正确。特别留意 m1 的场景此时 m-102×(m-1)、3×(m-1) 都是 0不会产生负数偏移。但前提是分支顺序正确n1 时点只可能落进上边分支不会跑到后面。所以代码里用 if-else 链而不是四个独立 if这个顺序保护是必须的。5. 常见问题与排查技巧实录5.1 样例全过却 WA先检查圈号公式和分支顺序最常见的翻车点就是圈号写错。有人写成 k min(i, j, n-i, n-j)这在很多点上会差 1。比如 n4 的 (4,4)正确 k1错误算出来 min(4,4,0,0)0直接变成第 0 圈后面的 m 和 start 全部乱套。记住1 索引坐标的下边距和右边距是 n-i、n-j但要换算成从 1 开始的圈号必须用 n1-i、n1-j这样第一圈的边界 1 和 n 才是对称的。更隐蔽的问题是分支顺序。如果把左边判断放在下边前面左下角 (n-k1, k) 会被错误归入左边分支因为它的 j 就是 k但它属于下边那段路。我见过有人用四个独立 if 写导致角被算两次或者被错误分支带走。建议死守上→右→下→左的 if-else 链这和顺时针方向一一对应逻辑上最顺。5.2 大数据超时是不是还在老老实实转圈如果你发现 n100 能过、n30000 超时基本可以断定你在填整个矩阵。模拟填表的复杂度是 O(n²)n30000 时就是九亿次操作哪怕每次操作只有几行代码也远超 1 秒限制。反过来如果用本文的 O(1) 算法还超时那就查查读入输出是不是用了 endl 而不是 \nendl 会强制刷新缓冲区在输出量大时拖慢程序。这道题单次查询正解代码运行时间应该在毫秒级。5.3 溢出和类型选择的细节n 最大 30000 时n²9×10⁸答案本身没超过 int 上限 2.1×10⁹所以很多题解用 int 也能过。但注意 start 的计算式里有 4×(k-1)×(n1-k)k 取中间值约 15000 时乘积大约是 4×15000×150009×10⁸也没超 int。真正危险的是你如果临时改公式、或者写了个等价变形中间某个因子可能悄悄超界。竞赛里最省心的做法就是干脆声明 long long几行代码的代价换一晚上不焦虑。5.4 一个自查技巧局部手算对照我常用的自查方法算完答案先别急着交把目标点附近几个已知点一起算一遍。比如 n5 时第一圈起始 1第二圈起始 17第二圈上边的数应该是 17、18、19、20、21。你算 (2,3) 时如果得到 18说明上边分支的偏移方向对了如果得到 20那很可能是把 j-k 写成了 n-k1-j 之类方向反了。这种局部手算对照法能秒杀公式里的符号错误比反复提交试错快得多。6. 从这道题看竞赛思维的养成6.1 普及组第三题真正考的是观察力NOIP 2014 普及组的 T1、T2 是比较直接的模拟和简单枚举到了 T3 突然上强度目的就是把只会写循环和会观察规律的学生区分开。螺旋矩阵这题只要你愿意在草稿纸上画一个 5×5 的矩阵把每圈的起始数标出来n5 时是 1、17、25很快就能发现起始数是外层周长累加的规律。竞赛里相当一部分题都是这样暴力解法一眼可见优化方案藏在数据结构与数学结构里就看你能不能从数据范围里读出警告信号。6.2 同款思维能迁移到哪些题按需计算、避免整体构造的思路在任何涉及大规模枚举的题目里都用得上。比如 P2831NOIP 2016 提高组 愤怒的小鸟暴力枚举所有抛物线组合是阶乘级爆炸正解用状态压缩把枚举降到 O(2ⁿ·n)第一步同样是质疑全枚举是否可行。再比如 25 年 CSP-J 普及组的座位类问题很多也是在考察你能不能把看似需要模拟全局的规则压缩成几个关键变量直接推算。它们的共同套路是先看数据范围再评估模拟可行性不可行就找递推、找公式、找状态压缩。6.3 我的实操体会与刷题建议我第一次做这题时也写过两百行的方向模拟调了半天只拿 40 分小 n 全过、大数据超时。后来静下心画图十分钟就推出了圈号公式。这个经历让我养成了一个习惯见到矩阵、棋盘、排座位这类题先问自己三个问题——数据范围允许整体构造吗问题要的是全局信息还是单个点规律能不能用数学式子表达如果你正在备战 CSP-J/NOIP 普及组建议把这类结构题单独建一个错题本。螺旋矩阵之外还有蛇形矩阵、旋转矩阵、锯齿遍历等变体核心都是坐标系变换和边界控制。每做一道就手写一遍小规模样例的推导过程坚持十几道你对看到数据范围就条件反射地评估算法会变得非常敏感。最后分享一个小习惯我复盘这题时会把 n 从 1 到 6 的螺旋矩阵全部手画一遍然后随机取坐标用公式和手画结果对照。这个方法帮我抓出过不止一次边界分支写反的问题。希望你做完这道题也能体会到公式比模拟更接近问题的本质这种乐趣。
