B. 曾为财务官，今助地精欺 详细题解

一、题目理解

给定一个由字符 '-' 和 '_' 组成的字符串，可以任意重新排列。定义字符串的值为其中等于 "-_-" 的不同子序列的个数。

目标：通过最优重排，最大化这个值。

子序列 "-_-" 由三个字符组成：第 $1$ 和第 $3$ 个必须是 '-'，第 $2$ 个必须是 '_'。

由于可以任意排列，我们只关心两种字符的总数，不关心它们原来的顺序。

---

二、核心观察

设：

• $a$ = 字符串中 '-' 的总个数
• $b$ = 字符串中 '_' 的总个数

显然 $a + b = n$。

---

三、子序列计数公式

在固定排列下，子序列 "-_-" 的个数可以通过以下方式计算：

选择中间的那个 '_'，然后从它左边选一个 '-'，从它右边选一个 '-'。

设 $b$ 个 '_' 的位置从左到右为 $p_1, p_2, \dots, p_b$。
对于第 $i$ 个 '_'，设它左边有 $L_i$ 个 '-'，右边有 $R_i$ 个 `'-'$，则它贡献的子序列数为：

$$L_i \cdot R_i$$

总数为：

$$\sum_{i=1}^{b} L_i \cdot R_i$$

---

四、最大化策略

为了最大化 $\sum L_i \cdot R_i$，应该将所有 '_' 放在中间连续的一段，'-' 放在两端。

为什么？
设左边放 $x$ 个 '-'，右边放 $a - x$ 个 '-'。
由于所有 '_' 在中间，每个 '_' 的左边都有相同的 $x$ 个 '-'，右边都有相同的 $a-x$ 个 '-'。

因此：

$$\text{总数} = b \cdot x \cdot (a - x)$$

这是一个关于 $x$ 的二次函数：

$$f(x) = b \cdot ( -x^2 + a x )$$

开口向下，最大值在 $x = \frac{a}{2}$ 处取得。

---

五、公式推导

由于 $x$ 必须是整数，最优取法为：

$$x = \left\lfloor \frac{a}{2} \right\rfloor$$

此时：

$$\text{最大值} = b \cdot \left\lfloor \frac{a}{2} \right\rfloor \cdot \left(a - \left\lfloor \frac{a}{2} \right\rfloor\right) $$

注意到 $a - \lfloor a/2 \rfloor = \lceil a/2 \rceil$。

因此：

$$\boxed{\text{ans} = b \cdot \left\lfloor \frac{a}{2} \right\rfloor \cdot \left\lceil \frac{a}{2} \right\rceil} $$

---

六、边界情况

• 如果 $a < 2$（'-' 少于 $2$ 个），无法构成 "-_-"，此时 $\lfloor a/2 \rfloor = 0$，公式自动给出 $0$
• 如果 $b = 0$（没有 '_'），公式自动给出 $0$
• 如果 $n < 3$，公式也自动给出 $0$

---

七、算法步骤

1. 读入 $n$ 和字符串 $s$
2. 统计 '-' 的个数 $a$（可用 count 函数）
3. 计算 $b = n - a$
4. 输出 $b \cdot \lfloor a/2 \rfloor \cdot \lceil a/2 \rceil$

---

八、标程代码解析

void solve() {
  int n;
  string s;
  cin >> n >> s;
  int64_t dash = count(s.begin(), s.end(), '-');   // a
  int64_t under = n - dash;                        // b
  int64_t ans = (dash / 2) * (dash - dash / 2) * under;
  // dash/2 是 floor(a/2)
  // dash - dash/2 是 ceil(a/2)
  cout << ans << '\n';
}

注意 int64_t 的使用，防止乘法溢出（$n \le 2\times 10^5$ 时最大答案约 $10^{15}$，需要 64 位整数）。

---

九、复杂度分析

• 统计字符：$O(n)$
• 计算答案：$O(1)$
• 每个测试用例 $O(n)$，总复杂度 $O(\sum n) \le 2\times 10^5$

---

十、总结

要点	说明
核心公式	$\text{ans} = b \cdot \lfloor a/2 \rfloor \cdot \lceil a/2 \rceil$
最优构造	所有 '_' 放在中间，'-' 均匀分到两边
时间复杂度	$O(n)$ 每个测试用例
空间复杂度	$O(1)$ 额外空间
注意事项	使用 64 位整数存储答案