蓝桥集训之子串分值

本文主要是介绍蓝桥集训之子串分值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蓝桥集训之子串分值

• 核心思想：贡献法

  • 正着做不好做，考虑贡献法，即每个字母对于答案的贡献
  • 为(该字母 – 左边最近的相同字母) * (右边最近的相同字母 – 该字母) 乘法原理
  • 因此 开数组记录每个字母左右边最近相同字母的位置即可

•   #include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N = 100010;typedef long long LL;int l[N],r[N],p[26];char str[N];int main(){cin>>str+1;int n = strlen(str+1);for(int i=1;i<=n;i++){int t = str[i] - 'a';l[i] = p[t];  //p[t]保存的是最近左相同数的位置 p[t]默认是0 即在0处有左边界p[t] = i;  //更新p[t]为当前位置}for(int i=0;i<26;i++) p[i] = n+1;  //更新p数组为n+1 因为n+1为右边界for(int i=n;i;i--){int t = str[i] - 'a';r[i] = p[t];p[t] = i;}LL res=0;for(int i=1;i<=n;i++){res += (LL)(i-l[i]) * (r[i] - i);}cout<<res;}
  

这篇关于蓝桥集训之子串分值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---