Xâu con (HSG12'18-19)

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

Small

Dạng bài

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự \(0\) hoặc \(1\).

Xâu \(v\) gọi là xâu con của \(w\) nếu xâu \(v\) có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu \(w\).

Ví dụ: xâu \(010\) có các xâu con là: \(0, 1, 0, 01, 10, 010\).

Yêu cầu: Cho trước một giá trị \(k\), hãy đếm xem có bao nhiêu xâu con chứa đúng \(k\) ký tự \(1\).

Input

Dòng \(1\): chứa một số nguyên \(k (0 \leq k \leq 10^6)\).
Dòng \(2\): chứa một xâu nhị phân có độ dài \(\leq 10^6\).

Output

Ghi ra một số nguyên duy nhất là kết quả tìm được.

Scoring

\(len(s)\) là độ dài xâu nhị phân.
Subtask \(1\) (\(40\%\) số điểm): \(1 \leq k \leq len(s) \leq 500\).
Subtask \(2\) (\(30\%\) số điểm): \(1000 \leq k \leq len(s) \leq 10000\).
Subtask \(3\) (\(30\%\) số điểm): \(10^5 \leq k \leq len(s) \leq 10^6\).

Example

Test 1

Input

2
01010

Output

Note

có 4 xâu con chứa 2 ký tự 1 là: \(101, 0101, 1010, 01010\).

Bình luận

include<bits/stdc++.h>

using namespace std ;

define ll long long

include<vector>

int main(){
ll k;
cin>>k;
string s;
cin>>s;
vector<ll> v;
if(k==0){
ll ans=0,dem=0;
for(ll i=0;i<s.size();i++){
if(s[i]=='0'){
ans++;
}
if(s[i]=='1'||i==s.size()-1){
dem+=ans*(ans+1)/2;
ans=0;
}
}
cout<<dem;
return 0;
}

else {
for(ll i=0;i<s.size();i++){
    if(s[i]=='1') v.push_back(i);
}
if(v.size()<k){
    cout<<0;
    return 0;
}
ll ans=0;
for(ll i=0;i<v.size()-k+1;i++){
    ll j=i+k-1;
    if(i==0){
        ll left=v[i]+1;
        ll right=v[j+1]-v[j];
    if(v.size()==k) right=s.size()-v[j];
        ans+=left*right;
    }
    else {
        ll left=v[i]-v[i-1];
        ll right=v[j+1]-v[j];
        if(j+1>v.size()-1) right=s.size()-v[j];

    ans+=left*right;
    }
}
cout<<ans;
return 0;

}
}

2 bình luận nữa