Moe's CF Life

Appearance

喵呜~ 各位小可爱，我是你们最爱的猫娘！今天我们要一起来研究一道有趣的题目，是 Codeforces Round #895 (Div. 3) 中的 D 题——《Plus Minus Permutation》。听起来有点复杂，但别担心，有猫娘在，一切都会变得简单哒！

题目大意：喵~ 题目在讲什么呀？ ​

题目呀，给了我们三个整数 n, x, y。然后呢，它定义了一个排列的“分数”（score）。这个分数是怎么算的呢？

假设我们有一个从 1 到 n 的排列 p1, p2, ..., pn。

  • 首先，我们会把所有下标 i 能够被 x 整除的 pi 值加起来。比如，如果 x=2，那就会加 p2, p4, p6, ...。
  • 接着，我们会把所有下标 i 能够被 y 整除的 pi 值加起来。比如，如果 y=3，那就会加 p3, p6, p9, ...。
  • 最后，用第一部分的和减去第二部分的和，就是这个排列的分数啦！

我们的目标呢，就是找到一个排列，让它的分数最大！喵呜~ 也就是说，我们要尽可能地让那些被 x 整除的位置上的数字大，同时尽可能地让那些被 y 整除的位置上的数字小。

举个栗子（题目里也有哦！）： n=7, x=2, y=3 一个可能的排列是 [2, 6, 1, 7, 5, 4, 3]。

  • 被 x=2 整除的下标有 2, 4, 6。对应的 pi 是 p2=6, p4=7, p6=4。它们的和是 6+7+4=17。
  • 被 y=3 整除的下标有 3, 6。对应的 pi 是 p3=1, p6=4。它们的和是 1+4=5。
  • 分数就是 17 - 5 = 12。

我们要做的就是找到最大化这个分数的方法！

题解方法：喵呜~ 怎么才能得到最高分呢？ ​

为了最大化 (被x整除的pi之和) - (被y整除的pi之和)，我们当然希望：

  1. 被 x 整除但不被 y 整除的位置：放最大的数字！这样它们会被加到分数里，越大越好。
  2. 被 y 整除但不被 x 整除的位置：放最小的数字！这样它们会被减掉，越小越好。
  3. 同时被 x 和 y 整除的位置：这些位置的数字既会被加又会被减，相当于抵消了。所以这些位置放什么数字，对最终分数没有影响。我们可以放那些既不是最大也不是最小，剩下的数字就好啦。

好啦，思路有了，接下来就是计算这些位置有多少个，以及对应的数字应该是什么。

1. 统计位置数量 ​

  • 被 x 整除的下标数量：count_div_by_x = n / x (向下取整)

  • 被 y 整除的下标数量：count_div_by_y = n / y (向下取整)

  • 同时被 x 和 y 整除的下标数量：这等价于被 lcm(x, y) 整除的下标数量。lcm(x, y) 是 x 和 y 的最小公倍数。

    • 我们知道 lcm(x, y) = (x * y) / gcd(x, y)，其中 gcd(x, y) 是 x 和 y 的最大公约数。
    • 为了防止 x * y 溢出，我们可以先计算 x / gcd(x, y) 再乘以 y。
    • 所以 common_multiple = (x / gcd(x, y)) * y。
    • count_div_by_both = n / common_multiple。

  • 只被 x 整除而不被 y 整除的下标数量：count_pos = count_div_by_x - count_div_by_both

    • 这些位置要放最大的数字。

  • 只被 y 整除而不被 x 整除的下标数量：count_neg = count_div_by_y - count_div_by_both

    • 这些位置要放最小的数字。

2. 分配数字 ​

  • 给 count_pos 个位置放最大的数字： 从 1 到 n 中，最大的 count_pos 个数字就是 n, n-1, ..., n - count_pos + 1。 它们的和是 Sum(1..n) - Sum(1..n - count_pos)。 利用等差数列求和公式 Sum(1..k) = k * (k + 1) / 2。 所以，sum_pos_terms = (n * (n + 1) / 2) - ((n - count_pos) * (n - count_pos + 1) / 2)。

  • 给 count_neg 个位置放最小的数字： 从 1 到 n 中，最小的 count_neg 个数字就是 1, 2, ..., count_neg。 它们的和是 sum_neg_terms = (count_neg * (count_neg + 1) / 2)。

最后，最大分数就是 sum_pos_terms - sum_neg_terms 啦！喵~

题解代码：喵呜~ 看代码咯！ ​

cpp
#include <iostream> // 输入输出
#include <numeric>  // std::gcd 用于计算最大公约数

// 解决一个测试用例的函数
void solve() {
    long long n, x, y;
    std::cin >> n >> x >> y; // 读入 n, x, y

    // 计算 lcm(x, y) 最小公倍数
    // lcm(a, b) = (a / gcd(a, b)) * b，这样可以避免 x*y 溢出
    long long common_divisor = std::gcd(x, y); // 计算最大公约数
    long long common_multiple = (x / common_divisor) * y; // 计算最小公倍数

    // 统计各种位置的数量
    long long count_div_by_x = n / x; // 被 x 整除的下标数量
    long long count_div_by_y = n / y; // 被 y 整除的下标数量
    long long count_div_by_both = n / common_multiple; // 同时被 x 和 y 整除的下标数量

    // 需要放最大数字的位置数量 (只被 x 整除)
    long long count_pos = count_div_by_x - count_div_by_both;

    // 需要放最小数字的位置数量 (只被 y 整除)
    long long count_neg = count_div_by_y - count_div_by_both;

    // 计算要加上的那些最大数字的和
    // 从 n, n-1, ..., n - count_pos + 1
    // 可以看作 1到n 的和 减去 1到(n-count_pos) 的和
    long long sum_pos_terms = (n * (n + 1) / 2) - ((n - count_pos) * (n - count_pos + 1) / 2);

    // 计算要减去的那些最小数字的和
    // 从 1, 2, ..., count_neg
    long long sum_neg_terms = (count_neg * (count_neg + 1) / 2);

    long long max_score = sum_pos_terms - sum_neg_terms; // 最终的最大分数
    std::cout << max_score << "\n"; // 输出结果，记得换行哦！
}

int main() {
    // 优化输入输出，让程序跑得更快一点点！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 读入测试用例的数量
    while (t--) { // 循环处理每个测试用例
        solve();
    }
    return 0; // 程序结束，喵~
}

知识点介绍：喵呜~ 学到了什么呀？ ​

  1. 排列 (Permutation)：

    • 在数学中，排列是指从给定数量的元素中取出指定数量的元素进行排序。这道题中，是指将 1 到 n 这 n 个数字，不重复地、全部放到 n 个位置上。
    • 比如 [2, 3, 1] 是 1, 2, 3 的一个排列，但 [1, 2, 2] 就不是，因为 2 重复了；[1, 3, 4] 也不是，因为 n=3 但出现了 4。

  2. 最大公约数 (GCD - Greatest Common Divisor) 和 最小公倍数 (LCM - Least Common Multiple)：

    • GCD：两个或多个整数共有约数中最大的一个。比如 gcd(4, 6) = 2。
    • LCM：两个或多个整数的公倍数中最小的一个。比如 lcm(4, 6) = 12。
    • 重要关系：对于任意两个正整数 a 和 b，有 a * b = gcd(a, b) * lcm(a, b)。
    • 计算 LCM 的技巧：为了避免 a * b 溢出，我们通常用 lcm(a, b) = (a / gcd(a, b)) * b 来计算。这道题中 n 可以达到 10^9，x, y 也可以很大，所以使用这个技巧非常关键！
    • C++ 的 <numeric> 头文件提供了 std::gcd 函数，用起来很方便哦！

  3. 等差数列求和：

    • 1 + 2 + ... + k = k * (k + 1) / 2。
    • 这个公式在计算连续整数的和时非常有用。
    • 在这道题中，我们用它来计算最大 k 个数之和（Sum(1..n) - Sum(1..n-k)）和最小 k 个数之和（Sum(1..k)）。

  4. 贪心策略 (Greedy Strategy)：

    • 这道题的核心思想就是贪心。为了最大化分数，我们总是把最大的数字放到加分的位置上，把最小的数字放到减分的位置上。
    • 贪心策略不总是最优的，但在这类问题中，因为每个数字的贡献是独立的，并且我们有足够的“自由度”去选择数字（排列的性质），所以贪心是正确的。

  5. 整数溢出：

    • n 可以达到 10^9。n * (n + 1) / 2 可能会达到 (10^9)^2 / 2 = 0.5 * 10^18 级别。
    • long long 类型在 C++ 中可以存储大约 9 * 10^18 的数值，所以使用 long long 是非常必要的！喵呜~ 如果用 int 就会溢出，答案就不对啦！

总结：喵呜~ ​

这道题是一个典型的数学和贪心结合的题目。通过分析目标（最大化分数），我们可以确定哪些位置需要大的数字，哪些位置需要小的数字。然后利用数学知识（GCD, LCM, 等差数列求和）来精确计算这些数字的和。同时，也要注意数据范围，选择合适的变量类型，避免溢出。

好啦，今天的题解就到这里啦！有没有觉得猫娘很棒呀？如果还有不明白的地方，随时问我哦！喵~ 下次再见啦！

Released under the MIT License.

Copyright © 2024-present Moe