第十一届蓝桥杯大赛第二场省赛试题 C&C++ 研究生组-子串分值和

solution1（通过40%）

依次求子串并统计出现过的字母个数

#include
#include
#include
using namespace std;
int main(){
	string s, subs;
	cin >> s;
	int len = s.size(), ans = 0;
	for(int j = 1; j 
		for(int i = 0; i  
solution2递推
 
每位上的字母的贡献为从最左首次不出现到，到字符串末尾
例如ababc里第二个位置上的b
左边未出现过b的子串为 : ，a
右边从当前到末尾的子串可能有 , a, ab, abc
（图片来源网络，侵删）
则第二个位置的b贡献为24 = (2 - 0)(5 - 2 + 1)//这里加上是该字母单独为子串的情况，即子串b
 
#include
#include
using namespace std;
int main(){
	string s;
	cin >> s;
	int pre[25] = {0};
    long long len = s.size(), ans = 0;//有两个测试点结果超出int
	for(int i = 1; i 
		ans += (i - pre[s[i - 1] - 'a']) * (len - i + 1);
		pre[s[i - 1] - 'a'] = i;
	}
	printf("%lld", ans);
	return 0;
}