Moe's CF Life

Appearance

E. Maximum Subsequence - 题解 ​

比赛与标签 ​

比赛: Educational Codeforces Round 32 标签: bitmasks, divide and conquer, meet-in-the-middle 难度: *1800

问题喵述~ ​

这道题目是这样子的喵：

我们有一个由 n 个整数组成的数组 a，还有一个整数 m。我们的任务是从数组 a 中挑选出一个子序列（也可以是空序列哦！），让这个子序列里所有元素的和对 m 取模后的值最大。最后，把这个最大的模 m 的值打印出来就好啦！

简单来说，就是要找到一个子序列，让它的 sum % m 最大，的说！

举个栗子：a = [5, 2, 4, 1]，m = 4。 如果我们选择子序列 {5, 2}，和是 7，7 % 4 = 3。 如果我们选择子序列 {4}，和是 4，4 % 4 = 0。 如果我们选择子序列 {5, 4, 1}，和是 10，10 % 4 = 2。 看起来，3 就是能得到的最大值了呢！

聪明的猫猫想到了... ​

看到这道题，咱的第一反应就是，要不……把所有可能的子序列都试一遍？

一个数组有 n 个元素，对于每个元素，我们都有“选”和“不选”两种选择。所以，总共的子序列数量就是 2^n 个，喵。

如果 n 很小，比如 n <= 20，那么 2^20 大约是一百万，计算机跑起来毫无压力。但是题目里说 n 最大可以到 35！2^35 是一个天文数字，咱的小爪子数不过来，电脑也肯定会超时的说！( TДT)

既然直接暴力不行，那肯定有更聪明的办法！当看到 n 在 40 左右，并且解法和指数相关时，一个非常强大的魔法就要登场啦——折半搜索 (Meet-in-the-Middle)！

这个魔法的咒语是：打不过就分两半打！

具体是这样做的喵：

  1. 分割数组：我们将 n 个元素分成几乎相等的两半。

    • 第一半：从 a[0] 到 a[n/2 - 1]
    • 第二半：从 a[n/2] 到 a[n-1] 这样，每一半的大小都约等于 n/2。对于 n=35，每一半的大小就是 17 或 18。2^18 大约是 26 万，这个计算量就非常可爱了！

  2. 分别计算：

    • 我们对第一半的元素进行暴力搜索，找出所有可能的子序列和，并对 m 取模。将这些结果存入一个列表，叫 sums1 吧。
    • 同样地，我们对第二半也做同样的操作，得到所有可能的子序列和（模 m），存入 sums2。

  3. 合并结果：现在，我们有了两份“半成品”。原数组的任何一个子序列的和，都可以看作是 sums1 中的一个数 s1 加上 sums2 中的一个数 s2 的结果（s1 和 s2 分别代表来自两半的子序列和）。我们的目标是找到一对 (s1, s2)，使得 (s1 + s2) % m 最大。

    怎么找呢？如果再暴力两两组合，那不就又回到 O(2^n) 了嘛！所以，这里的合并必须高效！

    我们可以先把 sums2 排序。然后，遍历 sums1 中的每一个元素 s1，对于当前的 s1，我们想在 sums2 中找到一个最佳的 s2。

    我们希望 s1 + s2 在模 m 意义下最大。有两种情况可以让结果变大：

    • 情况一：s1 + s2 不超过 m 为了让 s1 + s2 最大，我们希望 s2 尽可能大，但同时要满足 s2 < m - s1。在排好序的 sums2 中，我们可以用二分查找（比如 lower_bound）来寻找 m - s1 这个值。lower_bound 会找到第一个大于或等于 m - s1 的位置，那么它前一个元素就是我们想要的那个最大的、且小于 m - s1 的 s2 啦！此时的候选答案就是 s1 + s2。

    • 情况二：s1 + s2 超过 m 此时的和是 (s1 + s2) % m。为了让这个值最大，s1 + s2 的值应该“刚刚好”超过 m 或者 2m 等等。一个简单又有效的策略是，让 s1 和 sums2 中最大的那个元素 s2_max 相加，即 (s1 + s2_max) % m。这给了我们另一个候选答案。

    对于每个 s1，我们都计算这两个情况下的最大值，并和全局的最大值 max_val 比较，不断更新它。遍历完所有 s1 后，max_val 就是最终的答案啦！

整个过程就像两队猫猫分头探险，最后在中间的桥上汇合，交换情报，找出最佳宝藏路线一样，是不是很酷？这就是“中间相遇”的魅力所在，喵~

代码魔法展示喵~ ​

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

// 在 competitive programming 中很常见的写法，方便喵~
using namespace std;

// 这个函数用来生成一个数组片段所有可能的子序列和（对 m 取模）
// 它是用迭代的方式实现的，时间复杂度是 O(2^k)，其中 k 是这个片段的元素数量
void generate_sums(int start_idx, int end_idx, const vector<long long>& a, long long m, vector<long long>& sums) {
    sums.clear();
    sums.push_back(0); // 空子序列的和是 0，这是很重要的初始状态！

    // 遍历指定范围内的每个元素
    for (int i = start_idx; i < end_idx; ++i) {
        int current_size = sums.size();
        // 对于当前已经存在的所有和，都加上新元素 a[i] 形成新的和
        for (int j = 0; j < current_size; ++j) {
            sums.push_back((sums[j] + a[i]) % m);
        }
    }
}

int main() {
    // 快速 I/O，让程序跑得快一点~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long m;
    cin >> n >> m;

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

    // 这就是折半搜索的核心！把数组分成两半
    int n1 = n / 2;
    vector<long long> sums1, sums2;

    // 生成第一半的所有子序列和
    generate_sums(0, n1, a, m, sums1);
    
    // 生成第二半的所有子序列和
    generate_sums(n1, n, a, m, sums2);

    // 将第二半的和排序，这样我们才能用二分查找来加速！
    sort(sums2.begin(), sums2.end());
    // 去重是一个小优化，虽然不是必须的，但如果重复的和很多，可以提高效率
    sums2.erase(unique(sums2.begin(), sums2.end()), sums2.end());

    long long max_val = 0;

    // 遍历第一半的每一个和 s1，去第二半中寻找最佳搭档 s2
    for (long long s1 : sums1) {
        // 我们想要最大化 (s1 + s2) % m
        
        // 情况1: s1 + s2 < m。
        // 我们需要找到一个最大的 s2，使得 s2 < m - s1
        long long target = m - s1;
        // lower_bound 找到第一个 >= target 的元素
        auto it = lower_bound(sums2.begin(), sums2.end(), target);
        
        // 如果 it 不是开头，说明存在比 target 小的元素
        // it 前面的那个元素就是小于 target 的最大元素
        if (it != sums2.begin()) {
            long long s2 = *(it - 1);
            max_val = max(max_val, s1 + s2);
        }

        // 情况2: s1 + s2 >= m。
        // (s1 + s2) % m 的值要大的话，一个很好的选择是让 s2 取最大值
        // 这样 s1 + s2 的和也最大，取模后可能成为最优解
        if (!sums2.empty()) {
            long long s2_max = sums2.back();
            max_val = max(max_val, (s1 + s2_max) % m);
        }
    }
    
    // 上面的逻辑已经覆盖了最优解只在第一半（s2=0）或只在第二半（s1=0）的情况
    // 因为 sums1 和 sums2 都包含了0（空子序列的和）

    cout << max_val << endl;

    return 0;
}

时间与空间的魔法消耗 ​

  • 时间复杂度: O(n * 2^(n/2)) 的说

    • 生成 sums1 和 sums2 的时间都是 O(2^(n/2))。
    • 对 sums2 排序的时间是 O(2^(n/2) * log(2^(n/2)))，也就是 O(n * 2^(n/2))。
    • 最后合并的循环，对于 sums1 中的 O(2^(n/2)) 个元素，每个都对 sums2 进行一次二分查找，耗时 O(log(2^(n/2))) = O(n)。所以这部分总时间是 O(2^(n/2) * n)。
    • 综上，总的时间复杂度由最慢的部分决定，就是 O(n * 2^(n/2)) 啦！对于 n=35 来说，完全可以接受！

  • 空间复杂度: O(2^(n/2)) 的说

    • 我们需要额外的空间来存储 sums1 和 sums2，它们的大小最多是 2^(n/2)。所以空间复杂度就是 O(2^(n/2))。

猫猫的小课堂时间~ ​

今天我们学会了一个超级有用的技巧：折半搜索（Meet-in-the-Middle）！

核心思想 ​

它是一种分治思想的体现，专门用来对付那些朴素解法是指数级别 O(c^n) 且 n 不算太大（比如 30 到 45 之间）的问题。通过将问题一分为二，把复杂度降为 O(n * c^(n/2))，从而化不可能为可能。

适用场景 ​

当你发现一个问题，它的解可以由两部分独立生成的状态组合而成，并且直接枚举所有状态 O(c^n) 会超时的时候，就应该立刻想到这个方法！比如一些子集和、路径计数等问题。

本题技巧总结 ​

  1. 识别信号：n <= 35 + 求子集和问题 = 强烈的折半搜索信号！
  2. 分割：将数组分为两半。
  3. 生成：暴力生成两半的所有子集和（模 m）。
  4. 合并：最关键的一步！通过排序+二分查找，为第一半的每个和 s1，在第二半中高效地寻找能使 (s1 + s2) % m 最大化的 s2。别忘了考虑 s1+s2 < m 和 s1+s2 >= m 两种情况！

希望这次的讲解能帮助到你，喵~ 算法的世界充满了无限的乐趣和挑战，只要我们用心思考，总能找到像“折半搜索”这样优雅又强大的魔法！下次再遇到难题，也请不要放弃，和我一起加油吧！Nya~ ✨

Released under the MIT License.

Copyright © 2024-present Moe