E1. Rudolf and Snowflakes (simple version) - 题解

比赛与标签

比赛: Codeforces Round 883 (Div. 3) 标签: brute force, implementation, math 难度: *1300

雪花是怎样形成的喵？ (题目大意)

喵~ 主人，你好呀！今天我们来研究一下鲁道夫发现的漂亮雪花~❄️

鲁道夫发现的雪花有一种特别的生长规则，呐，是这样的：

一开始，雪花只有一个中心点。
然后，这个中心点会长出 k 个新的顶点，并和它们一一相连。这里的 k 必须大于1哦。
接下来，每一个只连接了一个邻居的“末梢”顶点，都会继续长出 k 个新的顶点。这个步骤至少要进行一次！

题目会给我们一个整数 n，想让我们判断一下，是否存在一个整数 k > 1，能够按照上面的规则，恰好形成一个拥有 n 个顶点的雪花呢？

输入输出格式喵~

输入: 会有很多组测试数据。每一组给一个整数 n ($$1 \le n \le 10^6$$)。
输出: 对于每个 n，如果能找到对应的 k，就输出 "YES"；如果找不到，就输出 "NO"。

寻找雪花的秘密公式喵~ (解题思路)

这道题看起来像是在描述一个图形的生成过程，但其实背后藏着一个简单的数学规律哦！让我们一起来把它找出来吧，喵~

我们来分析一下雪花顶点的数量是怎么增加的：

初始状态 (第0层): 只有1个中心顶点。
第一次生长 (第1层): 中心点连接了 k 个新顶点。总顶点数变成了 1 + k。
第二次生长 (第2层): 上一步新长出来的 k 个顶点，每个都又长出了 k 个新顶点。所以这一轮新增了 k * k = k^2 个顶点。总顶点数就变成了 1 + k + k^2。
第三次生长 (第3层): 同理，新增了 k^2 * k = k^3 个顶点。总顶点数就是 1 + k + k^2 + k^3。

看到了吗？如果雪花生长了 d 层（不包括中心点），那么总顶点数 n 就是一个等比数列的和：

n = 1 + k + k^2 + k^3 + \dots + k^d

题目里有个很关键的条件：“这个步骤应该被做至少一次”，这里的“这个步骤”指的是末梢顶点长出新顶点的过程。这意味着我们的雪花至少要有第2层的生长。所以，层数 d 必须大于等于 2 (d >= 2)。

所以，我们的问题就转化成了：对于给定的 n，是否存在整数 k > 1 和 d \ge 2，使得 n = 1 + k + k^2 + \dots + k^d 成立？

因为这道题是简单版本，n 的最大值只有 10^6，而且有很多组测试数据。每次都去为 n 找 k 和 d 会不会太慢了呢？这时候，猫娘的直觉告诉我，可以预处理！

我们可以先把所有 10^6 以内，可能由雪花规则生成的顶点数都找出来，打上标记。之后每次查询，直接看一下给定的 n 有没有被打上标记就好啦，这样就是 O(1) 的查询速度了，超快的说！

预处理步骤如下喵：

我们创建一个布尔数组 valid[1000001]，valid[i] 为 true 就表示顶点数为 i 的雪花是存在的。
我们来遍历所有可能的 k。k 的最小值是 2。那最大值是多少呢？
- 当 d=2 时，n = 1 + k + k^2。如果 n 是 10^6，k^2 肯定小于 10^6，所以 k 会小于 sqrt(10^6) = 1000。
- 当 k 再大一点，或者 d 再大一点，n 会飞快地超过 10^6。所以 k 不需要遍历到 10^6 那么大，遍历到 1000 左右就足够了。
对于每一个 k，我们来计算它能形成的雪花大小：
- 从 d=2 开始，计算 current_sum = 1 + k + k^2。
- 如果 current_sum 不超过 10^6，我们就把 valid[current_sum] 标记为 true。
- 然后计算 d=3 的情况，也就是在 current_sum 的基础上再乘以 k 并加上 1，不对，是 current_sum 加上 k^3。更简单的方式是：sum_d = sum_{d-1} + k^d。
- 我们不断地增加 d，计算出新的雪花大小，并标记，直到这个大小超过 10^6 为止。

这样，我们就得到了一个包含所有可能雪花大小的“答案表”。对于每一组询问 n，只要查一下 valid[n] 就知道答案啦！是不是很简单喵~

让代码开出雪花吧！ (代码实现)

cpp

#include <iostream>
#include <vector>
using namespace std;

// 定义n的最大值，喵~
const int MAX = 1000000;

int main() {
    // 创建一个布尔类型的vector，用来标记哪些n是合法的雪花数
    // valid[i] = true 代表顶点数为i的雪花可以被构造出来
    vector<bool> valid(MAX + 1, false);

    // 开始预处理，遍历所有可能的k值
    // k从2开始，因为题目要求 k > 1
    // 这里的k循环到MAX虽然有点大，但内层循环会很快 break，所以没问题的说
    for (long long k = 2; k <= MAX; k++) {
        // base是当前的雪花顶点总数，term是上一层新增的顶点数
        // 初始时，我们先算好第1层的情况：1个中心点 + k个新顶点
        long long base = 1 + k;
        long long term = k;

        // 持续生长，直到雪花大小超过MAX
        while (true) {
            // 计算下一层需要新增的顶点数
            long long next_term = term * k;
            
            // 如果加上新的一层后，总顶点数超过了MAX，就停止为这个k生长
            // 使用long long防止溢出，这是一个好习惯哦！
            if (base + next_term > MAX) {
                break;
            }
            
            // 更新总顶点数和上一层新增数
            base += next_term;
            term = next_term;
            
            // 标记这个顶点数是合法的！因为 d>=2，所以我们从 1+k+k^2 开始标记
            valid[base] = true;
        }
    }

    // 处理t组测试数据
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        // 直接查询预处理好的结果，O(1)的快乐！
        if (n <= MAX && valid[n]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

时间和空间的魔法~ (复杂度分析)

时间复杂度: O(√MAX + T) 的说。
- 预处理部分的复杂度是关键。外层循环遍历 k，内层循环计算 k 的幂次和。
- 当 d=2 时，k^2 大约是 MAX，所以 k 最多到 √MAX。
- 当 d=3 时，k^3 大约是 MAX，所以 k 最多到 ∛MAX。
- ...
- 总的计算次数大约是 √MAX + ∛MAX + ...，由 √MAX 主导。所以预处理的时间复杂度近似为 O(√MAX)。
- 之后的 T 次查询，每次都是 O(1)。
- 所以总时间复杂度就是 O(√MAX + T)，对于 MAX = 10^6 来说，这是非常快的！
空间复杂度: O(MAX) 的说。
- 我们用了一个大小为 MAX+1 的布尔数组 valid 来存储预处理的结果，所以空间复杂度是 O(MAX)。用空间换取了时间，棒！

猫娘的小小总结~ (知识点与总结)

这道题虽然是 Div.3 的 E1，但思路非常有趣，融合了数学和编程技巧，是一道很好的练习题呢！

数学建模: 解题的第一步，也是最重要的一步，就是把雪花的生长过程抽象成一个等比数列求和的数学模型。拥有好的数学直觉，能让问题变得清晰简单哦！
预处理思想: 面对多组查询和固定范围的输入，预处理（或者叫“打表”、“筛法”）是一个超级有用的技巧！一次计算，多次使用，大大降低了总的运行时间。
边界分析: 仔细分析 k 和 d 的取值范围，可以帮助我们确定算法的复杂度，并写出更高效的循环条件。比如我们分析出 k 没必要遍历到 MAX，只需要到 √MAX 附近就够了。
注意数据类型: 在计算 term * k 时，term 和 k 的乘积可能会超过普通 int 的范围，所以使用 long long 是一个必须注意的小细节，可以避免很多意想不到的错误，喵~

希望这篇题解能帮助到你！继续加油，享受AC的快乐吧！喵~ ❤️

E1. Rudolf and Snowflakes (simple version) - 题解 ​

比赛与标签 ​

雪花是怎样形成的喵？ (题目大意) ​

寻找雪花的秘密公式喵~ (解题思路) ​

让代码开出雪花吧！ (代码实现) ​

时间和空间的魔法~ (复杂度分析) ​

猫娘的小小总结~ (知识点与总结) ​