CF1307C Cow and Message（思维 + 前缀和）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <functional>
 5 #include <set>
 6 #include <vector>
 7 #include <queue>
 8 #include <cstring>
 9 #include <stack>
10  
11 using namespace std;
12  
13 #define ll long long
14 #define pb push_back
15 #define fi first
16 #define se second
17  
18  
19 void solve(){
20  
21     string str;
22     cin >> str;
23     int n = (int)str.size();
24      vector<vector<int > > pos(26);
25      vector<vector<int > > pre(26, vector<int >(n + 1));
26      //坐标+1
27      for(int i = 0; i < n; ++i){
28          int x = str[i] - 'a';
29          for(int j = 0; j < 26; ++j) pre[j][i + 1] = pre[j][i];
30          pre[x][i + 1] += 1;
31          pos[x].pb(i + 1);
32      }
33      ll Max_cnt = 0;
34      for(int i = 0; i < 26; ++i) Max_cnt = max(Max_cnt, (ll)pos[i].size());
35      for(int fi = 0; fi < 26; ++fi){
36          if((int)pos[fi].size() == 0) continue; //不存在
37  
38          for(int se = 0; se < 26; ++ se){
39              ll cnt = 0;
40              
41              if((int)pos[se].size() == 0) continue; //不存在
42              for(auto inx : pos[fi]){
43                  cnt += pre[se][n] - pre[se][inx];
44              }
45              Max_cnt = max(Max_cnt, cnt);
46          }
47          
48      }
49      cout << Max_cnt << endl;
50 }
51  
52 int main(){
53     
54     ios::sync_with_stdio(false);
55     cin.tie(0);
56     cout.tie(0);
57     solve();
58     
59     return 0;
60 }