#include<iostream> #include<vector> #include<algorithm> using namespace std; int n; long long SubproblemAlgorithm(vector<pair<int,int>> &A) { sort(A.begin(), A.end()); long long ile=1; long long wynik=0; for(int i=1; i<=n; i++) { if(A[i].first==A[i-1].first && A[i].second==A[i-1].second){ ile++; continue; }else{ wynik+=((ile*(ile-1))/2); ile=1; } } wynik+=((ile*(ile-1))/2); return wynik; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); string s; cin >> s; n = s.length(); long long ans=0; vector<pair<int,int>> A(n+1); for(int i=0; i<n; i++) { if(s[i]=='a') A[i].first=A[i].second=1; if(s[i]=='b') A[i].first=-1; if(s[i]=='c') A[i].second=-1; if(i>0) { A[i].first+=A[i-1].first; A[i].second+=A[i-1].second; } } A[n].first=A[n].second=0; ans+=SubproblemAlgorithm(A); for(int i=0; i<3; i++) { char x, y; if(i==0) { x='a'; y='b'; } if(i==1) { x='a'; y='c'; } if(i==2) { x='b'; y='c'; } for(int j=0; j<n; j++) { A[j].first=A[j].second=0; if(s[j]==x || s[j]==y) A[j].first++; if(j>0) A[j].first+=A[j-1].first; } A[n].first=A[n].second=0; ans+=SubproblemAlgorithm(A); for(int j=0; j<n; j++) { A[j].first=A[j].second=0; if(s[j]==x) A[j].first=1; else if(s[j]==y) A[j].first=-1; else A[j].second=1; if(j>0) { A[j].first+=A[j-1].first; A[j].second+=A[j-1].second; } } A[n].first=A[n].second=0; ans+=SubproblemAlgorithm(A); } cout << ans << "\n"; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include<iostream> #include<vector> #include<algorithm> using namespace std; int n; long long SubproblemAlgorithm(vector<pair<int,int>> &A) { sort(A.begin(), A.end()); long long ile=1; long long wynik=0; for(int i=1; i<=n; i++) { if(A[i].first==A[i-1].first && A[i].second==A[i-1].second){ ile++; continue; }else{ wynik+=((ile*(ile-1))/2); ile=1; } } wynik+=((ile*(ile-1))/2); return wynik; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); string s; cin >> s; n = s.length(); long long ans=0; vector<pair<int,int>> A(n+1); for(int i=0; i<n; i++) { if(s[i]=='a') A[i].first=A[i].second=1; if(s[i]=='b') A[i].first=-1; if(s[i]=='c') A[i].second=-1; if(i>0) { A[i].first+=A[i-1].first; A[i].second+=A[i-1].second; } } A[n].first=A[n].second=0; ans+=SubproblemAlgorithm(A); for(int i=0; i<3; i++) { char x, y; if(i==0) { x='a'; y='b'; } if(i==1) { x='a'; y='c'; } if(i==2) { x='b'; y='c'; } for(int j=0; j<n; j++) { A[j].first=A[j].second=0; if(s[j]==x || s[j]==y) A[j].first++; if(j>0) A[j].first+=A[j-1].first; } A[n].first=A[n].second=0; ans+=SubproblemAlgorithm(A); for(int j=0; j<n; j++) { A[j].first=A[j].second=0; if(s[j]==x) A[j].first=1; else if(s[j]==y) A[j].first=-1; else A[j].second=1; if(j>0) { A[j].first+=A[j-1].first; A[j].second+=A[j-1].second; } } A[n].first=A[n].second=0; ans+=SubproblemAlgorithm(A); } cout << ans << "\n"; return 0; } |