第十一届蓝桥杯第二场（子串分值和）

 思路：枚举每一个字符，统计每一个字符在其所有可能的子串中的贡献度

          （可能：就是不重复统计的意思；在其每一个子串中贡献度均为1。）

假设字符下标为i，其贡献度G=i*(n-i+1) ??? 有重复计算；

分析：对于[i,n]区间，其子串为[i,kr] ，（i<=kr<=n）；但对于[1,i]区间，其子串有[kl,i]，(1<=kl<=i);

           这样就可以看出，如果s[kl]==s[i]，那么对于所有满足[j,i]，(j<=kl)的区间对（[j,kl],[kl,kr]）都是重复计算过的

 

/*
自己选择的路 ,跪着也要走完。朋友们 , 虽然这个世界日益浮躁起来,只
要能够为了当时纯粹的梦想和感动坚持努力下去 , 不管其它人怎么样,我
们也能够保持自己的本色走下去。
To the world , you will be a person , but to a person , you
will be the world .                               ——AKPower
*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
ll pre[30];
string s;

int main()
{
	IOS;
	cin>>s;
	ll len=s.length();
	s="0"+s;//下标从1开始
	ll ans=0;
	for(ll i=1;i<=len;i++){
		ans+=(i-pre[s[i]-'a'])*(len-i+1);
		pre[s[i]-'a']=i;
	}	
	cout<<ans<<endl;
	getchar();
	getchar();
	return 0;
}

 

本文地址：https://blog.csdn.net/qq_43746332/article/details/109385747