S2OJ - 929. 古代龙人的谜题

#题面

#题目描述

Mark Douglas 是一名调查员。他接受了「调查古代龙人」的任务。经过千辛万苦，Mark 终于找到了一位古代龙人。Mark 找到他时，他正在摆弄一些秘药，其中一些药丸由于是从很久以前流传下来的，发出了独特的光泽。古代龙人告诉了 Mark 一些他想知道的事情，看了看手中的秘药，决定考一考这位来访者。

古代龙人手中共有 $n$ 粒秘药，我们可以用 $1$ 表示「古老的秘药」，其余的用 $0$ 表示。他将它们排成一列。古代龙人认为平衡是美的，于是他问 Mark 能选出 多少个「平衡的区间」。「平衡的区间」是指首先选出一个区间 $[L, R]$，在它内部选出一个中间点 $\mathit{mid}$，满足 $L < \mathit{mid} < R$，$\mathit{mid}$ 是「古老的秘药」，且区间 $[L,\mathit{mid}]$ 和 $[\mathit{mid}, R]$ 中「古老的秘药」个数相等。

#输入格式

第一行为一个正整数 $\mathit{t}$ 表示该测试点所属的子任务编号，子任务的详细信息请见「数据范围」。样例的子任务编号为 $0$。

第二行为一个正整数 $n$。

第三行为一个长度为 $n$ 的字符串，仅包含 $0$ 和 $1$。

#输出格式

输出一行，表示答案。

#样例输入输出

样例输入 #1

0
7
1101011

样例输出 #1

7

样例输入 #2

见 GitSB 仓库中本题目录下的 data/ex_puzzle2.in。

样例输出 #2

见 GitSB 仓库中本题目录下的 data/ex_puzzle2.out。

样例输入 #3

见 GitSB 仓库中本题目录下的 data/ex_puzzle3.in。

样例输出 #3

见 GitSB 仓库中本题目录下的 data/ex_puzzle3.out。

#数据范围与约定

本题采用捆绑测试，只有通过一个子任务中的全部测试点才能拿到这个子任务的分数。

对于所有测试点，$1 \leq n \leq 10^6$。各子任务分值及特殊约束如下：

#思路

预处理出每个以 $1$ 为分隔的段的长度，然后按照前缀和的奇偶性分别处理，由于每段之中只包含一个数字 $1$，所以第 $i$ 段的前缀和即为 $i$。最后再单独处理相邻的段即可。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <string>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e6 + 5;

int t, n;
int cnt, len[N];
int cnt_odd, cnt_even;
std::string s;
long long ans;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t >> n >> s;

    s = ' ' + s;

    len[0] = 1;
    for (int i = 1; i <= n; i++) {
        len[s[i] == '1' ? ++cnt : cnt]++;
    }

    for (int i = 0; i < cnt; i++) {
        if (i % 2 == 1) {
            ans += static_cast<long long>(cnt_odd) * len[i + 1];
            cnt_odd += len[i];
        } else {
            ans += static_cast<long long>(cnt_even) * len[i + 1];
            cnt_even += len[i];
        }
    }

    for (int i = 1; i <= cnt; i++) {
        if (len[i - 1] > 1 && len[i] > 1) {
            ans += static_cast<long long>(len[i - 1] - 1) * (len[i] - 1);
        }
    }

    cout << ans << endl;

    return 0;
}