CF1917B

luouhgy · 2024-01-06 11:59:15 · 题解

思路：找规律

题意：

有一个长度为 n 的字符串 s，现在有如下两种操作：

• 删除 s 的第 1 个字符。

• 删除 s 的第 2 个字符。

求经过任意次操作，最终的获得的非空字符串的种类数量。

思路：

我们发现对于长度为 i 的字符串，前 n - i + 1 个数是前缀，而这些字符串后缀都相同，所以枚举过去就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
    cin>>t;
    while(t--){
        int n,flag[30]={0};
        string s;
        cin>>n>>s;
        int sum=0,res=0;
        for (int i=0;i<n;i++){
            if(flag[s[i]-'a']==0){//判断 
                sum++;
            }
            flag[s[i]-'a']=1;//标记 
            res+=sum;//累加 
        }
        cout<<res<<endl;//多组样例，输出换行
    }
    return 0;//完工 
}