題解
列舉每個左端點（l）, 每個字母獨立計算貢獻，列舉每個字母，在【l, n】 中找到該字母第一次出現的位置p, 則左端點為 l, 右短點在【p, n】的子串都得到該字母的貢獻，貢獻 n - p + 1，
例如 :
- ccaba
- 當 l = 1 時 :
- 列舉 ‘a’ , 第一次出現的位置 p = 3 貢獻 5 - 3 + 1 = 3，
- 列舉 ‘b’ …
- 當 l = 2 …
序列自動機維護下一個字符位置, 復雜度 O(26 * n)
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f;
char s[maxn]; int n, nxt[maxn][30];
void init()
{
for(int i = n; i >= 1; i--)
{
for(int j = 1; j <= 26; j++)
nxt[i-1][j] = nxt[i][j];
nxt[i-1][s[i]-'a'+1] = i;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s + 1;
n = strlen(s + 1);
init();
ll ans = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= 26; j++)
{
int p = nxt[i-1][j];
if(p == 0) continue;
ans += (n - p + 1);
}
}
cout << ans << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/181746.html
標籤：其他
上一篇：2020第十一屆藍橋杯真題JAVA B組省賽答案分享（2020.10.17）
下一篇：牛牛的跳跳棋