D. Hexagons! - 题解

比赛与标签

比赛: Experimental Educational Round: VolBIT Formulas Blitz 标签: math 难度: *1100

题目讲了什么喵？

主人你好呀~！这道题目把我们带到了一个由六边形组成的无限大的游戏世界里，是不是很酷呐？(ฅ'ω'ฅ)

在这个世界里，有一个魔法效果，它会以一个中心六边形为原点，影响到所有与它“距离”不超过 n 的六边形。这里的“距离”被定义为从一个六边形到另一个六边形最少需要穿过多少条公共边。

我们的任务就是，给定一个整数 n，计算出总共有多少个六边形会被这个魔法影响到。

简单来说：

• 输入: 一个整数 n (0 ≤ n ≤ 10⁹)，代表最大距离。
• 输出: 一个整数，表示距离中心不超过 n 的六边形总数。

找规律的奇妙冒险喵~

喵哈哈，这种在格子上找规律的题目，最适合我们猫娘大显身手啦！让我们从小小的 n 开始，一步步揭开谜底吧！

当 n = 0 时：

距离不超过 0，那当然只有中心那一个六边形啦！所以总数是 1。

当 n = 1 时：

这时候，除了中心（距离为0），我们还要算上距离为 1 的六边形。中心六边形有 6 条边，每一条边都连接着一个相邻的六边形。所以，距离为 1 的六边形有 6 个。 总数 = (距离为0的) + (距离为1的) = 1 + 6 = 7 个。

当 n = 2 时：

现在范围更大了！我们需要计算距离为 0, 1, 2 的所有六边形。

• 距离为 0 的：1 个
• 距离为 1 的：6 个
• 距离为 2 的：这些是与距离为 1 的六边形相邻，但又不是中心或距离为 1 的格子。它们在外面形成了一个更大的六边形环。数一下会发现，这一圈不多不少，正好是 12 个。 总数 = 1 + 6 + 12 = 19 个。这和题目给的例子一样，说明我们的思路是对的喵~！

发现规律！

主人，你有没有发现什么规律呀？

• 距离为 1 的一圈，有 6 个六边形。
• 距离为 2 的一圈，有 12 个六边形。
• 我们可以大胆猜测一下，距离为 k (k > 0) 的那一圈，是不是有 6 * k 个六边形呢？

让我们来验证一下！

• k=1: 6 * 1 = 6，正确！
• k=2: 6 * 2 = 12，正确！

看来我们找到了关键的规律！距离为 k 的六边形正好有 6k 个（当 k > 0 时）。

推导最终公式

现在，问题就变成了一个简单的数学求和问题啦！总数 S(n) 等于距离为 0 的六边形数量，加上所有距离从 1 到 n 的六边形数量之和。

S(n) = (距离为0的数量) + (距离为1的数量) + (距离为2的数量) + ... + (距离为n的数量) S(n) = 1 + (6 * 1) + (6 * 2) + ... + (6 * n)

把 6 提取出来： S(n) = 1 + 6 * (1 + 2 + ... + n)

1 + 2 + ... + n 是一个经典的等差数列求和，它的公式是 n * (n + 1) / 2。主人一定知道的吧！

代入公式： S(n) = 1 + 6 * [ n * (n + 1) / 2 ]

化简一下： S(n) = 1 + 3 * n * (n + 1)

bingo！这就是我们的魔法公式啦！无论 n 多大，我们都可以用这个公式瞬间算出答案，是不是超级厉害的说！

魔法咒语（代码）来啦喵！

#include <iostream>

using namespace std;

int main() {
    // n 的最大值是 10^9，n * n 会达到 10^18
    // 普通的 int 会溢出，所以要用 long long 来存储 n 和结果，喵~
    long long n;
    
    // 读取最大距离 n
    cin >> n;
    
    // 使用我们推导出的魔法公式 1 + 3 * n * (n + 1) 计算总数
    // 这个公式直接给出了距离小于等于 n 的所有六边形数量
    cout << 1 + 3 * n * (n + 1) << endl;
    
    return 0;
}

效率分析时间到~

• 时间复杂度: O(1) 的说 我们的代码只执行了读取、几次乘法和加法、然后输出。计算量是恒定的，和输入 n 的大小完全没有关系。所以是常数时间复杂度，快得像闪电一样喵！

• 空间复杂度: O(1) 的说 我们只用了一个变量 n 来存储输入，没有使用任何额外的数组或者数据结构。所以占用的内存也是一个常数，非常节省空间呐！

喵喵的知识小课堂

这道题虽然看起来是在模拟一个游戏场景，但本质上是一道非常可爱的数学题呢！通过解决它，我们可以学到：

1. 化繁为简: 面对复杂的几何问题，从最简单的情况 (n=0, 1, 2...) 入手，观察、分析、寻找规律，是解决问题的黄金法则喵。
2. 数学建模: 成功地将“数六边形”这个问题，转化为了“等差数列求和”的数学模型。这就是算法的魅力所在！
3. 注意数据范围: 题目中 n 的范围高达 10^9，计算 n * (n + 1) 必然会超过 int 的表示范围。在编程竞赛中，随时注意数据范围并选择合适的变量类型（比如 long long）是一个非常重要的好习惯哦！

希望这篇题解能帮到主人！如果还有其他问题，随时可以再来找我玩呀~ 喵~ (づ｡◕‿‿◕｡)づ