前阵子带学员做 GESP 二级的模拟训练碰到一道很有意思的题给定一个 N×N 的方格表从外圈到内圈逐层“包起来”编号小的圈层在最外面要求快速判断某个坐标落在第几层或者计算某一层有多少个格子。题目里管这种圈层叫“黄金格”。说实话第一眼看到名字我以为要考黄金比例后来才反应过来考的就是最经典的“矩阵分圈”思路。这篇文章就把这道题的完整拆解、从暴力到 O(1) 的推导过程、C 实现以及考场上的易错点一次讲清楚适合正在准备 GESP 二级、或者刚学完二维数组想练模拟题的同学。1. 题目定位黄金格到底在考什么1.1 名字很花哨内核很朴素“黄金格”听起来像是某种几何美学题实际上它考察的是二维数组里非常基础的一种能力按圈层理解矩阵结构。你不需要求出什么比例、什么最美分割点只需要把 N×N 的方格想成一个“洋葱”从外往里一层一层剥开每一层就是一个“黄金格”。我上课的时候习惯让学生先画图。拿一张方格纸N5先把最外圈描粗这就是第 1 层再把剩下 3×3 的外圈描粗这就是第 2 层最后剩下中间 1 个格子就是第 3 层。画完图之后题目基本就解决了一半。很多同学看到“层”这个概念就发怵其实把它还原成“一圈一圈的格子集合”就好懂了这就是典型的模拟思维。1.2 与 GESP 二级考纲的对位GESP 二级在 C 这条线里核心语法考察范围大致是顺序结构、分支结构、循环结构、一维数组以及最基本的二维数组读写。黄金格这题如果出成编程题通常会落在“二维数组循环模拟”这个区间里但它有个更阴险的考法不让你真的开一个 N×N 数组去填而是让你通过公式直接算答案。因为 N 可能很大开二维数组会直接内存超限。所以说白了这题就是考察你能不能把一个具体的“填格子”过程抽象成数学模型。这也是 GESP 二级往后走向三级、四级时最需要的能力——不是每个题目都允许你傻乎乎地模拟到底。判断一个选手是“会用 for 循环”还是“理解了 for 循环的本质”看他对这类题的处理方式就知道了。1.3 典型的输入输出长什么样我没有拿到原题的完整数据范围但按同类题目的常见设计题目一般会给两种问法输入 N再输入一个坐标 (r, c)输出该坐标所在圈层的编号。输入 N再输入一个圈层编号 k输出第 k 层总共包含多少个格子。第一种问法考“坐标到层数的映射”第二种问法考“层数到数量的映射”。如果你能把这两种问法都吃透考试时不管它怎么换皮你都能认出来。下面我从数学模型开始一步步展开。2. 核心算法设计从圈层到公式2.1 建立统一的圈层模型先做约定行号、列号都从 1 开始计数。N×N 的矩阵中第 1 层就是最外面的那一圈第 2 层是去掉第 1 层后剩下的 (N−2)×(N−2) 矩阵的最外圈以此类推。这里有个很关键的点每一层都是一个“空心方框”。比如 N5 时第 1 层5×5 的外圈横着 5 个、竖着 5 个但因为四个角各被算了两次实际格子数是 5×4−4 16。第 2 层3×3 的外圈实际格子数是 3×4−4 8。第 3 层1×1就中间一个格子格子数是 1。第 3 层是个特例。如果继续套用“边长为 1 的方框”公式会得到 1×4−4 0这显然是错的。所以处理圈层问题时必须单独考虑“中心点到底算不算一层”的边界情况。2.2 第 k 层格子数的公式推导假设当前层的“边长”为 side意思是这一层所在方块每边有 side 个格子。第 k 层时前面已经剥掉了 k−1 层上下左右各少了 k−1 个格子所以side N − 2 × (k − 1)当 side ≥ 2 时这一层是一个空心方框格子数count 4 × side − 4展开一下就是count 4N − 8k 8 − 4 4N − 8k 4当 side 1 时也就是 N 为奇数且剥到了正中心格子数就是 1。我来验证几个数。N4 时k1side4count 4×4−4 12。k2side2count 4×2−4 4。12 4 16刚好等于 N² 16说明没有漏格子。N5 时k1side5count 4×5−4 16。k2side3count 4×3−4 8。k3side1count 1。16 8 1 25还是等于 N²。这个“总和等于 N²”的验证方法特别实用你自己写完公式后可以随手验一下能挡住一半以上的低级推导错误。2.3 坐标映射到圈层的快速算式反过来给定一个坐标 (r, c)它在第几层直观理解一个格子所在的层号取决于它离四条边分别有多远。离上边越近层号越靠外离下边越近层号也越靠外。最终的层号其实就是layer min(r, c, N − r 1, N − c 1)四个值分别是到上边的距离用行号表示、到左边的距离用列号表示、到下边的距离、到右边的距离。取最小值就是剥到这个格子之前至少要剥掉几层。举个例子。N5(3,3) 这个点min(3, 3, 3, 3) 3它确实在正中间也就是第 3 层。再看 (2,4)min(2, 4, 4, 2) 2我们验证一下5×5 矩阵去掉第 1 层后剩下的 3×3 矩阵范围是行 2 到 4、列 2 到 4点 (2,4) 在那个 3×3 矩阵的右上角属于第 2 层的外框所以答案是 2没毛病。这里有一个很容易绕晕的细节如果坐标用的是 0 起始下标从 0 开始数那么公式要相应改成layer min(r0, c0, N − 1 − r0, N − 1 − c0) 1因为从 0 开始的坐标离下边的距离不能直接写 N−r0而是 N−1−r0。考场上一旦行列起始编号看错公式全盘皆输。我在下面第三章会给完整的参考代码你直接用 0 起始和 1 起始各写一遍自己感受一下差别。2.4 为什么要先推公式而不是直接开数组模拟很多同学拿到这题的第一反应是开一个 N×N 的二维数组然后一层一层地填编号最后直接查数组。这个思路在 N 很小的时候完全没问题甚至更直观。但要注意如果 N 给到 10⁵ 甚至 10⁶开二维数组在内存上就爆了10⁵ × 10⁵ 个 int 需要 40GB 内存显然不可能。即便 N 没这么大暴力模拟在时间复杂度上也不划算。每一层都要走四条边总共需要 O(N²) 的时间。而公式法里计算某一层格子数、计算某个坐标的层号都是 O(1) 的。差距在 N 比较大的时候是碾压级的。我并不是说暴力模拟没有价值。实际上在正式推公式之前用暴力方法写一个“对照程序”拿小数据验证公式是否正确是特别好的工程习惯。你先写暴力再写公式对拍一下如果结果一致再交上去就很稳了。这比坐在那里反复验算快得多也可靠得多。3. C 实操从暴力验证到最优解法3.1 第一步写好暴力程序当“标尺”先用最直白的方式把方案写出来目的是拿到正确的基准答案。这里我用一个二维数组从外到内逐层填编号#include bits/stdc.h using namespace std; int main() { int N; cin N; vectorvectorint grid(N, vectorint(N, 0)); int layer 1; int top 0, bottom N - 1, left 0, right N - 1; while (top bottom left right) { for (int j left; j right; j) { grid[top][j] layer; } for (int i top 1; i bottom; i) { grid[i][right] layer; } if (top bottom) { for (int j right - 1; j left; --j) { grid[bottom][j] layer; } } if (left right) { for (int i bottom - 1; i top; --i) { grid[i][left] layer; } } layer; top; --bottom; left; --right; } int r, c; cin r c; cout grid[r - 1][c - 1] \n; return 0; }这个程序里有一个特别容易漏的判断if (top bottom)和if (left right)。不加这两个判断当只剩一行或一列时下面的循环会重复填格子导致编号被覆盖。我见过很多学员在 N5、N6 的时候都能跑对一到 N1 或者 N2 就崩原因就在这里。暴力程序写好后你就可以用它来“对拍”后面的最优解法了。3.2 第二步写基于公式的最优程序坐标映射到层号核心代码非常短#include bits/stdc.h using namespace std; int min4(int a, int b, int c, int d) { return min(min(a, b), min(c, d)); } int main() { int N, r, c; cin N r c; int layer min4(r, c, N - r 1, N - c 1); cout layer \n; return 0; }如果是计算第 k 层的格子数#include bits/stdc.h using namespace std; long long layerCount(long long N, long long k) { long long side N - 2 * (k - 1); if (side 1) return 1; return 4 * side - 4; } int main() { long long N, k; cin N k; cout layerCount(N, k) \n; return 0; }注意我在这里使用了long long。为什么因为 N 一旦超过 10⁵4×side−4 这个中间结果很容易超过 int 的上限。假如 N10⁹4×N−4 大概是 4×10⁹已经超过 int 的 21 亿上限了。GESP 二级虽然未必考这么大的数据但从一开始就养成选对数据类型的习惯后面学算法会省很多事。3.3 第三步用数理验证代替全量对拍如果理论上已经确定公式正确其实不需要跑全量对拍。我通常只做三类验证验证总数。对任意 N所有层的格子数之和必须等于 N²。把 N1、N2、N3、N4、N5 各试一遍写个循环累加一下能很快发现公式是否漏了中心点。验证对称点。比如 N7(1,1)、(1,7)、(7,1)、(7,7) 这四角都应该在第 1 层(3,3)、(3,5)、(5,3)、(5,5) 都应该在第 3 层。验证中心点。N 为奇数时中心点一定在第 (N1)/2 层且该层格子数为 1。N 为偶数时最内层是一个 2×2 的方框格子数为 4。这三类验证全部通过公式基本就稳了。3.4 变式一给定层号和序号求格子坐标真题不一定只考“层号”和“格子数”还可能反向考察。比如给定 N、层号 k以及这一层中按顺时针方向从左上角开始的序号 p求这个格子的坐标。这种题就是“坐标映射到层号”的逆运算考察的还是同一条知识线。完整实现如下#include bits/stdc.h using namespace std; int main() { long long N, k, p; cin N k p; long long side N - 2 * (k - 1); long long total (side 1) ? 1 : 4 * side - 4; if (p 1 || p total) { cout invalid\n; return 0; } if (side 1) { cout k k \n; return 0; } p--; // 转为 0-based long long r, c; if (p side) { r k, c k p; } else if (p 2 * side - 1) { long long q p - side 1; r k q, c k side - 1; } else if (p 3 * side - 2) { long long q p - (2 * side - 1) 1; r k side - 1, c k side - 1 - q; } else { long long q p - (3 * side - 2) 1; r k side - 1 - q, c k; } cout r c \n; return 0; }这个代码的思路是把一圈拆成四条边上边从左到右共 side 个右边从上到下共 side−1 个下边从右到左共 side−1 个左边从下到上共 side−1 个。把序号 p 映射到某条边上的偏移量 q就能算出坐标。考试中一旦出现这种“反向输出坐标”的问法很多同学会当场卡住但只要你理解了圈层模型它就是一道简单分段函数题。我建议你把“坐标求层号”和“层号序号求坐标”这两题放在一起练它们就像一对镜像题。能把它们同时弄明白说明你对二维矩阵的圈层结构是真的理解了而不是只背了一套模板。4. 考场易错点与调试技巧4.1 五个最常见的翻车现场我统计了一下平时课堂练习里学生们在这类题目上的报错情况基本集中在下面五类错误类型典型表现原因解决办法行列起始理解错输出结果总差 1题目说从 1 开始代码按 0 处理读题时先把“起始编号”圈出来代码里统一加 1 或减 1中心点漏判N 为奇数时答案少算side1 还套用“方框公式”判断side 1直接返回 1数据类型溢出大 N 时答案变成负数int 存不下 4N−4换成 long long四角格子重复计数输出格子数偏大模拟填数时四条边都走完整条四条边分别处理时边界要留好只走角上一次坐标越界没判断程序崩或直接 RE读取 p 后没检查范围加 if (p 1前三个问题是最常见的。特别是第二个中心点问题哪怕你公式推导得再顺忘记处理 side1 也会功亏一篑。我上课时反复跟学生说写圈层相关代码第一行就要想清楚“这一层是不是只剩一个点了”。4.2 一秒钟定位 bug 的调试方法如果你写的代码输出不对先别急着从头读代码。我调试这类题有一个固定顺序先拿 N1、N2、N3 这三个最小数据跑一遍。 N1 是最容易暴露中心点问题的因为整个矩阵就一个格子它是第 1 层同时也最内层。如果这都能错说明边界处理没写好。再看四角坐标。(1,1)、(1,N)、(N,1)、(N,N) 这四个点理论上一定都在第 1 层如果有一个不在说明公式里的 min 取错了。最后看中心坐标。N 为奇数时((N1)/2, (N1)/2) 必须在最内层N 为偶数时(N/2, N/2) 和 (N/21, N/21) 这些点必须落在第 N/2 层。这三板斧下来95% 的错误都能定位出来。剩下的 5%通常是对拍时数据范围不够大恰好绕过了某些边界。这时候就需要你主动构造一些“极端坐标”比如让 r1 或 c1让点贴着最左边或最上边最容易测出你公式里是不是少了个对称项。4.3 时间复杂度与内存开销分析暴力模拟填色方案的复杂度是 O(N²)因为每个格子都被填了一次。公式法的时间复杂度是 O(1)空间复杂度也是 O(1)。在 GESP 二级这个阶段出题人如果真想卡暴力通常会把 N 放到 10⁵ 甚至更大。这时候 O(N²) 是绝对过不去的。有的同学觉得“既然题目可能 N 不大我模拟也无妨”这种心态在考试时最危险。因为你不知道后台的测试点里是否有哪一组数据刚好把 N 拉满而那一组数据往往就决定了这道题你是拿满分还是拿零分。我带的学员里有个成绩不错的学生第一次做这道题时纯粹用暴力过了样例以为自己全对了。结果一交上去跑出来一堆 RE。后来我让他用公式法改一遍所有大数据直接通过。从那以后他养成了习惯只要涉及矩阵先想想能不能不建数组直接算。4.4 考场上更推荐哪种写法如果你的目标很明确就是 GESP 二级高分通过那么我建议你在考场上直接写公式法。理由有三代码短不容易出低级错误。不需要理会二维数组的越界问题。时间复杂度和空间复杂度都更优任何测试点都能应对。但前提是你真的理解了公式是怎么来的。如果只是背下min(r, c, N-r1, N-c1)遇到起始下标为 0 的变体还是会翻车。所以我强烈建议考前练习时先写暴力再写公式再用暴力去验证公式。这个过程走一遍比写十道同类题都管用。5. 从二级“黄金格”到更高级别的进阶思路5.1 为什么这个模型值得认真学“黄金格”这种圈层模型并不是 GESP 二级专属的考点它在更高级别里会以各种面貌出现。比如 GESP 七级、八级经常出现的矩阵旋转、蛇形填数、螺旋矩阵、以及各类棋盘类递归问题本质上都和“按圈层组织数据”有关。你可能觉得 O(1) 算层号这个技巧太简单高级别考试用不上。其实不然。在一些要求高效的算法里你需要快速定位一个坐标在什么层、这一层的边界是什么才能决定下一步在哪个子矩阵上递归。比如在二维平面上做分治、做搜索剪枝黄金格的“层层递进”思想都是基础中的基础。5.2 二级到七级八级的能力成长路径我带学生走的路子大致是这样的二级阶段把“黄金格”这类模拟题吃得透透的知道什么时候该建数组什么时候该直接套公式。三四级阶段开始学递归和排序圈层模型会出现在更复杂的递归题里比如汉诺塔变体、矩阵划分。五级六级阶段接触贪心和动态规划常常需要你从矩阵的局部信息推全局答案。七级八级阶段字符串、树、图的高级算法铺开但很多问题的初始化、边界处理仍然离不开最朴素的“能不能直接算出某个位置”的敏感度。很多家长问我GESP 二级到七级八级要多久。我的回答是进度不是最关键的关键是每个阶段的核心模型有没有真正扎实。像“黄金格”这样的题它本身不难但它是检验一个人有没有“建模意识”的试金石。有没有建模意识决定了你在算法这条路上能走多远。5.3 如果要给孩子报课应该重点关注什么最近“gesp c课程”这个词热度不低很多家长在给孩子选课。我个人选课的标准很简单课程有没有强调“先分析再动手”。如果一门课从头到尾只教学生记模板、背代码那么遇到“黄金格”这种名字变来变去、数据范围变来变去的题孩子大概率还是会懵。反之如果课程会带着学生画方格图、推公式、用暴力验证结论那这门课的下限一般都低不到哪里去。我这里说的“画图”不是一句空话。我自己的习惯是拿到任何矩阵题第一步先在草稿纸上画一个 5×5 的格子把第 1 层、第 2 层、第 3 层分别标出来。很多时候图画完之后解题思路自己就冒出来了。5.4 一个让我印象深刻的学员反馈我之前有个学员小周备考 GESP 二级的时候连续做了三道圈层类题目每次都是暴力模拟代码写得又长又容易错。直到第四道题N 给得特别大他的暴力程序直接超时。他跑来问我我说你画个图把每一层的格子数列出来看看有没有规律。他画了五分钟跑过来特别兴奋地说这不就是每层边长减 2格子数乘 4 减 4 吗。从那之后他再做同类型题基本都是先停三秒想一想能不能推公式。那次 GESP 二级考试他出来跟我说看到“黄金格”三个字的时候心里就踏实了因为考前刚做过一模一样的模型。这就是我想强调的考试考的不是你见过多少题而是你手里有没有几条能解决一类题的通路。6. 最后的一点体会带学生备考这么多次我最大的感受是像“黄金格”这种题其实是在帮你检查自己有没有建立“从具象到抽象”的能力。一个小方格一层层剥开画在纸上就是几圈方框写在程序里就变成了min和4 * side - 4。能从前者看到后者你就掌握了这一类题的灵魂。如果你现在正在备考建议不要急着背答案。拿张方格纸把 N5、N6 的每层格子数量亲手算一遍再把公式推一遍最后用代码实现一遍自己当自己的出题人换着法子提问自己。这个过程走完别说“黄金格”了再来了“白银格”“钻石格”你都不会慌。