← 返回题目列表

Codeforces · 2072/B

B. 曾经当过财务主管,我帮助妖精欺骗

中文机器翻译题面 查看原题

完成第一个任务后,明人离开了起始洞穴。过了一会儿,他偶然发现了一个哥布林村庄。

由于 Akito 无处可住,他想了解一下房价。众所周知,妖精们把数字写成‘-’和‘_’组成的字符串,字符串$$$s$$$表示的值就是字符串$$$s$$$中与字符串“相等的不同子序列$$$^{\text{*}}$$$的个数。-_-”(这与妖精的面孔非常相似)。

例如,字符串 $$$s=$$$"-_--_-“代表数字$$$6$$$,因为它有$$$6$$$子序列”-_-":

  1. $$$s_1+s_2+s_3$$$
  2. $$$s_1+s_2+s_4$$$
  3. $$$s_1+s_2+s_6$$$
  4. $$$s_1+s_5+s_6$$$
  5. $$$s_3+s_5+s_6$$$
  6. $$$s_4+s_5+s_6$$$

最初,妖精们写了一个随机的字符串数字 $$$s$$$ 来回答 Akito 的问题,但后来他们意识到他们想从旅行者那里拿走尽可能多的黄金。为此,他们要求您重新排列字符串 $$$s$$$ 中的字符,以便最大化字符串 $$$s$$$ 表示的数字的值。

$$$^{\text{*}}$$$字符串 $$$a$$$ 的子序列是字符串 $$$b$$$,可以通过从 $$$a$$$ 中删除几个(可能是 $$$0$$$)字符来获得。如果子序列是通过删除不同的索引集而获得的,则认为它们是不同的。

输入

第一行包含数字 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

在每个测试用例的第一行,有一个数字$$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)——小妖精写入的字符串的长度。

在每个测试用例的第二行中,有一个长度为$$$n$$$的字符串$$$s$$$,仅由字符“-”和“_”组成——这是妖精写的字符串。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,您需要输出一个数字 - 如果字符串 $$$s$$$ 中的字符经过最佳重新排列,则子序列的最大数量等于字符串“-_-”。

示例

输入
复制

8
3
--_
5
__-__
9
--__-_---
4
_--_
10
_-_-_-_-_-
7
_------
1
-
2
_-

输出
复制

1
0
27
2
30
9
0
0

注意

在第一个测试用例中,重新排列字符以形成字符串“-_-”是有益的。这是唯一一个至少有一个子序列“-_-”的三个字符的字符串。

在第二个测试用例中,只有一个字符“-”,子序列“-_-”至少需要两个字符。这意味着对于任何字符重新排列,答案将是 $$$0$$$。

在第七个和第八个测试用例中,字符串 $$$n \lt 3$$$ 的长度,这意味着长度为 $$$3$$$ 的子序列不存在。