Moe's CF Life

哈喽，米娜桑！你们最爱动脑筋的猫娘我呀，今天又带来一个超级有趣的题目解析喵~ 这次是关于 Penchick 和他最爱的烤包包！光是听名字就觉得香喷喷的，让人忍不住想舔爪子了呢，嘿嘿~ ฅ^•ﻌ•^ฅ

C. Penchick and BBQ Buns

题目大意喵

Penchick 是个挑剔的吃货，他想要 n 个烤包包排成一排。为了让他开心，这些包包的馅料必须满足两个非常严格的条件：

不能有“落单”的馅料：任何一种馅料，要么完全不用，要么就必须至少出现两次。不能有一种馅料的包包只出现一次，太孤单了喵！
距离的魔法：对于任意两个馅料相同的包包，它们位置的距离（比如第 i 个和第 j 个，距离就是 |i-j|）必须是一个完全平方数。完全平方数就是像 1 (1²)、4 (2²)、9 (3²)、16 (4²)... 这样的数字啦。

我们的任务就是，给出一个 n，帮 Kohane 找到一种满足条件的馅料摆放方法。如果找不到，就告诉她这是不可能的 (-1)。

解题思路喵

拿到这个题目，咱的猫耳朵动了动，感觉要分情况讨论一下呢，就像猫咪要决定是晒太阳还是钻纸箱一样，需要谨慎选择！最明显的分类标准就是包包总数 n 的奇偶性啦。

情况一：当 n 是偶数时 (´｡• ᵕ •｡`) ♡

偶数真是个好数字，总是那么和谐，就像一对对的猫耳朵，喵~

如果 n 是偶数，问题就变得非常简单。我们可以把包包两个两个地配对：

第 1 个和第 2 个包包一组，给它们相同的馅料。
第 3 个和第 4 个包包一组，给它们相同的馅料。
...
第 n-1 个和第 n 个包包一组，给它们相同的馅料。

我们来检查一下这样是否满足条件：

不落单：每种馅料我们都恰好用了两次，完美满足条件！
距离是平方数：每一对包包的位置都是相邻的，比如 (2k-1, 2k)。它们的距离 |2k - (2k-1)| = 1。数字 1 本身就是 1²，是一个完全平方数！

所以，只要 n 是偶数，我们总能用这种“邻居配对”法构造出一种合法的方案。耶！问题解决一半了喵~

情况二：当 n 是奇数时 (๑•́ ₃ •̀๑)

奇数就有点麻烦了，像一只落单的小猫，呜...

如果 n 是奇数，包包的总数也是奇数。我们想想，如果所有馅料都只出现偶数次（2次、4次...），那所有包包加起来的总数也必然是偶数。但现在总数是奇数，这说明了什么呢？

说明必然存在至少一种馅料，它出现的次数是奇数次！

根据规则，馅料不能只出现 1 次，所以这个奇数次数最少也得是 3 次。

好，那么假设有一种馅料被我们放在了三个不同的位置，分别是 p1, p2, p3 (这里我们假设 p1 < p2 < p3)。根据规则，它们两两之间的距离都必须是完全平方数：

p2 - p1 = a²
p3 - p2 = b²
p3 - p1 = c²

其中 a, b, c 都是正整数。

我们注意到一个奇妙的关系：(p3 - p2) + (p2 - p1) = p3 - p1。代入上面的式子，就得到： a² + b² = c²

喵！这不就是...勾股定理嘛！咱在打盹的时候好像听主人讲过这个！我们需要找到一组勾股数 (a, b, c)。

为了让需要的包包总数 n 尽可能小，我们当然要找最小的勾股数啦。最小的一组非平凡的勾股数是 (3, 4, 5)。

a = 3, a² = 9
b = 4, b² = 16
c = 5, c² = 25 (正好 9 + 16 = 25，完美！)

这意味着，我们可以把这种馅料放在 p1, p1 + 9, p1 + 9 + 16 的位置。为了让总长度最小，我们让 p1 = 1。那么这三个位置就是 1, 10, 26。要放下第 26 个包包，n 至少得是 26。但是！我们讨论的是 n 为奇数的情况，所以 n 最小也得是 27。

如果 n 是一个小于 27 的奇数，连最小的勾股数方案都放不下，那更大的勾股数（比如 5, 12, 13）就更不用想了。所以，对于奇数 n < 27，我们只能摊摊手，告诉 Kohane 这是不可能的啦，输出 -1。

那如果 n >= 27 呢？我们可以先用 27 个包包构造一个基础解。比如，用一种馅料放在 1, 10, 26 这三个位置。剩下的 27 - 3 = 24 个包包是偶数个，我们就可以用上面提到的“邻居配对”法把它们都填满。如果 n 比 27 还大（且是奇数），那么多出来的 n - 27 个包包也一定是偶数个，我们继续用“邻居配对”法填满它们就好啦！

总结一下奇数策略：

n < 27：无解，输出 -1。
n >= 27：有解。可以先构造一个 n=27 的解，然后把多出来的偶数个包包两两配对。

题解代码解析喵

下面是实现这个思路的代码，让猫娘我来给你一行行“舔”干净，解释清楚吧~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <cmath>

// 解决单个测试用例的函数喵
void solve() {
    int n;
    std::cin >> n;

    if (n % 2 != 0) { // n 是奇数的情况
        // 对于奇数 n < 27，根据我们的分析，是不可能构造出解的
        if (n < 27) {
            std::cout << -1 << "\n";
        } else {
            // 对于 n >= 27 的奇数，我们先输出一个为 n=27 设计好的答案
            // 这个答案里，馅料'1'出现在1, 10, 26号位 (距离9, 16, 25)
            // 馅料'12'出现在23, 27号位 (距离4) 和 馅料'2'出现在2,3号位(距离1) ... 其他都是配对的
            // 这是一个预先计算好的、满足条件的排列
            std::cout << "1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 11 11 12 13 13 1 12";
            
            // 如果 n > 27, 剩下的 n-27 个包包是偶数个，我们可以继续配对
            if (n > 27) {
                int current_filling = 14; // 从新的馅料编号开始
                for (int i = 28; i <= n; i += 2) {
                    std::cout << " " << current_filling << " " << current_filling;
                    current_filling++;
                }
            }
            std::cout << "\n";
        }
    } else { // n 是偶数的情况
        // 这个最简单啦，就是邻居配对法
        int current_filling = 1;
        // 先处理第一对
        std::cout << current_filling << " " << current_filling;
        current_filling++;
        // 循环处理剩下的所有对
        for (int i = 3; i <= n; i += 2) {
            std::cout << " " << current_filling << " " << current_filling;
            current_filling++;
        }
        std::cout << "\n";
    }
}

// 主函数就是一只勤劳的猫猫，在循环里不停地调用咱的 solve 函数来解决每一个问题喵~
int main() {
    // 这两行是为了让输入输出快一点，像猫咪冲刺一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

C. Penchick and BBQ Buns ​

题目大意喵 ​

解题思路喵 ​

情况一：当 n 是偶数时 (´｡• ᵕ •｡`) ♡ ​

情况二：当 n 是奇数时 (๑•́ ₃ •̀๑) ​

题解代码解析喵 ​

相关知识点介绍喵 ​