CF1917B题解

CF1917B

题目传送门

题意

给出一个长度为 的字符串 ，你可以进行若干次以下两种操作：

1、移除字符串 中的第一个字符

2、移除字符串 中的第二个字符

问题求在经过若干次以上两种中任意一种操作后，不同的非空字符串的数量。

思路

我们可以将字符串 划成左右两部分，枚举两部分的左右临界点，每次枚举完临界点后，将右半部分看作不进行修改的部分，仅对左半部分进行操作，那么每次枚举临界点后的右半部分均不同。为了保证方案的不同，左半部分仅保留一个字符，那么此时的方案数就是左半部分中包含的不同字母的数量。

使用计数数组 动态记录不同字符数量，每次枚举分界点后更新前半部分字符种类并记录到答案中即可。

详细注释代码

码风丑，勿喷

#include<bits/stdc++.h>
using namespace std;
int n,t[30]={0};//字符串长度和计数数组t
int main(){
    int T;
    cin>>T;
    for(;T--;){
    	memset(t,0,30);//将计数数组t归零
        string s;
        cin>>n>>s;//输入字符串长度和字符串s
        int cnt=0,ans=0;
        for(int i=1;i<=n;i++){
            t[s[i]-'a']++;
            if(t[s[i]-'a']==1) cnt++;//统计前半部分中包含的不同字母的数量
            res=res+cnt;
        }
        cout<<res<<endl;
    }
    return 0;
}