藍橋杯 子串分值和 最詳細題解
#include<iostream>//這是看過一個大佬的寫的，改寫的
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=2e5+10;
ll ans;//總個數->定義為long long ,否則會爆
int id[30][maxn];//每個字母的id 對應的位置
int cnt[30];//字母id 對應的數量
char a[maxn];//定義字符陣列
int b[30];//各個字符區間段位置
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>a+1; //記得加1
int len=strlen(a+1);
// cout<<len<<endl;
for(int i=1;i<=len;i++)
{
id[a[i]-'a'][++cnt[a[i]-'a']]=i;//字母出現的最后位置
}
for(int i=1;i<=len;i++)
{
int front=0;//統計不同字符數
for(int j=0;j<26;j++)//26個字母跑一遍
{
if(id[j][cnt[j]]>=i)//這個字母在i后面
{
int t=lower_bound(id[j],id[j]+1+cnt[j],i)-id[j];//就是二分查找
b[++front] =id[j][t];//不同字符出現的第一個位置
}
}
sort(b+1,b+1+front);//對i后面出現的字母排一下序
int last=i;//當前正在索引的位置
for(int j=2;j<=front;j++)//跑一遍下一個位置 ->其實這里就是第幾個不同字符
{
ans+=(b[j]-last)*(j-1);
//b[j]-last是該位字母去上一個字母=距離差 ->其實就是有幾個重復的這樣的塊
//然后再 * 這個塊的長度,當前字符位置-1，其實就是對前面的做處理
//只是需要當前這個字符做標志,j-1是除去當前字符，然后將(b[j]-last)個段 *(前面不同字符個數j-1);
last=b[j];//將索引位置更新
}
ans+=(len-last+1)*front; //最后的位置,就是最長的一個段;
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274487.html
標籤：其他
上一篇：Alien Worlds NFT 自動點擊游戲教程 (Allen worlds NFT auto click game tutorial)