传送门：洛谷 CF2072B Having Been a Treasurer in the Past, I Help Goblins Deceive | Codeforces B. Having Been a Treasurer in the Past, I Help Goblins Deceive

更佳的阅读体验：CF2072B 题解

简要题意：给定字符串只包含减号 - 和下划线 _ 的字符串 $s$，重新排列 $s$ 中的所有字符，使得 $s$ 中组成字符串 -_- 的子序列数量最大，并输出这个数量。

-_- 只有中间有一个下划线 _。为了保证这样的子序列一定存在，下划线 _ 一定是位于重新排列的字符串的中间位置的，即下划线 _ 左右两端一定都有减号 -。

根据均值不等式，我们知道当左右两侧的减号 - 数量尽可能相等时，他们的乘积最大。

又根据乘法原理，我们知道最终的子序列数量为左侧减号 - 的数量、右侧减号 - 的数量与下划线 _ 数量的乘积。

因此，我们只需要统计减号 - 和下划线 _ 的乘积，即可求出答案。

#include <iostream>
using namespace std;

int t, n, cnt[2];
char c;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        cnt[0] = cnt[1] = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> c, ++cnt[c == '-'];
        cout << 1ll * (cnt[1] >> 1) * cnt[0] * ((cnt[1] + 1) >> 1) << '\n';
    } return 0;
}