CF1398C-Good Subarrays
题目:
题目描述:
You are given an array $ a_1, a_2, \dots , a_n $ consisting of integers from $ 0 $ to $ 9 $ . A subarray $ a_l, a_{l+1}, a_{l+2}, \dots , a_{r-1}, a_r $ is good if the sum of elements of this subarray is equal to the length of this subarray ( $ \sum\limits_{i=l}^{r} a_i = r - l + 1 $ ).
For example, if $ a = [1, 2, 0] $ , then there are $ 3 $ good subarrays: $ a_{1 \dots 1} = [1], a_{2 \dots 3} = [2, 0] $ and $ a_{1 \dots 3} = [1, 2, 0] $ .
Calculate the number of good subarrays of the array $ a $ .
输入格式:
The first line contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases.
The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array $ a $ .
The second line of each test case contains a string consisting of $ n $ decimal digits, where the $ i $ -th digit is equal to the value of $ a_i $ .
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .
输出格式:
For each test case print one integer — the number of good subarrays of the array $ a $ .
样例:
样例输入 1:
1
2
3
4
5
6
7
| 3
3
120
5
11011
6
600005
|
样例输出 1:
思路:
实现:
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
| /*
*User: ybw051114
*Time: 2020.08.14 22:35:09
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef use_ios11
#define use_ios11
using namespace std;
struct ins
{
int ans;
ins() { ans = 1; }
#define endl '\n'
void read()
{
}
void read1(char &s)
{
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
s = c;
if (c == EOF)
ans = 0;
}
void read1(string &s)
{
s = "";
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
s += c;
if (c == EOF)
ans = 0;
}
template <typename T>
void read1(T &n)
{
T x = 0;
int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-')
f = -1;
if (c == EOF)
{
ans = 0;
return;
}
}
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
n = x * f;
if (c == EOF)
ans = 0;
if (c != '.')
return;
T l = 0.1;
while ((c = getchar()) <= '9' && c >= '0')
x = x + (c & 15) * l, l *= 0.1;
n = x * f;
if (c == EOF)
ans = 0;
}
void write() {}
void write1(string s)
{
int n = s.size();
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(const char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(char s) { putchar(s); }
void write1(float s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%df", x);
printf(y, s);
}
void write1(double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dlf", x);
printf(y, s);
}
void write1(long double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dLf", x);
printf(y, s);
}
template <typename T>
void write1(T n)
{
if (n < 0)
n = -n, putchar('-');
if (n > 9)
write1(n / 10);
putchar('0' + n % 10);
}
template <typename T>
friend ins operator>>(ins x, T &n);
template <typename T>
friend ins operator<<(ins x, T n);
operator bool() { return ans; }
};
template <typename T>
ins operator>>(ins x, T &n)
{
if (!x.ans)
return x;
x.read1(n);
return x;
}
template <typename T>
ins operator<<(ins x, T n)
{
x.write1(n);
return x;
}
ins yin;
ins yout;
#endif
map<int, int> x;
int sum[100010];
int main()
{
int TTT;
yin >> TTT;
while (TTT--)
{
string s;
int n;
yin >> n;
yin >> s;
x.clear();
long long ans = 0;
x[0] = 1;
for (int i = 0; i < n; i++)
{
sum[i + 1] = sum[i] + s[i] - '0';
ans += x[(sum[i + 1] - i - 1)];
x[sum[i + 1] - i - 1]++;
// yout << ans << endl;
}
yout << ans << endl;
}
return 0;
}
|