本文主要是介绍试题 历届试题 子串分值和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今天好困,写的好慢
这题告诉我画图的重要性qwq
没有这张图,我可能不一定写的出来…
规律是 减少的那个字符只会影响下个字母开头第一次出现这个字符之前子序列的长度
#include<bits/stdc++.h>
using namespace std;
#define ld long double
typedef long long int ll;int main()
{string s;cin>>s;int n=s.length();map<char,int >mm;map<char,map<int,int> >pp;ll ans=0;int zl=0;for(int i=0;i<s.length();i++){int t=mm[s[i]];pp[s[i]][t]=i;if(mm[s[i]]==0){zl++;ans+=zl;}else ans+=zl;mm[s[i]]++;}int item=ans;map<char,int>p1;for(int i=0;i<s.length()-1;i++){mm[s[i]]--;if(mm[s[i]]==0){ans+=item-(n-1-i)-1;item=item-(n-1-i)-1;}else{p1[s[i]]++;int t=p1[s[i]];ans+=item-(pp[s[i]][t]-i-1)-1;item=item-(pp[s[i]][t]-i-1)-1;}}cout<<ans;
}
希望我们都可以打起精神!
放弃很容易,但坚持真的很酷!!!
这篇关于试题 历届试题 子串分值和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!