G. Gangsta - 题解

比赛与标签

比赛: Codeforces Round 1032 (Div. 3) 标签: data structures, divide and conquer, math, sortings 难度: *1900

喵喵，题目讲了什么呀？

主人你好呀~ 这道题目是这样的呐：

我们拿到一个由 '0' 和 '1' 组成的二进制字符串 s。对于 s 的任意一个子串 p（比如从第 l 个字符到第 r 个字符），我们要计算一个函数 f(p)。这个函数的值等于子串 p 中出现次数最多的那个字符的数量。比如说，对于 "00110"，'0' 出现了 3 次，'1' 出现了 2 次，所以 f(00110) = 3 啦。

我们的任务呢，就是要找出 s 的 所有 子串，对每个子串都计算出 f 值，然后把这些 f 值全部加起来，得到最终的总和！听起来是不是很有趣喵？

输入: 一个整数 n 表示字符串长度，和长度为 n 的二进制字符串 s。 输出: 所有子串 f 值的总和。

解题思路大揭秘喵~

嘿嘿，直接暴力枚举所有子串再计算 f 值肯定会超时的说！(>ω<) 所以我们需要找到更聪明的办法。让本猫娘带你一步步拆解这个问题吧！

第一步：一个神奇的数学变换！

我们要求的 f(p) 是 max(p中'0'的个数, p中'1'的个数)。 这里有一个超级好用的数学恒等式，一定要记住哦： max(a, b) = (a + b + |a - b|) / 2

把它用到我们的问题里就是： f(p) = ( (p中'0'的个数 + p中'1'的个数) + |p中'0'的个数 - p中'1'的个数| ) / 2

主人你看，p中'0'的个数 + p中'1'的个数 不就是子串 p 的长度 length(p) 嘛！ 所以，公式就变成了： f(p) = (length(p) + |count_0(p) - count_1(p)|) / 2

第二步：拆分任务，逐个击破！

现在，我们要计算所有子串的 f(p) 之和，也就是： Sum = Σ f(p) = Σ (length(p) + |count_0(p) - count_1(p)|) / 2

根据加法分配律，我们可以把这个大求和拆成两部分： Sum = (1/2) * [ Σ length(p) + Σ |count_0(p) - count_1(p)| ]

这样一来，问题就清晰多啦！我们只需要分别计算出 所有子串的长度总和 和 所有子串的(0的个数-1的个数)的绝对值总和，然后把它们加起来再除以2，就是答案啦！

第三步：计算所有子串的长度总和

Σ length(p) 是一个经典的组合数学问题。对于一个长度为 n 的字符串，它的所有子串的长度总和有一个漂亮的公式： Σ length(p) = n * (n + 1) * (n + 2) / 6 这个公式可以直接使用，能省下不少功夫呢！

第四步：计算差值的绝对值总和 (最关键的一步！)

接下来是重头戏：如何高效计算 Σ |count_0(p) - count_1(p)| 呢？

这里就要用到 前缀和 的思想了！我们把 '0' 看作 +1，'1' 看作 -1。然后创建一个前缀和数组 P。P[i] 表示字符串 s 的前 i 个字符中 ('0'的个数 - '1'的个数) 的值。为了方便处理，我们让 P[0] = 0。

这样，对于任何一个子串 s[l..r]（0-indexed），它的 count_0 - count_1 的值就等于 P[r+1] - P[l]。

所以，我们的目标就转化为了计算： Σ_{0 <= l <= r < n} |P[r+1] - P[l]|

这个式子看起来还是很复杂，因为它要枚举所有子串的左右端点。但其实它等价于计算 P 数组中 所有 数对 (P[i], P[j]) 且 i < j 的差的绝对值之和，即 Σ_{0 <= i < j <= n} |P[j] - P[i]|。

对付这个式子，有一个绝妙的技巧！

1. 首先，我们将前缀和数组 P (从 P[0] 到 P[n]) 从小到大排序。
2. 排序后，对于任意 i < j，都有 P[i] <= P[j]，所以 |P[j] - P[i]| 就等于 P[j] - P[i]，绝对值被消除了！
3. 现在我们要计算 Σ_{0 <= i < j <= n} (P[j] - P[i])。 我们可以统计每个 P[k] 被加了多少次、被减了多少次。
   • 对于每个 P[k]，当它作为 P[j] 时（即 j=k），它会被加上 k 次（因为 i 可以取 0, 1, ..., k-1）。
   • 当它作为 P[i] 时（即 i=k），它会被减去 (n-k) 次（因为 j 可以取 k+1, ..., n）。
   • 所以，P[k] 对总和的贡献是 P[k] * k - P[k] * (n-k) = P[k] * (2*k - n)。
4. 因此，总和就是 Σ_{k=0 to n} P[k] * (2*k - n)。

这正是代码中 total_abs 的计算方式！是不是超级巧妙呀？喵~

第五步：合并答案！

我们已经算出了 total_length_sum = Σ length(p) 和 total_abs = Σ |count_0(p) - count_1(p)|。 根据第二步的公式，最终答案就是： ans = (total_length_sum + total_abs) / 2

搞定收工！(๑•̀ㅂ•́)و✧

代码实现喵~

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

using namespace std;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    // 第一步：计算所有子串的长度总和
    // 公式：n * (n + 1) * (n + 2) / 6
    long long total_length_sum = (long long)n * (n + 1) * (n + 2) / 6;

    // 第二步：构建前缀差值数组 P
    // P[i] 表示前 i 个字符中 ('0'的个数 - '1'的个数)
    // '0' 计为 +1, '1' 计为 -1
    vector<long long> P(n + 1);
    P[0] = 0; // P[0] 代表空前缀，差值为 0
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            P[i + 1] = P[i] + 1;
        } else {
            P[i + 1] = P[i] - 1;
        }
    }

    // 第三步：对前缀差值数组进行排序
    sort(P.begin(), P.end());

    // 第四步：计算所有数对的绝对值差之和
    // 使用公式 Σ P[i] * (2*i - n)
    long long total_abs = 0;
    for (int i = 0; i <= n; i++) {
        // P[i] 在排序后的数组中，它比 i 个数大，比 n-i 个数小
        // 所以它作为较大数出现 i 次，作为较小数出现 n-i 次
        // 总贡献为 P[i] * i - P[i] * (n-i) = P[i] * (2*i - n)
        total_abs += P[i] * (2LL * i - n);
    }

    // 第五步：合并结果，得到最终答案
    // ans = (Σ length + Σ |diff|) / 2
    long long ans = (total_length_sum + total_abs) / 2;
    cout << ans << '\n';
}

int main() {
    // 优化输入输出，跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析的说

• 时间复杂度: O(N log N) 的说。 瓶颈在于对大小为 n+1 的前缀和数组 P 进行排序，这需要 O(N log N) 的时间。计算 total_length_sum、构建 P 数组以及计算 total_abs 都只需要 O(N) 的时间。所以总的时间复杂度由排序决定。

• 空间复杂度: O(N) 的说。 我们主要需要一个大小为 n+1 的 vector 来存储前缀和数组 P，所以空间开销是 O(N) 级别。

知识点与总结

这道题真是一次美妙的思维旅行呀！我们来总结一下学到了什么吧：

1. 问题转化: max(a, b) 到 (a+b+|a-b|)/2 的转化是本题的破局点！在处理 max 或 min 的求和问题时，这可是一个非常有用的工具喵。
2. 前缀和: 又是你，前缀和！它再一次展示了处理区间问题的强大能力。通过把 '0' 和 '1' 映射到 +1 和 -1，我们成功地用前缀和来表示任意子串的字符数之差。
3. 绝对值和的快速计算: 排序后利用 Σ P[i] * (2i - n) 的公式来计算 Σ |P[j] - P[i]| 是一个非常高效且优雅的技巧。这个方法值得每个追求算法之美的同学牢牢记住！
4. 组合数学公式: n(n+1)(n+2)/6 这个公式虽然不是解题的核心，但能熟练运用可以简化代码和思考过程。

总之，只要我们能把一个复杂的问题一步步分解，并运用合适的数学工具和算法技巧，就能找到这样漂亮又高效的解法哦！主人也要继续加油，探索更多算法的奥秘喵~ (´｡• ᵕ •｡`) ♡