孤独的字符
发布时间
阅读量：
阅读量
题目2 : 孤独的字符
时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB
描述
对于一个字符串S，如果某个字符在S中只出现了一次，我们就称这个字符是“孤独”的。
我们用f(S)表示S中孤独的字符的数量，称为S的"孤独值"。
现在给定一个字符串T，请你计算T的所有子串的孤独值。
例如对于T="hih"
f("h") = 1
f("i") = 1
f("h") = 1 (注：两个"h"算作不同的子串)
f("hi") = 2
f("ih") = 2
f("hih") = 1
输入
一个字符串T，只包含小写字母。
对于30%的数据，1 ≤ |T| ≤ 100
对于70%的数据，1 ≤ |T| ≤ 1000
对于100%的数据，1 ≤ |T| ≤ 100000
输出
一个整数表示答案
样例输入
样例输出
统计每一个字符可以在多少个子串里孤独，
比如abbbabbba
那么中间的a往两边延伸，只要不遇到a就说明它经过的这些子串都可以保证它自己孤独
这样预处理每一个字符左右出现的前后位置就可以算每一个字符在多少个子串里孤独
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=100010;
ll L[maxn],R[maxn],Laxt[30],ans;
char c[maxn];
int main()
{
int N,i,j;
scanf("%s",c+1);
N=strlen(c+1);
for(i=0;i<26;i++) Laxt[i]=0;
for(i=1;i<=N;i++) {
L[i]=Laxt[c[i]-'a'];
Laxt[c[i]-'a']=i;
}
for(i=0;i<26;i++) Laxt[i]=N+1;
for(i=N;i>=1;i--) {
R[i]=Laxt[c[i]-'a'];
Laxt[c[i]-'a']=i;
}
//for(i=1;i<=N;i++) ans+=(ll)(i-L[i])*(R[i]-i) ,cout<<L[i] << R[i]<<endl;
cout<<ans<<endl;
return 0;
}
全部评论 (0)
还没有任何评论哟~