F. Puzzle - 题解

比赛与标签

比赛: Educational Codeforces Round 179 (Rated for Div. 2) 标签: brute force, constructive algorithms, greedy, math 难度: *2400

喵喵的题目解读

主人给了我们一个任务，要用很多 1x1 的小方块拼图。我们需要拼出一个单一连通的图形（就是说所有方块都得连在一起，不能分成几块哦），并且这个图形的周长（Perimeter）和面积（Area）的比值，要正好等于给定的 p/s 呐。

总共使用的方块数量（也就是面积）不能超过 50,000。

如果能拼出来，就要告诉本喵用了多少块方块，以及每一块方块的坐标。如果无论如何都拼不出来，就伤心地说一声 -1 就好啦。

简单来说，就是：

• 输入: 两个整数 p 和 s。
• 目标: 构造一个图形，使得 周长 / 面积 = p / s。
• 输出: 如果成功，输出方块数量和坐标；否则输出 -1。

寻找完美身材的喵喵~

这道题的核心就是构造一个满足特定周长和面积比例的图形。直接去凑可能会像无头苍蝇一样乱撞，所以我们需要一套清晰的策略，喵！

第一步：化繁为简喵~ (简化比例)

我们面对的等式是 周长 / 面积 = p / s。 这可以写成 周长 * s = 面积 * p。

看到这种比例关系，本猫娘的直觉告诉我们，第一步一定是化简！我们将 p 和 s 同时除以它们的最大公约数（__gcd(p, s)）。这样 p 和 s 就互质了。

p 和 s 互质后，从 周长 * s = 面积 * p 这个等式中，我们可以得出一个非常重要的结论：

• 面积 必须是 s 的倍数。
• 周长 必须是 p 的倍数。

所以，我们可以设 面积 = k = s * i 以及 周长 = c = p * i，其中 i 是某个正整数。我们的任务就变成了，找到一个合适的整数 i，然后构造出面积为 k、周长为 c 的图形！

第二步：思考一些基本限制~

在开始构造前，我们先排除一些明显不可能的情况，这样可以省下很多力气呢！

1. 周长的上限: 对于一个由 k 个方块组成的图形，它的周长 c 最多是多少呢？是 4 * k（每个方块都贡献4条边，互不相邻）。所以，c <= 4k，也就是说 c / k <= 4。因此，我们要求的比例 p / s 也必须满足 p / s <= 4，即 p <= 4s。如果输入不满足这个条件，直接输出 -1 就好啦！
2. 周长的奇偶性: 任何由方格组成的图形，它的周长一定是偶数！你可以想象沿着图形的边界走一圈，向右走的步数和向左走的步数相等，向上和向下也一样，总步数（周长）必然是偶数。所以，我们计算出的目标周长 c = p * i 必须是偶数。如果 c 是奇数，这个 i 就不行，我们得试试下一个 i。

第三步：构造一个万能的形状！

好戏登场！怎么才能灵活地构造一个图形，同时控制它的周长和面积呢？

本喵想到了一个绝妙的主意！我们来构造一个可以被填充的 "L" 型框架。

想象一个 h 行 l 列的巨大矩形。它的周长是 2 * (h + l)。我们可以不把它完全填满，而是只画出它的轮廓。一个最简单的轮廓就是一个 "L" 型，它由一个 1 x l 的横条和一个 h x 1 的竖条在角点 (1,1) 连接而成。

• 周长: 这个 "L" 型框架正好占据了一个 h x l 矩形的边界范围，所以它的周长就是 2 * (h + l)。这太棒了！只要我们确定了 h 和 l，周长就固定了。
• 面积: 这个 "L" 型框架本身的面积是 h + l - 1（因为角点 (1,1) 被计算了两次）。更神奇的是，我们可以在这个 h x l 的框架内部（那些 x > 1 且 y > 1 的位置）任意填充方块，而完全不改变它的周长！

这意味着，对于一个由 h 和 l 决定的 "L" 型框架，我们可以构造出任意面积 k，只要 k 满足： h + l - 1 (只有框架) <= k <= h * l (框架被完全填满)

第四步：整合思路，开始搜索！

现在我们的计划清晰了：

1. 化简 p 和 s。
2. 检查 p <= 4s，否则无解。
3. 循环遍历倍数 i (从 1 开始)，确保目标面积 s * i 不超过 50,000。
4. 对于每个 i，计算出目标面积 k = s * i 和目标周长 c = p * i。
5. 检查 c 是否为偶数。如果不是，跳过这个 i。
6. 我们知道 c = 2 * (h + l)，所以 h + l = c / 2。我们可以循环遍历 h 的可能值（比如从 1 到 c/2 - 1），l 也就随之确定了 (l = c/2 - h)。
7. 对于每一对 (h, l)，检查我们的目标面积 k 是否在它们能构造的范围内：h + l - 1 <= k <= h * l。
8. 一旦找到满足条件的 (h, l)，我们就成功了！可以开始打印坐标：
   • 先打印 "L" 型框架：l 个方块 (1, 1)...(1, l) 和 h-1 个方块 (2, 1)...(h, 1)。
   • 然后计算还需要填充的方块数量 remaining = k - (h + l - 1)。
   • 在框架内部（x 从 2 到 h，y 从 2 到 l）依次放置方块，直到用完 remaining 个。
9. 如果所有循环都跑完了还没找到解，那就真的无解了，输出 -1。

这个方法通过枚举 i 和 h，暴力搜索所有可能的构造方案，但由于 p, s 很小，且解通常在 i 较小时出现，所以速度是足够快的！

喵喵的代码实现

#include <iostream>
#include <algorithm>
#include <numeric> // 为了 __gcd

// 为了防止溢出和方便，我们把 int 定义为 long long，是个好习惯喵~
#define int long long

signed main() {
    // 关掉同步流能让输入输出快一点点，虽然这题不卡这个
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T;
    std::cin >> T;
    while (T--) {
        int p, s;
        std::cin >> p >> s;

        // Step 1: 化简 p/s，让它们互质
        int g = std::gcd(p, s);
        p /= g;
        s /= g;

        // Step 2: 检查最基本的无解情况 p > 4s
        if (p > 4 * s) {
            std::cout << -1 << std::endl;
            continue;
        }

        bool found = false;
        // Step 3: 遍历倍数 i
        for (int i = 1; s * i <= 50000; i++) {
            int k = s * i; // 目标面积
            int c = p * i; // 目标周长

            // Step 5: 检查周长是否为偶数
            if (c % 2 != 0) {
                continue;
            }

            int half = c / 2; // half = h + l

            // Step 6: 遍历 h, 从而确定 l
            for (int h = 1; h < half; h++) {
                int l = half - h;

                // Step 7: 检查面积 k 是否在可构造范围内
                // 面积不能比 h*l (填满) 还大
                if (h * l < k) {
                    continue;
                }
                // 面积不能比 L 型框架还小
                if (k < h + l - 1) {
                    continue;
                }

                // 找到解啦！喵~
                found = true;
                std::cout << k << std::endl;

                // Step 8.1: 构造 L 型框架的横臂
                for (int j = 1; j <= l; j++) {
                    std::cout << "1 " << j << std::endl;
                }
                // Step 8.2: 构造 L 型框架的竖臂
                for (int j = 2; j <= h; j++) {
                    std::cout << j << " 1" << std::endl;
                }

                // Step 8.3: 填充内部空间
                int remaining = k - (l + h - 1);
                for (int x = 2; x <= h; x++) {
                    for (int y = 2; y <= l; y++) {
                        if (remaining <= 0) {
                            break;
                        }
                        std::cout << x << " " << y << std::endl;
                        remaining--;
                    }
                    if (remaining <= 0) {
                        break;
                    }
                }
                break; // 找到一组 h, l 就够了
            }
            if (found) {
                break; // 找到一个 i 的解就够了
            }
        }

        if (!found) {
            std::cout << -1 << std::endl;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度: O(N * P * I) 的说。这里的 N 是最大面积，P 是最大 p。具体来说，外层循环 i 的次数约为 50000/s，内层循环 h 的次数约为 c/2 = p*i/2。虽然理论上的上界看起来很大，但在实际测试中，由于 p, s 较小，且能很快找到一个 i 和 h 比较小的解，所以程序运行得飞快，完全能通过！
• 空间复杂度: O(1) 的说。我们没有使用额外的数组来存储坐标，而是直接计算并输出，所以只用了几个变量，空间是常数级别的，非常环保呐！

知识点与总结

这真是一道结合了数论和构造思想的绝妙好题，让本喵玩得很开心！

1. 数论先行: 遇到比例问题，先用gcd化简是黄金法则！它能揭示问题最本质的结构。
2. 构造的艺术: "L型框架+填充"的策略非常强大。它成功地将周长和面积这两个变量在一定程度上解耦，给了我们足够的自由度来满足条件。这是构造题中一个非常值得学习的思路：先搭建一个满足部分条件（如周长）的骨架，再通过填充或修改来满足另一部分条件（如面积）。
3. 边界思维: 别忘了检查那些简单的边界情况，比如 p <= 4s 和周长为偶数。它们是高效的剪枝，能帮你过滤掉大量无解的搜索分支。

希望本喵的讲解能帮助你理解这道题的奥秘！多多练习这种构造题，你的思维会变得越来越灵活，就像猫咪一样敏捷哦！加油，喵~！