Editorial for Bedao Grand Contest 01 - DISTR
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> using namespace std; #define maxn 10000007 #define forinc(i,a,b) for(int i=a;i<=b;i++) #define fordec(i,a,b) for(int i=a;i>=b;i--) #define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); } ///mydata: ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> int n,k; string s; int a[maxn]; int z[maxn]; void prez(){ z[1]=n; int l=0,r=0; forinc(i,2,n) if(r<i) { l=r=i; while(s[r]==s[r-l+1]) ++r; --r; z[i]=r-l+1; } else{ int a=i-l+1,B=r-i+1; if(z[a]<B) z[i]=z[a]; else { l=i; while(s[r]==s[r-l+1]) ++r; --r; z[i]=r-l+1; } } } void update(int i){ if(i*k>n || z[i+1]<(k-1)*i) return; a[i*k]+=1;a[i*k+min(i,z[i*k+1])+1]-=1; } void enter(){ cin>>n>>k; cin>>s; s='$'+s; } void solve(){ prez(); forinc(i,1,n/k) update(i); forinc(i,1,n) a[i]+=a[i-1]; int ans=0; forinc(i,1,n) ans+=a[i]>0; cout<<ans; } signed main() { checkfile("DISTR"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); enter(); solve(); return 0; }
Comments