数据结构
你有一个长度为 n 的字符串,其中仅含0
,1
,2
三个字符。
你希望知道,这个字符串有多少个子串,满足该子串的0
,1
,2
个数相等?
n 之和不超过3e5
输入
4
3
012
6
001122
18
102100120120120012
18
012012012012012012
输出
1
1
25
51
分析:
map记录0,1与1,2的差值出现次数,在下一次出现时可以直接更新答案
注意map[{0 ,0}]的初始化
int n;
int res;
map<PII, int> mp;
string s;
int a[N], b[N], c[N];
void solve()
{
mp.clear();
res = 0;
for(int i = 1; i <= n; i ++)
{
a[i] = b[i] = c[i] = 0;
}
cin >> n >> s;
s = " " + s;
for (int i = 1; i <= n; i++)
{
a[i] = a[i - 1];
b[i] = b[i - 1];
c[i] = c[i - 1];
if (s[i] == '0')
a[i]++;
if (s[i] == '1')
b[i]++;
if (s[i] == '2')
c[i]++;
}
mp[{0, 0}] = 1;
for (int i = 1; i <= n; i++)
{
int t = a[i] - b[i], tt = b[i] - c[i];
res += mp[{t, tt}];
mp[{t, tt}]++;
}
cout << res << endl;
}
标签:map,int,18,mp,res,数据结构
From: https://www.cnblogs.com/Aidan347/p/17231896.html