acwing-4261 | vegeone
0%

acwing-4261

题意

给定一串字符串,求其中有多少长度>=3子串,且该子串中某个字符只出现一次。

思路

最终答案的求取可以通过遍历以i位置为所要求的只出现一次的字符所对应的子串数量来求取。

然后显然我们不可能直接对于每个字符c,都暴力的去找左边有多少个相邻的连续的连续的字符与c不同,以及右边有多少个相邻的连续的连续的字符与c不同。于是,我们需要通过预处理,来记录每个字符左右两边分别有多少个相邻的、连续的、与此字符不同的字符,最终的答案也可以理解为左边挑,右边取,然后相乘即可。假设左边的个数为l,右边的个数为r。那么对于该字符,它的贡献为:

由于还有一个限制是长度>=3,所以对某一边没有符合要求的字符时,需要另一边减去只取一个字符的情况,即:

代码

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
void solve()
{
int n;
cin>>n;
string str;
cin>>str;
str=' '+str;
vector<int>l(n+2),r(n+2);
int sum=0;
for(int i=1;i<=n;++i){
if(str[i]==str[i-1]){
l[i]=0;
sum++;
}else {
l[i]=sum;
sum=1;
}
}
sum=0;
for(int i=n;i>=1;--i){
if(str[i]==str[i+1]){
r[i]=0;
sum++;
}else {
r[i]=sum;
sum=1;
}
}
int ans=0;
for(int i=1;i<=n;++i){
// cerr<<l[i]<<" "<<r[i]<<endl;
if(l[i]==0||r[i]==0){
if(l[i]+r[i]>=2)ans+=l[i]+r[i]-1;
}else {
ans+=l[i]*r[i];
if(r[i]>=2)ans+=r[i]-1;
if(l[i]>=2)ans+=l[i]-1;
}
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
// cin>>T;
while(T--) solve();
return 0;
}