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 }