E. Romantic Glasses - 题解

比赛与标签

比赛: Codeforces Round 918 (Div. 4) 标签: data structures, greedy, math 难度: *1300

喵喵，这题说什么呀？

主人，你好喵~！这道题讲的是一个叫 Iulia 的女孩和她的约会对象一起喝果汁的故事，听起来很浪漫，但规矩好奇怪哦！(ฅ'ω'ฅ)

他们面前有一排 n 杯果汁，第 i 杯有 a_i 毫升。

• Iulia 只喝奇数位置上的果汁。
• 她的约会对象只喝偶数位置上的果汁。

Iulia 想找到一个连续的区间（比如从第 l 杯到第 r 杯），在这个区间里，她喝到的果汁总量和她的约会对象喝到的果汁总量完全相等。

我们的任务就是帮她判断，是否存在这样一个神奇的区间。如果存在，就输出 "YES"，否则就输出 "NO"，的说。

举个例子喵：如果果汁是 [1, 3, 2]，我们选 l=1, r=3 这个区间。

• Iulia 喝第 1 杯和第 3 杯，总量是 1 + 2 = 3。
• 她的约会对象喝第 2 杯，总量是 3。
• 哎呀，相等了！所以答案是 "YES" 喵~！

本喵的奇思妙想~✨

嘿嘿，这个问题看起来有点复杂，但只要我们稍微变个戏法，它就会变得非常简单哦！

首先，我们把题目要求的条件翻译成数学语言： 在子数组 a[l...r] 中，奇数位置的元素和 == 偶数位置的元素和

把等式移项一下，就变成了： 奇数位置的元素和 - 偶数位置的元素和 == 0

看到这个 ... - ... = 0 的形式，本喵的直觉就告诉我，可以搞点事情！呐，我们来施展一个魔法喵！我们创造一个新的数组 b：

• 如果原来的位置 i 是奇数，那么 b_i = a_i。
• 如果原来的位置 i 是偶数，那么 b_i = -a_i（把它变成负数！）。

经过这个魔法变换后，奇数和 - 偶数和 就变成了新数组 b 中对应区间的所有元素之和！

所以，问题就转化为了： 在新数组 b 中，是否存在一个连续子数组，其和为 0？

是不是瞬间就清晰了呀？寻找和为 0 的子数组，这可是前缀和算法的经典应用场景！

接下来就是前缀和的 show time 啦！( •̀ ω •́ )✧

1. 我们计算数组 b 的前缀和。设 P[k] 是 b 数组从第 1 个元素到第 k 个元素的和。
2. 一个子数组 b[l...r] 的和就等于 P[r] - P[l-1]。
3. 我们想让这个和为 0，也就是说 P[r] - P[l-1] = 0，即 P[r] == P[l-1]。

这说明，我们只需要检查是否存在两个不同的位置 i 和 j（i < j），使得它们的前缀和相等！

要实现这个，我们可以这样做：

• 创建一个集合（std::set 或 std::unordered_set），用来存放我们已经计算过的所有前缀和。
• 先在集合里放一个 0。这个 0 非常重要哦！它代表一个空的前缀（在数组开始之前），对应着那些从数组开头 l=1 就满足条件的子数组。因为此时 P[r] = P[l-1] = P[0] = 0。
• 然后，我们从头到尾遍历数组，一边计算当前的前缀和 current_sum。
• 每算出一个 current_sum，就去集合里查一下：这个 current_sum 以前出现过吗？
  • 如果出现过，太棒了！我们找到了 P[r] == P[l-1] 的情况，说明存在一个和为 0 的子数组。马上输出 "YES" 并结束！
  • 如果没出现过，就把这个新的 current_sum 加入到集合中，然后继续向后遍历。
• 如果遍历完整个数组都没有找到相等的前缀和，那就说明不存在这样的子数组，输出 "NO"。

这个方法是不是既聪明又高效呀，喵~？

看本喵敲代码喵！

#include <iostream>
#include <vector>
#include <numeric>
#include <set>

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 题目要求找到一个子数组 [l, r]，其中奇数位置的和等于偶数位置的和。
    // 这等价于：sum(奇数位) - sum(偶数位) = 0。
    //
    // 我们可以把这个问题转化一下，喵~
    // 创建一个新数组 b，如果 i 是奇数（1-based），b_i = a_i；如果 i 是偶数（1-based），b_i = -a_i。
    // 这样，原问题就变成了在新数组 b 中找一个和为 0 的连续子数组。
    //
    // 找和为 0 的子数组，可以用前缀和解决！
    // 如果子数组 b[l...r] 的和为 0，那么 P[r] - P[l-1] = 0，也就是 P[r] == P[l-1]。
    // P[k] 表示 b 数组的前 k 项和。
    // 我们只需要遍历数组，记录出现过的所有前缀和，如果发现当前前缀和已经出现过，就说明找到了！
    //
    // 注意喵：代码实现用的是 0-based 索引。
    // 1-based 的奇数位 i -> 0-based 的偶数位 i-1
    // 1-based 的偶数位 i -> 0-based 的奇数位 i-1
    // 所以，我们对 0-based 索引为偶数的项取正，为奇数的项取负。

    std::set<long long> seen_sums;
    // 预先插入 0，处理从数组开头就满足条件的子数组（即 P[r] = 0 的情况）。
    seen_sums.insert(0); 

    long long current_sum = 0;
    bool found = false;

    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) { // 0-based 偶数索引 (对应 1-based 奇数位置)
            current_sum += a[i];
        } else { // 0-based 奇数索引 (对应 1-based 偶数位置)
            current_sum -= a[i];
        }

        // 检查当前的前缀和是否在集合中出现过
        if (seen_sums.count(current_sum)) {
            // 如果出现过，说明我们找到了一个和为 0 的子数组！
            found = true;
            break;
        }
        // 否则，把当前的前缀和加入集合
        seen_sums.insert(current_sum);
    }

    if (found) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

跑得快不快呀？

• 时间复杂度: O(N log N) 的说。 我们只把数组从头到尾遍历了一遍，这是 O(N) 的。在循环里，我们对 std::set 进行了查找 (count) 和插入 (insert) 操作。因为 std::set 内部是红黑树实现的，所以这些操作的复杂度都是 O(log k)，其中 k 是集合中元素的数量（最多为 N）。所以总的时间复杂度就是 O(N log N) 啦。如果主人换成 std::unordered_set（哈希表），平均时间复杂度可以优化到 O(N) 哦！

• 空间复杂度: O(N) 的说。 在最坏的情况下，所有的前缀和都互不相同，我们需要把它们全部存到 seen_sums 集合里。所以，集合最大可能需要存储 N+1 个元素（包括初始的0），空间复杂度就是 O(N) 喵。

这次学到了什么喵？

这道题真是个很好的例子，告诉我们如何化繁为简，喵~

1. 核心思想：问题转化 最关键的一步就是把 sum(odd) == sum(even) 这个看起来有点麻烦的条件，通过引入负号，转化成了标准的**“寻找和为0的子数组”**问题。这是算法竞赛中一个超级有用的技巧，能让复杂的问题变得清晰明了！

2. 关键算法：前缀和 + 集合/哈希表 “前缀和”是解决子数组和相关问题的利器。而“哈希表”或“集合”则是检查“某个东西是否出现过”的绝佳工具。将它们组合起来，就能高效地解决“寻找特定和的子数组”这类问题。

3. 实现细节：别忘了那个0！ 在用前缀和解决这类问题时，千万别忘了初始化时加入的那个 0。它代表了空前缀，是处理从数组头部开始的子数组的关键，少了这个小细节可是会出错的哦！

掌握了前缀和的魔法，再配上灵活的思维，很多题目都会向主人你屈服的！继续加油，下一个难题也一定能轻松解决的，喵~！(≧∇≦)ﾉ