博客

Summer Trip Kattis – summertrip

vj题目传送门


思路：遍历字符串，更新每一个字母最新出现的位置vis，从之后走过的位置更新st（set数组），记录在这个字母两次出现的区间中，其他字母是否出现过，没出现过就使结果加一，并添加在st数组中；若最外层遍历中，字母再次出现则清空st对应字母的数组重新添加字母，以此来计算结果总数。

题解：

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn = 1e5+7;
set<int> st[29];
bool vis[29];
char str[maxn];
int ans;

int main() {
    scanf("%s", str);
    int len = strlen(str);
    for(int i=0; i<len; i ++ ){
        int t = str[i] - 'a' + 1;
        if(vis[t]) st[t].clear();
        for(int j=1; j<=26; j++){
            if(j == t) continue;
            if(vis[j]){
                if(st[j].count(t))
                    continue;
                st[j].insert(t);
                ans ++;
             }
        }
        vis[t] = true;
    }
    printf("%d\n", ans);
    return 0;
 }