1 题目说明

2 题目分析

2.1 暴力分析

这道题可以用暴力做，比如题中的例子 ababc ，可以拆成 5 组（第一重循环），第一组只有 a ，第二组将 b 加进串里，可以和前面的 a 组合成 ab 和 b两个字串 ，同理三四五组是分别将后续的三个字母 a, b, c 加进来， a, b, c 分别和他们前面的字符构成子串（第二重循环）。

• 第一组：a
• 第二组：b, ab
• 第三组：a, ba, aba
• 第四组：b, ab, bab, abab
• 第五组：c, bc, abc, babc, ababc

按理如果字符串长度为n，分为n组并遍历后，再遍历其与前面的字符构成的子串，这儿就需要两重循环了，再加上还要遍历统计构成的子串中字母出现的次数，这就要三重循环了。如何减少第3重循环呢，这个时候就需要一份数组来记录，每一个分组都有一个桶数组，来记录字母出现的次数。

第二重循环向前走一步，比如从 abc 变为 babc, b加入了第五组的子串中，那么就将下标代表为b的位置桶数组加1，用 b-‘a’ (即1)代表 b 的桶下标。每组循环最开始的时候还要定义一个计数多少个字母出现了一次的变量 subsum=0，每在一组中向前加入一个字母，桶数组对应下标就计数加1，如果桶数组计数是从0变为1——subsum+1，如果桶计数是从1变为2——subsum-1，每组对每个字串的subsum求和就得到了每组的子串的 f() 和。对每组的 f() 求和就得到了所有子串的 f() 。

2.2 暴力代码

洛谷得分60，其他样例超时。

#include<iostream>
#include<cstring>
using namespace std;

const int N=100010;

char c[N];
int bucket[26];

int main(){
	cin>>c;
	int n=strlen(c);
	int res=0;
	for(int i=0;i<n;i++){	// 分组
		int subsum=0,sum=0;
		// 每一组从第i个元素开始，逐步将前面的字母加进组内，构成新的子串
		for(int j=i;j>=0;j--){ 
			int k=c[j]-'a'; // 求该字母对应桶数组的下标 
			bucket[k]++;
			if(bucket[k]==1){	// 该元素只出现了一次 
				subsum++;
			}
			else if(bucket[k]==2){	// 该元素重复出现了
				subsum--; 
			}
			sum+=subsum;
		}
		res+=sum;
		memset(bucket,0,sizeof bucket);	// 每次分组要重新计数 
	}
	cout<<res;
}

2.3 优化分析

暴力需要二重循环 \(O(n^2)\)，数据范围是100000，所以肯定会超时，需要把时间控制到 O(nlogn) 或者 O(n)。

还是样例ababc，来看第一个a, 什么时候它能被计数在f()里呢？——当它在该子串中只出现了一次时。下标从1开始，a在下标为3的时候再次出现了，所以第一个a被计数在f()里的子串肯定不能包括第3个a，即只能是ab 和 a这两个子串。

下图所示，会统计下标为5的a出现一次的次数，只会是下面16种组合的字符串，16=（i-left[i]）*（right[i]-i）。其他字母同理，计算所有字母出现一次的子串数即可求得本题。

2.4 优化代码

#include<iostream>
#include<cstring>
using namespace std;

const int N=100010;

char c[N];
int l[N],r[N],d[N];

int main(){
	cin>>c+1; // 下标从1开始 
	c[0]=' ';
	int n=strlen(c)-1;
	// 计算每个字母的左边的重复元素的位置。 
	for(int i=1;i<=n;i++){
		l[i]=d[c[i]-'a'];
		d[c[i]-'a']=i;
	}
	// 计算每个字母的右边的重复元素的位置。 
	memset(d,0,sizeof d);
	for(int i=n;i>=1;i--){
		if(!d[c[i]-'a']){
			r[i]=n+1; // 如果右边没有重复元素，即置为 n+1 
		}
		else{
			r[i]=d[c[i]-'a'];
		}
		d[c[i]-'a']=i;
	}
	// res要开long long,否则会爆 
	long long res=0;
	for(int i=1;i<=n;i++){
		res+=(i-l[i])*(r[i]-i);
	}
	cout<<res;
}