Xâu con (HSG12'18-19)

View as PDF

All submissions

Best submissions

Author:

Small

Problem types

Points: 300 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

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\).

Comments

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;

}
}

1

duongnguyen0210 12:44 p.m. 17 sep, 2023

code o(nlogn) cho mọi người tham khảo ạ :V
code: https://ideone.com/bEz2W8

0

EAGLE_RULER 10:14 a.m. 26 dec, 2022

Mọi người cho e hỏi thuật full bài này làm như nào ạ?

2 replies