Question

#2647 SecvBiti rezolvare de 100 p are cineva?
Să se scrie funcția cu următorul antet: long long SecvBiti(char s[])
Funcția primește ca parametru un șir de caractere din mulțimea {'0', '1'} și returnează numărul secvențelor cu proprietatea că numărul biților de 1 din secvență este egal cu numărul biților de 0.

Indicații de rezolvare
Problema SecvBiti – descrierea soluției

Fie n lungimea șirului s. Se construiește vectorul t[] în care t[0] = 1 și, pentru i=1..n, t[i] = numărul de biți de 1 minus numărul de biți de 0 din primii i biți din șir. Soluția problemei este dată de numărul de perechi (i, j) cu 0 ≤ i < j ≤ n și t[i] = t[j]. Complexitate O(n).

Answer 1

long long SecvBiti(char s[]){

int v[1000001],n=1, f[1000001]={0};

v[0]=1;

int b1=1,b0=0;

for(char* p=s;*p;p++){

if(*p == '0')b0++;else b1++;

v[n++]=b1-b0;

}

long long total = 0;

for(int i = 0; i < n; i++){

total+=f[v[i]];

f[v[i]]++;

}

return total;

}