前缀和和后缀和

1.Problem - 1791D - Codeforces

定义函数 f⁡()f() 表示字符串 x 中不同字符的数量。

现给定一个字符串 S，将它分割为两个字符串 a,b。求出：max⁡(f⁡()+f⁡())max(f(a)+f(b))。

我们可以搞一个前缀和 a 和一个后缀和 b，分别表示 f⁡(S1​∼Si​) 和 f(Si​∼Sn​)。

然后枚举分界点即可。

 1 #include <bits/stdc++.h>
 2 #define re register
 3 
 4 using namespace std;
 5 
 6 const int N = 2e5 + 10,M = 230;
 7 int T,n;
 8 int arr[N],brr[N];
 9 string s;
10 bool vis[M];
11 
12 int main(){
13     cin >> T;
14     while (T--){
15         int ans = 0;
16         memset(arr,0,sizeof(arr));
17         memset(brr,0,sizeof(brr));
18         memset(vis,false,sizeof(vis));
19         cin >> n >> s;
20         s = ' ' + s;
21         for (re int i = 1;i <= n;i++){//前缀和 
22             if (!vis[s[i]]){
23                 arr[i] = arr[i - 1] + 1;
24                 vis[s[i]] = true;
25             }
26             else arr[i] = arr[i - 1];
27         }
28         memset(vis,false,sizeof(vis));
29         for (re int i = n;i;i--){//后缀和 
30             if (!vis[s[i]]){
31                 brr[i] = brr[i + 1] + 1;
32                 vis[s[i]] = true;
33             }
34             else brr[i] = brr[i + 1];
35         }
36         for (re int i = 0;i <= n;i++) ans = max(ans,arr[i] + brr[i + 1]);//选出 max 
37         printf("%d\n",ans);
38     }
39     return 0;
40 }