公式)
前阵子刷 UVa 12573 Sohel Sir‘s Assignment这道题让我在同一个坑里摔了两次第一次老老实实写 BFS小数据全对数据一大直接超时第二次推完公式兴冲冲交上去又因为漏掉 N1 的特判被 WA 到怀疑人生。题目描述很短但里面藏了三个容易忽略的细节。这篇文章把完整思路、公式推导和踩坑记录都整理出来给同样在做 UVa 或者刷组合计数题的朋友做个参考。1. 题目到底在问什么六个方向、恰好 N 步、去重计数1.1 题意拆解题目的大意是在平面直角坐标系中从原点出发每一步可以选择六个方向之一移动一个单位问走恰好 N 步之后能够到达多少个不同的格子点。听起来很简单但你先别急着写 BFS。这里有三个关键词会决定你最终答案对不对。第一个是“六个方向”。普通网格题是上下左右四个方向这道题多了两个对角方向也就是我们可以走水平两个方向(1, 0)、(-1, 0)垂直两个方向(0, 1)、(0, -1)两条对角线方向(1, -1)、(-1, 1)注意对角线不是 (1, 1) 这种而是斜着穿过方格的对角步。把六个方向画在坐标系里刚好是正六边形的六个顶点方向。也就是说这个网格实质上是一个三角格点图不是普通的方形网格。这一点理解错了后面推公式会全部跑偏。第二个关键词是“恰好 N 步”。不是“最多 N 步”而是路径长度必须精确等于 N。多绕路可以少走不行。也就是说哪怕某个点距离原点只有 1 步只要你能用 N 步走到它它也要被计入答案。这一点直接导致了 N1 时会出现一个非常反直觉的特例后面我会专门讲。第三个关键词是“不同的格子点”。同一个点完全可能被多条路径走到比如先向右再向左就回到原点但统计答案时只算一次。所以不能用简单的路径计数去套要做的是集合大小的统计。这道题在 UVa 里属于较新的题目数据范围我记得可以给到很大所以暴力搜索一定不是正解。你需要找到答案的数学规律把 O(6^N) 的爆炸搜索压缩成 O(1) 的公式输出。1.2 为什么不能直接 DFS很多同学看到“六个方向、N 步、有多少个点”的第一反应就是 DFS 或 BFS。我一开始也是这么干的用一个 set 存当前所有可达点每一层把每个点往六个方向扩展一遍最后数 set 里的点数。这种思路在小数据下完全没问题。N1 答案是 6N2 答案是 19N3 答案是 37轻轻松松。但只要 N 到 20 左右你可以自己去试一下每一层能到达的点数按二次方增长虽然比 6^N 小得多但 set 操作加上逐层扩展时间还扛得住可一旦 N 到 100、1000甚至 10^9暴力就直接死掉了。更要命的是 UVa 这类在线判题系统一般会给你多组测试数据。如果每组都要重新 BFS那就算 N 只有几百累积起来也会超时。所以这道题真正考的是推导能力先在小范围打表找规律再想办法证明规律最后用公式输出。1.3 方向集合的坐标写法为了方便讨论先把六个方向写成六组向量方向向量右(1, 0)左(-1, 0)上(0, 1)下(0, -1)右下对角线(1, -1)左上对角线(-1, 1)这六个向量在二维平面上形成一个闭合的对称结构。注意 (1, -1) 和 (-1, 1) 互为相反向量另外两组也是。所以本质上你手里相当于握住了三个轴方向的“正负步”只是这三个轴不是互相垂直的但组合起来同样能张成整个平面。观察六个方向可以发现一个关键事实沿某个方向走一步再去掉沿另一个方向走一步可能等效于某个单步方向。比如先 (0,1) 再 (1,-1)合计是 (1,0)也就是向右一步。这意味着同一个终点会有非常多的路径表示所以去重是必须的也正因为这种冗余才让“恰好 N 步”变得大多数情况下都能实现。2. 先别急着推公式打表把规律“看”出来2.1 用 BFS 打小数据的表我不建议一上来就闷头推导因为在没有结论的时候你根本不知道要证什么。正确做法是先用暴力程序把 N0 到 N8 的答案全部算出来盯着数字看几分钟。打表代码非常简单。用 set 存点用坐标结构体判重。我写了一个 C 版本的 BFS#include bits/stdc.h using namespace std; struct Point { int x, y; bool operator(const Point other) const { if (x ! other.x) return x other.x; return y other.y; } }; int main() { int dx[6] {1, -1, 0, 0, 1, -1}; int dy[6] {0, 0, 1, -1, -1, 1}; for (int N 0; N 8; N) { setPoint cur, nxt; cur.insert({0, 0}); for (int step 0; step N; step) { nxt.clear(); for (auto p : cur) { for (int k 0; k 6; k) { nxt.insert({p.x dx[k], p.y dy[k]}); } } cur nxt; } cout N N - cur.size() \n; } return 0; }这里每循环一次 step 就相当于走了一步cur 里存的是当前步数下所有可达点。因为 set 会自动去重所以最后 cur.size() 就是答案。我跑出来的结果如下。2.2 观察到的序列N可达格点数0116219337461591612771698217看到 1、6、19、37、61、91、127 之后我第一反应是查差分。6 - 1 519 - 6 1337 - 19 1861 - 37 2491 - 61 30127 - 91 36从 N2 开始差分是 18、24、30、36每次增加 6。也就是说从 N2 往后相邻两项之差是 6(N1)或者说约等于 6 的倍数递增。二次差分恒定是 6这强烈暗示答案是一个关于 N 的二次函数。再对比一个经典数列中心六边形数 1, 7, 19, 37, 61, 91, 127。除了 N1 那一项差了 1后面的 19、37、61、91、127 完全对上了。中心六边形数的通项是 1 3N(N1)也就是 3N^2 3N 1。打表结果已经给了很明显的信息这道题的答案大概率就是 3N^2 3N 1只不过当 N1 时需要特殊处理因为数列里 1 对应的不是 7而是 6。2.3 差分和公式如何对应如果你手边有计算器把 3N^2 3N 1 验证一下N212 6 1 19N327 9 1 37N448 12 1 61而相邻两项差的公式是(3(N1)^2 3(N1) 1) - (3N^2 3N 1) 6N 6 6(N1)这正好解释了打表里 N2 往后差分是 18、24、30、36 的规律。差分等于 6 的倍数意味着图形上每一圈新增的格点数量是线性增加的这跟“六边形按圈向外扩展”的直觉完全吻合。打表找规律的套路在这道题上体现得淋漓尽致你不需要一开始就知道什么高深理论只需要把前几项算出来然后观察差分、二阶差分或者和已知数列比对。一旦发现二次差分恒定就可以放心大胆地假设通项是二次函数。3. 为什么答案是中心六边形数几何解释与证明思路3.1 三角格点与六边形圈如果你把六个方向画成一个图会发现所有可达点在平面上排布成一个六边形形状的网格这正是三角格点图。从原点出发走 0 步是圆心 1 个点走 1 步以内能到的点是围绕圆心的一圈 6 个点走 2 步以内能到的点又向外扩展一圈新增 12 个点走 3 步以内能到的点新增 18 个点。这里有一个关键观察每一步最多让“到原点的某种距离”增加 1而这个距离在三角格点上刚好可以用“六边形圈数”来衡量。走 N 步以内能到达的所有点恰好是以原点为中心、半径为 N 的六边形内部及边界的全部格点。那么这个六边形内到底有多少个点很简单一圈一圈数第 0 圈圆心1 个点第 1 圈6 个点第 2 圈12 个点第 3 圈18 个点...第 k 圈6k 个点所以走 N 步以内能到达的格点总数是1 6 12 18 ... 6N 1 6 * (1 2 ... N) 1 3N(N1)展开就是 3N^2 3N 1。你可能已经发现了这个式子还有一个非常漂亮的等价形式3N^2 3N 1 (N1)^3 - N^3它就是相邻两个立方数的差。这不是巧合而是中心六边形数和立方数之间的经典关系。所以在代码里你既可以写 3LL * N * N 3LL * N 1也可以写 (N1)^3 - N^3。就编程而言前者更直接不会因为乘方溢出出问题。3.2 为什么 N2 时“恰好 N 步”能覆盖全部点上面数的是“N 步以内”能到达的点但题目问的是“恰好 N 步”能到达的点。这里需要论证一件事对任意一个距离原点不超过 N 的格点都一定存在一条长度恰好为 N 的路径走到它。先看原点本身。N2 时可以先走 (1,0) 再走 (-1,0) 回原点N3 时可以走 (1,0)、(-1,1)、(0,-1)三个向量加起来是 (0,0)。所以只要 N2原点都能被恰好走到。再看距离原点 1 步的那些点比如 (1,0)。N2 时可以走 (0,1) (1,-1)合计就是 (1,0)N3 时也能走因为可以先用两步到达 (1,0)再绕一个三角形环回到原位。所以距离 1 的点在 N2 时也都能被恰好走到。那么距离更远的点呢假设某个点最短需要 L 步到达其中 LN。你需要把步数从 L 补到 N。怎么补有两个基本“绕路”手段两步往返走一个方向再走它的反方向合计 2 步位置不变比如 (1,0) (-1,0)。三步三角环走三条方向向量合计为 03 步回到原点比如 (1,0) (-1,1) (0,-1)。由于 2 和 3 可以组合出任何不小于 2 的整数差值除了 1所以只要 N-L 不等于 1补步数都能实现。唯一需要担心的是 N-L1 的情况也就是路径长度只比最短距离多 1。这时候因为 3 步三角环和 2 步往返都加不进去看起来会出问题。但实际分析会发现对于 L1 的任意点都可以直接用一条长度为 L1 的折线走到它因为三角形的存在让“走一步之后再绕个小弯”变得非常容易。所以真正无法处理的情况只有 L0 且 N1也就是原点只用一步回不去。因此结论就是N0 时答案是 1N1 时答案是 6N2 时答案等于中心六边形数 3N^2 3N 1。这是一个很典型的“先数后证”路径先用几何直观告诉你总点数是多少再用三角格点上的绕路性质说明这些点都能被刚好覆盖到。日常做题时你不需要把证明写得像论文那么严格但至少要能说服自己。3.3 N1 这个特例是怎么来的为什么打表结果里 N1 是 6而不是公式给的 7因为公式 13N(N1) 算的是“距离原点不超过 N 的所有格点”其中包含原点。当 N1 时这个集合是原点加周围 6 个点共 7 个。但“恰好 1 步”从原点出发不可能留在原点一步走出去位置就变了所以原点必须从答案中去掉剩下 6 个。这个特例极其阴险。你从 N2 开始推规律得到 3N^23N1验证 N2、3、4 全对想当然地认为 N1 也适用结果提交上去 WA。标准的 UVa 题解里基本都有一行 if (n 1) 的特判原因就在这里。如果你的代码还能遇到 N0 的输入那就更要注意公式在 N0 时算出来是 1而 0 步只能待在原点答案恰好是 1所以 N0 用公式也正确。但很多题目给的约束是 N1这时候 N1 特判就足够了。4. 代码实现与边界处理4.1 C 主代码当你确定了公式和特判之后AC 代码非常短。这里我给出一个标准的 EOF 写法#include cstdio int main() { long long n; while (scanf(%lld, n) 1) { if (n 1) { printf(6\n); } else { printf(%lld\n, 3LL * n * n 3LL * n 1); } } return 0; }有几个点需要解释一下。第一为什么要用 long long因为 3N^2 这一项在 N 比较大时增长很快。假设 N 可以到 10^9那么 N^2 是 10^18 级别int 只有 32 位最大能表示约 2.1×10^9远远不够。long long 在绝大多数在线判题系统里是 64 位能扛住这个范围。我一开始用 int 交小数据没问题一旦题目里有大 N 的测试点就爆掉所以直接上 long long 是最稳妥的。第二为什么用 while (scanf(%lld, n) 1)因为 UVa 老题的风格一般是不给测试组数而是不断读入直到文件结束。如果你只读一组数据遇到多组输入就会漏算。有的题目第一行会先给 T那就改成先读 T 再循环 T 次但原题我记得是非 EOF 莫属所以采用这个写法。第三特判 n 1 一定要放在公式之前。因为 n1 时代入公式得到 7答案是 6差的是原点。如果题目给的 N 可能是 0你要不要特判不需要因为公式在 N0 时算出的结果是 1和实际一致。4.2 Python 的实现与快速验证如果你平时用 Python 刷题或者想迅速验证小数据代码更简洁import sys for line in sys.stdin: line line.strip() if not line: continue n int(line) if n 1: print(6) else: print(3 * n * n 3 * n 1)Python 的整数没有溢出问题所以直接算就行。但要注意输入里可能混有空行所以 strip 之后跳过空行是个好习惯。我还建议你把 BFS 打表代码和这段公式代码放在一起写一个对拍程序。随便生成几个小 N对比 BFS 结果和公式结果一旦发现不一致立刻定位。这种对拍习惯在算法竞赛里非常有用能够避免你把一个错误的规律当成真理直接提交。4.3 时间复杂度与空间复杂度公式解的时间复杂度是每组数据 O(1)空间复杂度是 O(1)。不管 N 有多大不管有多少组数据每个测试点都是常数时间。相比 BFS 的状态爆量这完全是降维打击。在线判题最讨厌的就是超时和超内存。超时可以通过推公式解决超内存则直接不会出现在这道题里。你只需要小心输入输出别太慢。C 里如果用了 cin/cout建议加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr)或者干脆用 scanf/printf这样在大数据量下会稳很多。5. 常见问题与排查技巧实录5.1 WA 的经典原因汇总我在群里见过好几个同学卡在这道题总结下来基本就是下面几个原因。第一个就是漏掉 N1 特判。这也是最常见的错误。如果你提交后 WA但你已经推导出公式优先检查是不是这个问题。直接把 n1 特判加上十有八九就过了。第二个是 int 溢出。很多同学看完题意觉得 N 最大可能也就几万直接用 int 写结果题目隐藏数据里冒出个大 NWA 或者报运行时错误。建议所有涉及平方的中间结果一律用 long long。第三个是读入方式不对。题目如果有多组数据你却只用 scanf 读了一次那程序只会处理第一个测试点后面的全部忽略自然 WA。处理 EOF 是 UVa 的老传统养成 while (scanf(...) 1) 的习惯能帮你少踩很多坑。第四个是方向集合写错。虽然你没有用 BFS 做最终代码但如果打表阶段方向就写错了你观察到的规律就是错的。六个方向里最容易漏的是 (1,-1) 和 (-1,1) 这对对角线或者误写成 (1,1)。一旦方向错打表数据就和正确题意不符后续推导全废。我整理成表格方便你对照排查错误类型现象解决办法漏特判 N1样例过了但隐藏数据 WA增加 if (n 1) 输出 6int 溢出N 较大时输出负数或错值使用 long long读入只处理一次多组数据只算第一组改为 while EOF方向向量写错打表规律不对核对 (1,-1)、(-1,1) 等六个方向公式记忆错误输出和打表对不上用 3N^23N1 或 (N1)^3-N^35.2 怎么快速自检公式给你一个笨但有效的方法写一个 15 行的暴力程序把 N0 到 N7 的答案全算出来然后写一个公式程序输出同样范围的答案两个程序的结果并排打印肉眼比对。我用的方向数组是这样的int dx[6] {1, -1, 0, 0, 1, -1}; int dy[6] {0, 0, 1, -1, -1, 1};注意这里的方向顺序无所谓只要六个方向齐全就行。我的顺序是右、左、上、下、右下、左上。你根据自己的习惯调整即可。对拍时重点看 N1暴力输出 6公式输出 7这时候你就知道特判必须加。其他 N 值两边应该完全一致。如果 N2 或 N3 就对不上那多半是方向写错或者公式算错。5.3 从这道题延伸出去的套路“打表找规律 - 差分判断 - 假设通项公式 - 特判边界 - O(1) 输出”这个流程在组合计数题里非常通用。UVa 和同类在线判题里有一批题都是这个套路核心就是让你从小数据里发现二次或线性规律。比如很多六边形棋盘、三角形网格计数题答案最后都是 3N^23N1 这种形式。你甚至可以记住一个规律如果差分序列是等差数列原数列就是二次函数如果二阶差分恒定通项一定是二次多项式。反过来如果差分序列是等比数列那就要往指数函数上想。另外(N1)^3 - N^3 这个形式值得单独记一下。它既可以是中心六边形数也对应着三维空间里立方体的增长量。在解题时如果发现答案和立方差有关大概率能找到几何解释。我个人做这道题的体会是不要轻视任何一道“看起来像搜索”的题。你花五分钟写个 BFS 打表可能帮你省下五个小时的无效推导而推公式的时候也一定要记得把 N 的每个小值都代入验证一遍尤其是 0 和 1因为边界永远是最容易出错的地方。以后遇到类似题目先暴力拿小数据再盯着数字多看一眼答案往往就自己跳出来了。
前阵子刷 UVa 12573 Sohel Sir‘s Assignment这道题让我在同一个坑里摔了两次第一次老老实实写 BFS小数据全对数据一大直接超时第二次推完公式兴冲冲交上去又因为漏掉 N1 的特判被 WA 到怀疑人生。题目描述很短但里面藏了三个容易忽略的细节。这篇文章把完整思路、公式推导和踩坑记录都整理出来给同样在做 UVa 或者刷组合计数题的朋友做个参考。1. 题目到底在问什么六个方向、恰好 N 步、去重计数1.1 题意拆解题目的大意是在平面直角坐标系中从原点出发每一步可以选择六个方向之一移动一个单位问走恰好 N 步之后能够到达多少个不同的格子点。听起来很简单但你先别急着写 BFS。这里有三个关键词会决定你最终答案对不对。第一个是“六个方向”。普通网格题是上下左右四个方向这道题多了两个对角方向也就是我们可以走水平两个方向(1, 0)、(-1, 0)垂直两个方向(0, 1)、(0, -1)两条对角线方向(1, -1)、(-1, 1)注意对角线不是 (1, 1) 这种而是斜着穿过方格的对角步。把六个方向画在坐标系里刚好是正六边形的六个顶点方向。也就是说这个网格实质上是一个三角格点图不是普通的方形网格。这一点理解错了后面推公式会全部跑偏。第二个关键词是“恰好 N 步”。不是“最多 N 步”而是路径长度必须精确等于 N。多绕路可以少走不行。也就是说哪怕某个点距离原点只有 1 步只要你能用 N 步走到它它也要被计入答案。这一点直接导致了 N1 时会出现一个非常反直觉的特例后面我会专门讲。第三个关键词是“不同的格子点”。同一个点完全可能被多条路径走到比如先向右再向左就回到原点但统计答案时只算一次。所以不能用简单的路径计数去套要做的是集合大小的统计。这道题在 UVa 里属于较新的题目数据范围我记得可以给到很大所以暴力搜索一定不是正解。你需要找到答案的数学规律把 O(6^N) 的爆炸搜索压缩成 O(1) 的公式输出。1.2 为什么不能直接 DFS很多同学看到“六个方向、N 步、有多少个点”的第一反应就是 DFS 或 BFS。我一开始也是这么干的用一个 set 存当前所有可达点每一层把每个点往六个方向扩展一遍最后数 set 里的点数。这种思路在小数据下完全没问题。N1 答案是 6N2 答案是 19N3 答案是 37轻轻松松。但只要 N 到 20 左右你可以自己去试一下每一层能到达的点数按二次方增长虽然比 6^N 小得多但 set 操作加上逐层扩展时间还扛得住可一旦 N 到 100、1000甚至 10^9暴力就直接死掉了。更要命的是 UVa 这类在线判题系统一般会给你多组测试数据。如果每组都要重新 BFS那就算 N 只有几百累积起来也会超时。所以这道题真正考的是推导能力先在小范围打表找规律再想办法证明规律最后用公式输出。1.3 方向集合的坐标写法为了方便讨论先把六个方向写成六组向量方向向量右(1, 0)左(-1, 0)上(0, 1)下(0, -1)右下对角线(1, -1)左上对角线(-1, 1)这六个向量在二维平面上形成一个闭合的对称结构。注意 (1, -1) 和 (-1, 1) 互为相反向量另外两组也是。所以本质上你手里相当于握住了三个轴方向的“正负步”只是这三个轴不是互相垂直的但组合起来同样能张成整个平面。观察六个方向可以发现一个关键事实沿某个方向走一步再去掉沿另一个方向走一步可能等效于某个单步方向。比如先 (0,1) 再 (1,-1)合计是 (1,0)也就是向右一步。这意味着同一个终点会有非常多的路径表示所以去重是必须的也正因为这种冗余才让“恰好 N 步”变得大多数情况下都能实现。2. 先别急着推公式打表把规律“看”出来2.1 用 BFS 打小数据的表我不建议一上来就闷头推导因为在没有结论的时候你根本不知道要证什么。正确做法是先用暴力程序把 N0 到 N8 的答案全部算出来盯着数字看几分钟。打表代码非常简单。用 set 存点用坐标结构体判重。我写了一个 C 版本的 BFS#include bits/stdc.h using namespace std; struct Point { int x, y; bool operator(const Point other) const { if (x ! other.x) return x other.x; return y other.y; } }; int main() { int dx[6] {1, -1, 0, 0, 1, -1}; int dy[6] {0, 0, 1, -1, -1, 1}; for (int N 0; N 8; N) { setPoint cur, nxt; cur.insert({0, 0}); for (int step 0; step N; step) { nxt.clear(); for (auto p : cur) { for (int k 0; k 6; k) { nxt.insert({p.x dx[k], p.y dy[k]}); } } cur nxt; } cout N N - cur.size() \n; } return 0; }这里每循环一次 step 就相当于走了一步cur 里存的是当前步数下所有可达点。因为 set 会自动去重所以最后 cur.size() 就是答案。我跑出来的结果如下。2.2 观察到的序列N可达格点数0116219337461591612771698217看到 1、6、19、37、61、91、127 之后我第一反应是查差分。6 - 1 519 - 6 1337 - 19 1861 - 37 2491 - 61 30127 - 91 36从 N2 开始差分是 18、24、30、36每次增加 6。也就是说从 N2 往后相邻两项之差是 6(N1)或者说约等于 6 的倍数递增。二次差分恒定是 6这强烈暗示答案是一个关于 N 的二次函数。再对比一个经典数列中心六边形数 1, 7, 19, 37, 61, 91, 127。除了 N1 那一项差了 1后面的 19、37、61、91、127 完全对上了。中心六边形数的通项是 1 3N(N1)也就是 3N^2 3N 1。打表结果已经给了很明显的信息这道题的答案大概率就是 3N^2 3N 1只不过当 N1 时需要特殊处理因为数列里 1 对应的不是 7而是 6。2.3 差分和公式如何对应如果你手边有计算器把 3N^2 3N 1 验证一下N212 6 1 19N327 9 1 37N448 12 1 61而相邻两项差的公式是(3(N1)^2 3(N1) 1) - (3N^2 3N 1) 6N 6 6(N1)这正好解释了打表里 N2 往后差分是 18、24、30、36 的规律。差分等于 6 的倍数意味着图形上每一圈新增的格点数量是线性增加的这跟“六边形按圈向外扩展”的直觉完全吻合。打表找规律的套路在这道题上体现得淋漓尽致你不需要一开始就知道什么高深理论只需要把前几项算出来然后观察差分、二阶差分或者和已知数列比对。一旦发现二次差分恒定就可以放心大胆地假设通项是二次函数。3. 为什么答案是中心六边形数几何解释与证明思路3.1 三角格点与六边形圈如果你把六个方向画成一个图会发现所有可达点在平面上排布成一个六边形形状的网格这正是三角格点图。从原点出发走 0 步是圆心 1 个点走 1 步以内能到的点是围绕圆心的一圈 6 个点走 2 步以内能到的点又向外扩展一圈新增 12 个点走 3 步以内能到的点新增 18 个点。这里有一个关键观察每一步最多让“到原点的某种距离”增加 1而这个距离在三角格点上刚好可以用“六边形圈数”来衡量。走 N 步以内能到达的所有点恰好是以原点为中心、半径为 N 的六边形内部及边界的全部格点。那么这个六边形内到底有多少个点很简单一圈一圈数第 0 圈圆心1 个点第 1 圈6 个点第 2 圈12 个点第 3 圈18 个点...第 k 圈6k 个点所以走 N 步以内能到达的格点总数是1 6 12 18 ... 6N 1 6 * (1 2 ... N) 1 3N(N1)展开就是 3N^2 3N 1。你可能已经发现了这个式子还有一个非常漂亮的等价形式3N^2 3N 1 (N1)^3 - N^3它就是相邻两个立方数的差。这不是巧合而是中心六边形数和立方数之间的经典关系。所以在代码里你既可以写 3LL * N * N 3LL * N 1也可以写 (N1)^3 - N^3。就编程而言前者更直接不会因为乘方溢出出问题。3.2 为什么 N2 时“恰好 N 步”能覆盖全部点上面数的是“N 步以内”能到达的点但题目问的是“恰好 N 步”能到达的点。这里需要论证一件事对任意一个距离原点不超过 N 的格点都一定存在一条长度恰好为 N 的路径走到它。先看原点本身。N2 时可以先走 (1,0) 再走 (-1,0) 回原点N3 时可以走 (1,0)、(-1,1)、(0,-1)三个向量加起来是 (0,0)。所以只要 N2原点都能被恰好走到。再看距离原点 1 步的那些点比如 (1,0)。N2 时可以走 (0,1) (1,-1)合计就是 (1,0)N3 时也能走因为可以先用两步到达 (1,0)再绕一个三角形环回到原位。所以距离 1 的点在 N2 时也都能被恰好走到。那么距离更远的点呢假设某个点最短需要 L 步到达其中 LN。你需要把步数从 L 补到 N。怎么补有两个基本“绕路”手段两步往返走一个方向再走它的反方向合计 2 步位置不变比如 (1,0) (-1,0)。三步三角环走三条方向向量合计为 03 步回到原点比如 (1,0) (-1,1) (0,-1)。由于 2 和 3 可以组合出任何不小于 2 的整数差值除了 1所以只要 N-L 不等于 1补步数都能实现。唯一需要担心的是 N-L1 的情况也就是路径长度只比最短距离多 1。这时候因为 3 步三角环和 2 步往返都加不进去看起来会出问题。但实际分析会发现对于 L1 的任意点都可以直接用一条长度为 L1 的折线走到它因为三角形的存在让“走一步之后再绕个小弯”变得非常容易。所以真正无法处理的情况只有 L0 且 N1也就是原点只用一步回不去。因此结论就是N0 时答案是 1N1 时答案是 6N2 时答案等于中心六边形数 3N^2 3N 1。这是一个很典型的“先数后证”路径先用几何直观告诉你总点数是多少再用三角格点上的绕路性质说明这些点都能被刚好覆盖到。日常做题时你不需要把证明写得像论文那么严格但至少要能说服自己。3.3 N1 这个特例是怎么来的为什么打表结果里 N1 是 6而不是公式给的 7因为公式 13N(N1) 算的是“距离原点不超过 N 的所有格点”其中包含原点。当 N1 时这个集合是原点加周围 6 个点共 7 个。但“恰好 1 步”从原点出发不可能留在原点一步走出去位置就变了所以原点必须从答案中去掉剩下 6 个。这个特例极其阴险。你从 N2 开始推规律得到 3N^23N1验证 N2、3、4 全对想当然地认为 N1 也适用结果提交上去 WA。标准的 UVa 题解里基本都有一行 if (n 1) 的特判原因就在这里。如果你的代码还能遇到 N0 的输入那就更要注意公式在 N0 时算出来是 1而 0 步只能待在原点答案恰好是 1所以 N0 用公式也正确。但很多题目给的约束是 N1这时候 N1 特判就足够了。4. 代码实现与边界处理4.1 C 主代码当你确定了公式和特判之后AC 代码非常短。这里我给出一个标准的 EOF 写法#include cstdio int main() { long long n; while (scanf(%lld, n) 1) { if (n 1) { printf(6\n); } else { printf(%lld\n, 3LL * n * n 3LL * n 1); } } return 0; }有几个点需要解释一下。第一为什么要用 long long因为 3N^2 这一项在 N 比较大时增长很快。假设 N 可以到 10^9那么 N^2 是 10^18 级别int 只有 32 位最大能表示约 2.1×10^9远远不够。long long 在绝大多数在线判题系统里是 64 位能扛住这个范围。我一开始用 int 交小数据没问题一旦题目里有大 N 的测试点就爆掉所以直接上 long long 是最稳妥的。第二为什么用 while (scanf(%lld, n) 1)因为 UVa 老题的风格一般是不给测试组数而是不断读入直到文件结束。如果你只读一组数据遇到多组输入就会漏算。有的题目第一行会先给 T那就改成先读 T 再循环 T 次但原题我记得是非 EOF 莫属所以采用这个写法。第三特判 n 1 一定要放在公式之前。因为 n1 时代入公式得到 7答案是 6差的是原点。如果题目给的 N 可能是 0你要不要特判不需要因为公式在 N0 时算出的结果是 1和实际一致。4.2 Python 的实现与快速验证如果你平时用 Python 刷题或者想迅速验证小数据代码更简洁import sys for line in sys.stdin: line line.strip() if not line: continue n int(line) if n 1: print(6) else: print(3 * n * n 3 * n 1)Python 的整数没有溢出问题所以直接算就行。但要注意输入里可能混有空行所以 strip 之后跳过空行是个好习惯。我还建议你把 BFS 打表代码和这段公式代码放在一起写一个对拍程序。随便生成几个小 N对比 BFS 结果和公式结果一旦发现不一致立刻定位。这种对拍习惯在算法竞赛里非常有用能够避免你把一个错误的规律当成真理直接提交。4.3 时间复杂度与空间复杂度公式解的时间复杂度是每组数据 O(1)空间复杂度是 O(1)。不管 N 有多大不管有多少组数据每个测试点都是常数时间。相比 BFS 的状态爆量这完全是降维打击。在线判题最讨厌的就是超时和超内存。超时可以通过推公式解决超内存则直接不会出现在这道题里。你只需要小心输入输出别太慢。C 里如果用了 cin/cout建议加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr)或者干脆用 scanf/printf这样在大数据量下会稳很多。5. 常见问题与排查技巧实录5.1 WA 的经典原因汇总我在群里见过好几个同学卡在这道题总结下来基本就是下面几个原因。第一个就是漏掉 N1 特判。这也是最常见的错误。如果你提交后 WA但你已经推导出公式优先检查是不是这个问题。直接把 n1 特判加上十有八九就过了。第二个是 int 溢出。很多同学看完题意觉得 N 最大可能也就几万直接用 int 写结果题目隐藏数据里冒出个大 NWA 或者报运行时错误。建议所有涉及平方的中间结果一律用 long long。第三个是读入方式不对。题目如果有多组数据你却只用 scanf 读了一次那程序只会处理第一个测试点后面的全部忽略自然 WA。处理 EOF 是 UVa 的老传统养成 while (scanf(...) 1) 的习惯能帮你少踩很多坑。第四个是方向集合写错。虽然你没有用 BFS 做最终代码但如果打表阶段方向就写错了你观察到的规律就是错的。六个方向里最容易漏的是 (1,-1) 和 (-1,1) 这对对角线或者误写成 (1,1)。一旦方向错打表数据就和正确题意不符后续推导全废。我整理成表格方便你对照排查错误类型现象解决办法漏特判 N1样例过了但隐藏数据 WA增加 if (n 1) 输出 6int 溢出N 较大时输出负数或错值使用 long long读入只处理一次多组数据只算第一组改为 while EOF方向向量写错打表规律不对核对 (1,-1)、(-1,1) 等六个方向公式记忆错误输出和打表对不上用 3N^23N1 或 (N1)^3-N^35.2 怎么快速自检公式给你一个笨但有效的方法写一个 15 行的暴力程序把 N0 到 N7 的答案全算出来然后写一个公式程序输出同样范围的答案两个程序的结果并排打印肉眼比对。我用的方向数组是这样的int dx[6] {1, -1, 0, 0, 1, -1}; int dy[6] {0, 0, 1, -1, -1, 1};注意这里的方向顺序无所谓只要六个方向齐全就行。我的顺序是右、左、上、下、右下、左上。你根据自己的习惯调整即可。对拍时重点看 N1暴力输出 6公式输出 7这时候你就知道特判必须加。其他 N 值两边应该完全一致。如果 N2 或 N3 就对不上那多半是方向写错或者公式算错。5.3 从这道题延伸出去的套路“打表找规律 - 差分判断 - 假设通项公式 - 特判边界 - O(1) 输出”这个流程在组合计数题里非常通用。UVa 和同类在线判题里有一批题都是这个套路核心就是让你从小数据里发现二次或线性规律。比如很多六边形棋盘、三角形网格计数题答案最后都是 3N^23N1 这种形式。你甚至可以记住一个规律如果差分序列是等差数列原数列就是二次函数如果二阶差分恒定通项一定是二次多项式。反过来如果差分序列是等比数列那就要往指数函数上想。另外(N1)^3 - N^3 这个形式值得单独记一下。它既可以是中心六边形数也对应着三维空间里立方体的增长量。在解题时如果发现答案和立方差有关大概率能找到几何解释。我个人做这道题的体会是不要轻视任何一道“看起来像搜索”的题。你花五分钟写个 BFS 打表可能帮你省下五个小时的无效推导而推公式的时候也一定要记得把 N 的每个小值都代入验证一遍尤其是 0 和 1因为边界永远是最容易出错的地方。以后遇到类似题目先暴力拿小数据再盯着数字多看一眼答案往往就自己跳出来了。
