Petrozavodsk Summer-2014. Andrew Stankevich Contest 46. J.Jingles of a String
题目大意
给你一个字符串，定义 $J(l, r)$ 为 $[l, r]$ 连续子串的字符集，定义 $S(J)$ 为 $J$ 的大小， $L(J)$ 为字符串中字符集为 $J$ 的连续子串的最长长度，求 $\sum{S(J)L(J)}$ 和 $J$ 的数量。
题目分析
考虑统计每一种 $J$ 的最长长度。从每一个字符作为起始字符入手，那么统计其之后的所有其他字符第一次出现的位置，这些情况对字符集中的字符做出了影响。可以使用 $26$ 个队列维护所有字符出现的位置，最后求解即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, t;
int cnt[(1 << 26) + 5];
char str[maxn];
long long ans;
vector <int> s;
struct ex {
int x;
int c;
};
bool cmp(ex x, ex y){
return x.x < y.x;
}
queue <int> q[30];
int main(){
int i, j;
scanf("%d", &t);
while(t--){
scanf("%s", str);
n = strlen(str);
for(auto i : s){
cnt[i] = 0;
}
s.clear();
ans = 0;
for(i=0;i<26;i++){
while(q[i].size()){
q[i].pop();
}
}
for(i=0;i<n;i++){
q[str[i] - 'a'].push(i);
}
for(i=0;i<n;i++){
vector <ex> vec;
for(j=0;j<26;j++){
if(q[j].size()){
vec.push_back((ex){q[j].front(), j});
}
}
vec.push_back((ex){n, str[i] - 'a'});
sort(vec.begin(), vec.end(), cmp);
int tmp = (1 << vec[0].c);
int c = 1;
for(j=1;j<vec.size();j++){
if(!cnt[tmp]){
s.push_back(tmp);
}
if(cnt[tmp] < vec[j].x - i){
ans += (vec[j].x - i - cnt[tmp]) * c;
cnt[tmp] = vec[j].x - i;
}
tmp |= (1 << vec[j].c);
c++;
}
q[str[i] - 'a'].pop();
}
printf("%d %lld\n", (int)s.size(), ans);
}
return 0;
}