CF2072B 题解

1. 题目分析

题意简述

给定一个只含 - 和 _ 的字符串，可以任意重排字符。重排后，统计等于 -_- 的不同子序列个数，要求这个数量最大。

难点剖析

子序列 -_- 需要两个 - 和一个 _，并且 _ 必须位于这两个 - 中间。重排时我们只需要关心两类字符的数量，而不用关心原字符串顺序。

设 - 的数量为 $c$，_ 的数量为 $u$。如果某个 _ 左边有 $L$ 个 -，右边有 $R$ 个 -，那么它作为中间字符可以贡献 $L \times R$ 个 -_- 子序列。

2. 从暴力到正解

策略一：小数据暴力 / 部分分

当 $n$ 很小时，可以枚举所有不同的重排，然后对每个重排统计 -_- 子序列数量，取最大值。

统计一个固定字符串时，可以枚举中间的 _，计算它左边和右边的 - 数量，累加贡献。

这种做法的复杂度主要来自重排枚举，最坏接近 $O(n!)$，只能处理很小的 $n$。

策略二：观察贡献形式

暴力的瓶颈在于枚举了大量本质相同的排列。实际上，对于每个 _ 来说，它的贡献只由左侧 - 数量和右侧 - 数量决定。

为了让所有 _ 的贡献尽可能大，最优策略是把所有 _ 放在一起，并放在两段 - 中间：

-----_____----

此时每个 _ 的贡献都相同，等于左侧 - 数量乘右侧 - 数量。

剩下的问题变成：把 $c$ 个 - 分成左右两组，最大化 $L(c-L)$。当两边尽量平均时乘积最大，所以：

$$L = \left\lfloor \frac c2 \right\rfloor,\quad R = \left\lceil \frac c2 \right\rceil$$

3. 正解思路

如何想到正解

目标子序列固定为 -_-，中间字符只能是 _。因此先固定一个 _，它能和左边任意一个 -、右边任意一个 - 组成答案。要最大化总数，就要让每个 _ 都拥有尽可能多的左右 - 组合。

把 _ 分散开不会比把它们集中在同一个最佳位置更优，因为每个 _ 都希望同样的左右 - 划分达到最大乘积。

算法步骤

1. 统计字符串中 - 的数量 $c$ 和 _ 的数量 $u$。
2. 将 $c$ 个 - 尽量平均分成左右两边：
   • 左边数量为 $\left\lfloor c/2 \right\rfloor$；
   • 右边数量为 $c-\left\lfloor c/2 \right\rfloor$。
3. 每个 _ 的最大贡献为左右数量乘积。
4. 总答案为：

$$u \times \left\lfloor \frac c2 \right\rfloor \times \left\lceil \frac c2 \right\rceil$$

正确性说明

对于任意排列，设某个 _ 左边有 $L$ 个 -，右边有 $R$ 个 -，则 $L+R=c$，该 _ 的贡献为 $LR$。在 $L+R$ 固定时，$LR$ 在两数尽量接近时最大。

因此单个 _ 的贡献不超过 $\left\lfloor c/2 \right\rfloor\left\lceil c/2 \right\rceil$。所有 _ 的总贡献也不超过这个上界乘以 $u$。

将所有 _ 放在两段尽量均分的 - 中间时，每个 _ 都恰好达到这个最大贡献，所以上界可以取到，算法正确。

复杂度分析

每组测试用例只需要扫描一次字符串。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

4. 参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;

        // 统计两种字符的数量。
        long long dash = 0, under = 0;
        for (char ch : s) {
            if (ch == '-') {
                ++dash;
            } else {
                ++under;
            }
        }

        // 把所有 '-' 尽量平均分到 '_' 的左右两侧。
        long long left = dash / 2;
        long long right = dash - left;

        // 每个 '_' 都贡献 left * right 个 "-_-" 子序列。
        cout << under * left * right << '\n';
    }

    return 0;
}