#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<char,char> pcc; ll a(ll k){ return k*(k+1)/2; } void solve(string s){ ll result1=0,result2=0,result3=0,result; // Ilosc jedno-literowych slow zbilansowanych int runLen=1; for(int i=1; i<s.size(); ++i){ if(s[i]==s[i-1]){ ++runLen; }else{ result1 += a(runLen); runLen=1; } } result1 += a(runLen); // Ilosc dwu-literowych slow zbilansowanych pcc cases[3] = {{'a','b'}, {'a','c'}, {'b','c'}}; for(int u=0; u<3; ++u){ char litera1 = cases[u].first; char litera2 = cases[u].second; int cnt = 0; map<int,int> iloscWystapien; iloscWystapien[0]=1; for(int i=0; i<s.size(); ++i){ if(s[i] == litera1){ ++cnt; result2 += iloscWystapien[cnt]; ++iloscWystapien[cnt]; }else if(s[i] == litera2){ --cnt; result2 += iloscWystapien[cnt]; ++iloscWystapien[cnt]; }else{ // zla litera, przeskakujemy cnt = 0; iloscWystapien.clear(); iloscWystapien[0] = 1; } } } // Ilosc wystapien trzy-literowych char literaSpecjalna = 'c'; char zwyklaLitera1 = 'a'; map<pii,int> iloscWystapien; int cnt1 = 0, cnt2 = 0; iloscWystapien[{0,0}] = 1; for(int i=0; i<s.size(); ++i){ if(s[i] == literaSpecjalna){ cnt1--; cnt2--; }else if(s[i] == zwyklaLitera1){ cnt1++; }else{ cnt2++; } // Operacje te spelniaja zaleznosc: a+b+c => 0 result3 += iloscWystapien[{cnt1,cnt2}]; iloscWystapien[{cnt1,cnt2}]++; } result = result1+result2+result3; cout << result; } int main(){ ios_base::sync_with_stdio(0); string s; cin >> s; solve(s); 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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<char,char> pcc; ll a(ll k){ return k*(k+1)/2; } void solve(string s){ ll result1=0,result2=0,result3=0,result; // Ilosc jedno-literowych slow zbilansowanych int runLen=1; for(int i=1; i<s.size(); ++i){ if(s[i]==s[i-1]){ ++runLen; }else{ result1 += a(runLen); runLen=1; } } result1 += a(runLen); // Ilosc dwu-literowych slow zbilansowanych pcc cases[3] = {{'a','b'}, {'a','c'}, {'b','c'}}; for(int u=0; u<3; ++u){ char litera1 = cases[u].first; char litera2 = cases[u].second; int cnt = 0; map<int,int> iloscWystapien; iloscWystapien[0]=1; for(int i=0; i<s.size(); ++i){ if(s[i] == litera1){ ++cnt; result2 += iloscWystapien[cnt]; ++iloscWystapien[cnt]; }else if(s[i] == litera2){ --cnt; result2 += iloscWystapien[cnt]; ++iloscWystapien[cnt]; }else{ // zla litera, przeskakujemy cnt = 0; iloscWystapien.clear(); iloscWystapien[0] = 1; } } } // Ilosc wystapien trzy-literowych char literaSpecjalna = 'c'; char zwyklaLitera1 = 'a'; map<pii,int> iloscWystapien; int cnt1 = 0, cnt2 = 0; iloscWystapien[{0,0}] = 1; for(int i=0; i<s.size(); ++i){ if(s[i] == literaSpecjalna){ cnt1--; cnt2--; }else if(s[i] == zwyklaLitera1){ cnt1++; }else{ cnt2++; } // Operacje te spelniaja zaleznosc: a+b+c => 0 result3 += iloscWystapien[{cnt1,cnt2}]; iloscWystapien[{cnt1,cnt2}]++; } result = result1+result2+result3; cout << result; } int main(){ ios_base::sync_with_stdio(0); string s; cin >> s; solve(s); return 0; } |