E. Magic Stones - 题解

比赛与标签

比赛: Codeforces Global Round 1 标签: constructive algorithms, math, sortings 难度: *2200

题目大意喵~

主人，你好呀！这道题是这样的喵~

我们有两排魔法石，每排都有 n 个。第一排是格里高利（Grigory）的，石头们的魔力值是 c_1, c_2, ..., c_n。第二排是安德鲁（Andrew）的，魔力值是 t_1, t_2, ..., t_n。

格里高利可以对他的石头施展一种魔法：选择一个中间的石头（也就是编号 i 满足 2 ≤ i ≤ n-1 的石头），然后这个石头的魔力值 c_i 就会变成 c'_i = c_{i+1} + c_{i-1} - c_i。这个魔法可以施展任意多次。

我们的任务就是判断，格里高利能不能通过一系列魔法，把他那排石头的魔力值变得和安德鲁那排完全一样呢？如果可以，就输出 "Yes"，不然就输出 "No"，很简单对吧，喵~

寻找不变量的魔法！

这道题看起来操作很神秘，c_i 变成 c_{i+1} + c_{i-1} - c_i，好像很复杂的样子，让人头大呢... 但是别怕！我们猫娘最擅长发现藏在复杂外表下的简单规律了，喵~

不会动的石头

首先，我们来观察一下魔法的限制。魔法只能对中间的石头施展，也就是索引从 2 到 n-1 的石头。这意味着什么呢？这意味着 c_1 和 c_n 这两块位于两端的石头，是永远不会被选中的，它们的魔力值也永远不会改变！

所以，如果格里高利的石头能变成安德鲁的石头，一个最最基本的前提就是，它们两端的石头魔力值必须一开始就相同！

必要条件 1: c_1 == t_1 并且 c_n == t_n。如果这个条件不满足，那肯定变不成，可以直接说 "No" 啦！

差分的奇迹

好，现在我们假设两端的石头已经一样了，再来看看中间的操作。c'_i = c_{i+1} + c_{i-1} - c_i 这个式子到底藏着什么秘密呢？

直接看数值的变化太乱了，我们不妨换个角度，看看相邻石头之间的差值会发生什么变化。我们定义一个差分数组 d，其中 d_i = c_{i+1} - c_i。

当对第 i 个石头（2 ≤ i ≤ n-1）施法后，我们看看新的差分值变成了什么：

原来的差分 d_{i-1} 是 c_i - c_{i-1}。
原来的差分 d_i 是 c_{i+1} - c_i。

施法后，第 i 个石头的魔力值变成了 c'_i。我们来计算新的差分：

新的 d'_{i-1} 是 c'_i - c_{i-1} = (c_{i+1} + c_{i-1} - c_i) - c_{i-1} = c_{i+1} - c_i。
新的 d'_i 是 c_{i+1} - c'_i = c_{i+1} - (c_{i+1} + c_{i-1} - c_i) = c_i - c_{i-1}。

喵！你发现了吗？

新的 d'_{i-1} 正好等于旧的 d_i！
新的 d'_i 正好等于旧的 d_{i-1}！

这说明，对第 i 个石头施法，本质上就是交换了它左边的差值 d_{i-1} 和右边的差值 d_i！

魔法的真相

我们可以在 i 从 2 到 n-1 的任何一个位置施法，这就意味着我们可以交换任何一对相邻的差分值 d_{i-1} 和 d_i。熟悉排序算法的小伙伴们肯定立刻就想到了，如果我们可以交换任意相邻的元素，那就等同于我们可以对这个序列进行任意的排列组合！就像冒泡排序一样，通过不断交换相邻元素，我们可以得到任何我们想要的顺序，喵~

所以，魔法的真相就是：我们可以任意排列 c 数组的差分序列 (c_2-c_1, c_3-c_2, ..., c_n-c_{n-1})！

那么，c 数组能变成 t 数组的充要条件就是：

两端点值相同：c_1 == t_1 和 c_n == t_n。
c 数组的差分序列和 t 数组的差分序列，包含的元素（作为一个多重集）是完全相同的。

如何判断两个多重集是否相同呢？最简单的办法就是把它们都排个序，然后看看排序后的序列是不是一模一样！

最终的解题步骤

总结一下我们的策略，喵~

检查 c[0] 是否等于 t[0]，以及 c[n-1] 是否等于 t[n-1]。如果任意一个不相等，直接输出 "No"。
创建一个新的数组 diff_c，存放 c 数组的差分值，即 c[i] - c[i-1]（对于 i 从 1 到 n-1）。
同样地，创建数组 diff_t，存放 t 数组的差分值。
将 diff_c 和 diff_t 两个数组进行排序。
比较排序后的 diff_c 和 diff_t 是否完全相同。如果相同，输出 "Yes"；否则，输出 "No"。

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 使用C++标准库的快速IO，让程序跑得更快喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<long long> c(n), t(n);

    // 读入格里高利的石头魔力值
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    // 读入安德鲁的石头魔力值
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    // 第一步：检查两端的石头喵~ 它们是不会动的哦！
    // 如果起点或终点不匹配，那就不可能转换成功。
    if (c[0] != t[0] || c[n - 1] != t[n - 1]) {
        cout << "No" << endl;
        return 0;
    }

    // 第二步：计算差分数组，这是魔法的关键所在！
    vector<long long> diff_c, diff_t;
    for (int i = 1; i < n; i++) {
        // 计算 c 数组的差分
        diff_c.push_back(c[i] - c[i - 1]);
        // 计算 t 数组的差分
        diff_t.push_back(t[i] - t[i - 1]);
    }

    // 第三步：把差分数组排个序
    // 这样我们就能比较它们是不是拥有相同的元素集合了，喵~
    sort(diff_c.begin(), diff_c.end());
    sort(diff_t.begin(), diff_t.end());

    // 第四步：比较排序后的差分数组
    // 如果完全一样，那就说明可以转换成功！
    if (diff_c == diff_t) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

复杂度分析

时间复杂度: O(N log N) 的说。我们首先需要 O(N) 的时间来读取输入和计算两个差分数组。之后，我们需要对两个大小为 N-1 的差分数组进行排序，这部分的时间复杂度是 O(N log N)。最后比较两个排序好的数组需要 O(N) 的时间。所以总的时间复杂度由排序决定，是 O(N log N) 呐。
空间复杂度: O(N) 的说。我们需要额外的空间来存储 c 和 t 两个原始数组，以及 diff_c 和 diff_t 两个差分数组。这些都需要 O(N) 的空间。

知识点与总结 🐾

这真是一道有趣的题目，喵！它教会了我们一个非常重要的思想：

寻找不变量 (Invariant): 当题目中的操作看起来很复杂时，试着去寻找在操作过程中保持不变的量。在这道题里，虽然石头的值在变，但差分数组的多重集是不变的（只是顺序可以变）。找到不变量往往是解开这类构造题或博弈题的钥匙！
差分思想 (Difference Array): 这是一个非常有用的技巧！将问题从关注数值本身转移到关注数值之间的关系（如差、和、比等），有时能极大地简化问题。这道题就是差分思想的完美应用。
多重集相等性判断: 判断两个集合/多重集是否相等，一个通用且高效的方法就是将它们的元素排序后进行比较。

下次再遇到这种变换来变换去的题目，不要慌张，静下心来，像猫咪一样敏锐地观察，看看能不能找到那个藏在背后的“不变量”哦！加油，你一定可以的，喵~！

E. Magic Stones - 题解 ​

比赛与标签 ​

题目大意喵~ ​

寻找不变量的魔法！ ​

不会动的石头 ​

差分的奇迹 ​

魔法的真相 ​

最终的解题步骤 ​

代码实现喵~ ​

复杂度分析 ​

知识点与总结 🐾 ​