CF2237D Fullmetal Bitchemist

一个二进制字符串是仅由字符 $0$ 和 $1$ 组成的字符串。字符 $0$ 和 $1$ 称为相反值。 考虑一个二进制字符串 $t$，记 $|t|$ 为 $t$ 的长度。当 $|t| \ge 2$ 时，对于每个 $1 \le i < |t|$，字符 $t_i$ 和 $t_{i+1}$ 是相邻的。 如果通过任意多次（也可以是零次）应用如下操作，能将二进制字符串 $t$ 归约为恰好长度为 $1$ 的字符串，则称 $t$ 是“美丽”的： - 选择一对相等的相邻字符，删去这两个字符，并在它们原位置插入一个相反值的字符。 例如，字符串 $\mathtt{10001}$ 可以将第一个相邻的 $\mathtt{00}$ 替换为 $\mathtt{1}$，变为 $\mathtt{1101}$。接着变为 $\mathtt{001}$，再变为 $\mathtt{11}$，最后是 $\mathtt{0}$。因此，$\mathtt{10001}$ 是美丽的。 而 $\mathtt{111}$ 就不是美丽的。操作一次后变为 $\mathtt{01}$，无法继续操作。 现在给定一个二进制字符串 $s$。请计算 $s$ 的非空美丽子串的个数 $^{\text{∗}}$。 $^{\text{∗}}$ 字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可以通过删除 $b$ 的开头和结尾的若干（可能为零或全部）字符得到。

每组测试包含若干测试用例。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。接下来每组测试数据格式如下： 每个测试用例的第一行为一个整数 $n$（$1 \le n \le 10^6$），表示字符串 $s$ 的长度。 第二行为一个长度为 $n$ 的二进制字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示 $s$ 的美丽子串的个数。

在第一个测试用例中，唯一的非空子串是 $\mathtt{0}$，它本身就是长度为 $1$ 的二进制字符串，因此美丽。 在第二个测试用例中，美丽的子串是 $\mathtt{0}$ 和 $\mathtt{1}$。子串 $\mathtt{01}$ 不是美丽的，因为它的两个字符不相等，无法进行任何操作。 在第三个测试用例中，美丽的子串包括： - $s[1,1] = \mathtt{0}$； - $s[2,2] = \mathtt{1}$； - $s[3,3] = \mathtt{0}$； - $s[4,4] = \mathtt{0}$； - $s[5,5] = \mathtt{1}$； - $s[3,4] = \mathtt{00}$，可以变为 $\mathtt{1}$； - $s[2,4] = \mathtt{100}$，可以变为 $\mathtt{11}$，再变为 $\mathtt{0}$； - $s[3,5] = \mathtt{001}$，可以变为 $\mathtt{11}$，再变为 $\mathtt{0}$； - $s[1,4] = \mathtt{0100}$，可以变为 $\mathtt{011}$，再变为 $\mathtt{00}$，再变为 $\mathtt{1}$； - $s[1,5] = \mathtt{01001}$，可以变为 $\mathtt{0111}$，再变为 $\mathtt{001}$，再变为 $\mathtt{11}$，最后变为 $\mathtt{0}$。 因此，一共有 $10$ 个美丽子串。 由 ChatGPT 5 翻译