Processing math: 100%
Solutions of Ratio Substrings - MarisaOJ: Marisa Online Judge

Solutions of Ratio Substrings

Select solution language

Write solution here.


User Avatar hvnamyd    Created at    13 likes

**Khai báo biến:** Gọi xâu nhị phân độ dài nst. **Dùng mảng tổng tiền tố:** mảng a với a[i] lưu số kí tự 0 từ vị trí 0 đến i, mảng b với b[i] lưu số kí tự 1 từ vị trí 0 đến i **Ý tưởng:** vì đề bài yêu cầu đếm số lượng xâu con liên tiếp có tỉ lệ giữa số 0 và số 1 là xy. Ta có công thức: a[i]b[i]=xy a[i] × y=b[i] × x Khi đó, ta nhân cả mảng a với y, mảng b với x. Gọi mảng c với c[i] là hiệu a[i]b[i]. Bài toán trở thành đếm số cặp i,j sao cho i<jc[i]=c[j] Để đếm số cặp i,j thỏa mãn điều kiện trên thì ta có nhiều cách như dùng đếm phân phối và tìm kiếm nhị phân (trong code hướng dẫn thì dùng đếm phân phối). Code C++: #clude<bitsstdc++.h>constN=1e5;usingnamespacestd;strgst;n,a[N+5],b[N+5],x,y;unorderedmap<,>f;longlongres=0;ma(){iosbase::syncwithstdio(false);c.tie(0);cout.tie(0);cxyst;n=st.n>h();a[0]=(st[0]==0);b[0]=(st[0]==1);for(i=1;i<n;++i){a[i]=a[i-1]+(st[i]==0);b[i]=b[i-1]+(st[i]==1);}for(i=0;i<n;++i){a[i]=y;b[i]=x;}for(i=0;i<n;++i)a[i]b[i];++f[0];for(i=0;i<n;++i){res+=f[a[i]];++f[a[i]];}coutres;return0;}