#P18916. [2026多校联测]糖果店
[2026多校联测]糖果店
糖果店
题目描述
如果一个非空字符串包含相同个数的加号与减号,称其为平衡字符串。例如 +--+、++-+-- 是平衡的,+--、-- 和空字符串不是。
允许进行以下操作:把两个相邻的减号替换为一个加号。如果一个字符串经过若干次操作(可以是零次)能够变得平衡,就称它为有希望的字符串。
所有平衡字符串都是有希望的,但反之不一定成立。例如 -+--- 可以变成平衡字符串 -++- 或 -+-+。
给定仅含 +、- 的字符串 ,求有多少个非空子串是有希望的。相同子串在不同位置出现时分别计数。
输入格式
第一行一个正整数 ,表示测试数据组数。
每组数据两行:第一行一个正整数 ,表示字符串长度;第二行是字符串 。
输出格式
每组数据输出一行一个整数,表示有希望的非空子串数量。
样例 1
输入
5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---
输出
2
4
2
7
4
数据范围
,,所有测试数据的 之和不超过 。
| 子任务 | 特殊性质 | 分值 | |
|---|---|---|---|
| 1 | 无 | 5 | |
| 2 | 10 | ||
| 3 | 25 | ||
| 4 | 字符全部为 - |
10 | |
| 5 | - 的个数至多为 |
20 | |
| 6 | 无 | 30 |
更多样例见附加文件 samples.zip,分别对应各子任务限制。