我要评论
思路：枚举每一个字符，统计每一个字符在其所有可能的子串中的贡献度
（可能：就是不重复统计的意思；在其每一个子串中贡献度均为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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论