企业官网建设流程全解析

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 的陷阱

先明确题目的输入输出结构：

n=30000 意味着什么？先算内存账：一个 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, n+1-i, n+1-j)

注意右边用的是 n+1-i 和 n+1-j，而不是 n-i 和 n-j。因为 i、j 是 1 索引，对称边要拿 n+1 去减才对得上。举个例子：n=4 时点 (2,2)，到上边距离 1，到下边 2，到左边 1，到右边 2，最小值 1，所以圈号 k=2；点 (1,1) 到上边距离 0，最小值 0，加 1 后是 k=1，在第一圈。这个公式一旦写错，后面全盘皆输，后面我还会专门强调。

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)。验证一下：n=4 时第一圈边长 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 = Σ(t=1 到 k-1) 4×(n-2t+1)

这是一个等差数列求和。把 4 提出来，括号里的项求和：

S = 4 × [(k-1)×(n+1) - 2×(1+2+...+k-1)] = 4 × [(k-1)×(n+1) - (k-1)×k] = 4×(k-1)×(n+1-k)

所以第 k 圈的起始值：

start = 4×(k-1)×(n+1-k) + 1

验证一下：n=4 时，k=1，start=1；k=2，start=4×1×(4+1-2)+1=4×3+1=13。看 4×4 螺旋矩阵：

1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7

第二圈确实从 13 开始，完全吻合。再多验一个 n=5：第二圈起始应该是 17，公式算出来是 4×1×(5+1-2)+1=17，也对。

3.2 上右下左四条边的偏移量怎么加

知道起始值后，剩下的事就是计算 (i,j) 在它所在圈上走了多少步，答案等于 start 加上这个偏移量。以第 k 圈左上角 (k,k) 为起点，顺时针走，整圈被切成四段：

上边：条件是 i == k。从起点 (k,k) 向右走到 (k,j)，走了 j-k 步，值 = start + (j-k)。

右边：条件是 j == n-k+1。走完上边需要 m-1 步，再从上边往下走到 (i, n-k+1)，又走了 i-k 步，值 = start + (m-1) + (i-k)。

下边：条件是 i == n-k+1。此时上边和右边都已经走完，共 2×(m-1) 步，然后从右下角往左走 n-k+1-j 步，值 = start + 2×(m-1) + (n-k+1-j)。

左边：条件是 j == k，且点不在最下面一行（否则会被下边分支命中）。走完三条边一共 3×(m-1) 步，再从左下角往上走 n-k+1-i 步，值 = start + 3×(m-1) + (n-k+1-i)。

判断顺序固定为"先上边、再右边、再下边、最后左边"，这是有讲究的。四个角上的点同时满足两条边的条件，比如左上角 (k,k) 既满足 i==k 也满足 j==k，按这个顺序判断，角会归入它遇到的第一条边，不会重复也算不错位。你要是把左边的判断放前面，四个角的答案全部会乱，而且小样本还不一定能测出来。

3.3 完整公式速查表

把上面所有公式收拢成一张表，写代码时直接对照：

其中 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}) 是 C++11 的 initializer_list 写法，老编译器就老老实实嵌套四层 min。第三，最后那个 else 不需要再判断 j==k，因为走到 else 时，点既不在上边、右边、下边，那必然在左边。

4.2 官方样例加上四个角，逐一手算核对

还是用那张 4×4 的矩阵，验证官方两个样例。

输入 4 2 3：k = min(2,3,3,2) = 2，start = 13，m = 2。先判断 i==k，2==2 成立，ans = 13 + (3-2) = 14。矩阵里 (2,3) 位置确实是 14，通过。

输入 4 3 2：k = min(3,2,2,2) = 2，start = 13，m = 2。i==k 不成立；j==n-k+1 即 2==3 不成立；i==n-k+1 即 3==3 成立，进入下边分支，ans = 13 + 2×(2-1) + (4-2+1-2) = 13+2+1 = 16。矩阵里 (3,2) 确实是 16，通过。

再补测四个角。n=4 时 (1,4)：k=1，start=1，m=4，i==k 成立，ans = 1+(4-1)=4，正确；(4,4)：k=1，i==k 不成立，j==4 成立走右边，ans = 1+(4-1)+(4-1)=7，正确；(4,1)：依次判断后落到下边分支，ans = 1+2×3+(4-1+1-1)=10，正确。实际矩阵里右上角是 4、右下角是 7、左下角是 10，全中。

4.3 n=1 和 n=2 的极端情况也别放过

n=1 时矩阵只有一个格子，答案必然是 1。套公式：k = min(1,1,1,1)=1，start=4×0×(1+1-1)+1=1，m=1。i==k 成立，ans = 1+(1-1)=1，稳。

n=2 时矩阵是：

1 2 4 3

随便取一个容易被坑的坐标 (2,1)：k = min(2,1,1,2)=1，start=1，m=2。i==k 不成立，j==n-k+1 即 1==2 不成立，i==n-k+1 即 2==2 成立，ans = 1+2×(2-1)+(2-1+1-1)=1+2+1=4，正确。

特别留意 m=1 的场景，此时 m-1=0，2×(m-1)、3×(m-1) 都是 0，不会产生负数偏移。但前提是分支顺序正确：n=1 时点只可能落进上边分支，不会跑到后面。所以代码里用 if-else 链而不是四个独立 if，这个顺序保护是必须的。

5. 常见问题与排查技巧实录

5.1 样例全过却 WA：先检查圈号公式和分支顺序

最常见的翻车点就是圈号写错。有人写成 k = min(i, j, n-i, n-j)，这在很多点上会差 1。比如 n=4 的 (4,4)，正确 k=1，错误算出来 min(4,4,0,0)=0，直接变成"第 0 圈"，后面的 m 和 start 全部乱套。记住：1 索引坐标的下边距和右边距是 n-i、n-j，但要换算成从 1 开始的圈号，必须用 n+1-i、n+1-j，这样第一圈的边界 1 和 n 才是对称的。

更隐蔽的问题是分支顺序。如果把"左边"判断放在"下边"前面，左下角 (n-k+1, k) 会被错误归入左边分支，因为它的 j 就是 k，但它属于下边那段路。我见过有人用四个独立 if 写，导致角被算两次或者被错误分支带走。建议死守"上→右→下→左"的 if-else 链，这和顺时针方向一一对应，逻辑上最顺。

5.2 大数据超时：是不是还在老老实实转圈

如果你发现 n=100 能过、n=30000 超时，基本可以断定你在填整个矩阵。模拟填表的复杂度是 O(n²)，n=30000 时就是九亿次操作，哪怕每次操作只有几行代码，也远超 1 秒限制。反过来，如果用本文的 O(1) 算法还超时，那就查查读入输出：是不是用了 endl 而不是 '\n'，endl 会强制刷新缓冲区，在输出量大时拖慢程序。这道题单次查询，正解代码运行时间应该在毫秒级。

5.3 溢出和类型选择的细节

n 最大 30000 时，n²=9×10⁸，答案本身没超过 int 上限 2.1×10⁹，所以很多题解用 int 也能过。但注意 start 的计算式里有 4×(k-1)×(n+1-k)，k 取中间值约 15000 时，乘积大约是 4×15000×15000=9×10⁸，也没超 int。真正危险的是你如果临时改公式、或者写了个等价变形，中间某个因子可能悄悄超界。竞赛里最省心的做法就是干脆声明 long long，几行代码的代价，换一晚上不焦虑。

5.4 一个自查技巧：局部手算对照

我常用的自查方法：算完答案先别急着交，把目标点附近几个已知点一起算一遍。比如 n=5 时，第一圈起始 1，第二圈起始 17，第二圈上边的数应该是 17、18、19、20、21。你算 (2,3) 时如果得到 18，说明上边分支的偏移方向对了；如果得到 20，那很可能是把 j-k 写成了 n-k+1-j 之类，方向反了。这种"局部手算对照法"能秒杀公式里的符号错误，比反复提交试错快得多。

6. 从这道题看竞赛思维的养成

6.1 普及组第三题真正考的是观察力

NOIP 2014 普及组的 T1、T2 是比较直接的模拟和简单枚举，到了 T3 突然上强度，目的就是把"只会写循环"和"会观察规律"的学生区分开。螺旋矩阵这题，只要你愿意在草稿纸上画一个 5×5 的矩阵，把每圈的起始数标出来（n=5 时是 1、17、25），很快就能发现"起始数是外层周长累加"的规律。竞赛里相当一部分题都是这样：暴力解法一眼可见，优化方案藏在数据结构与数学结构里，就看你能不能从数据范围里读出警告信号。

6.2 同款思维能迁移到哪些题

"按需计算、避免整体构造"的思路，在任何涉及大规模枚举的题目里都用得上。比如 P2831（NOIP 2016 提高组 愤怒的小鸟），暴力枚举所有抛物线组合是阶乘级爆炸，正解用状态压缩把枚举降到 O(2ⁿ·n)，第一步同样是质疑"全枚举是否可行"。再比如 25 年 CSP-J 普及组的"座位"类问题，很多也是在考察你能不能把看似需要模拟全局的规则，压缩成几个关键变量直接推算。它们的共同套路是：先看数据范围，再评估模拟可行性，不可行就找递推、找公式、找状态压缩。

6.3 我的实操体会与刷题建议

我第一次做这题时，也写过两百行的方向模拟，调了半天只拿 40 分，小 n 全过、大数据超时。后来静下心画图，十分钟就推出了圈号公式。这个经历让我养成了一个习惯：见到矩阵、棋盘、排座位这类题，先问自己三个问题——数据范围允许整体构造吗？问题要的是全局信息还是单个点？规律能不能用数学式子表达？

如果你正在备战 CSP-J/NOIP 普及组，建议把这类"结构题"单独建一个错题本。螺旋矩阵之外，还有蛇形矩阵、旋转矩阵、锯齿遍历等变体，核心都是坐标系变换和边界控制。每做一道，就手写一遍小规模样例的推导过程，坚持十几道，你对"看到数据范围就条件反射地评估算法"会变得非常敏感。

最后分享一个小习惯：我复盘这题时，会把 n 从 1 到 6 的螺旋矩阵全部手画一遍，然后随机取坐标，用公式和手画结果对照。这个方法帮我抓出过不止一次边界分支写反的问题。希望你做完这道题，也能体会到"公式比模拟更接近问题的本质"这种乐趣。