https://www.bnuoj.com/v3/problem_show.php?pid=52781
【AC】
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=5e5+3; 5 char str[maxn]; 6 int l; 7 int a[maxn]; 8 int b[maxn]; 9 int n,m; 10 void init() 11 { 12 memset(a,-1,sizeof(a)); 13 memset(b,-1,sizeof(b)); 14 int len=0; 15 for(int i=0;i<l;i++) 16 { 17 if(str[i]==' ') 18 { 19 b[i-1]=i-len; 20 a[i-1]=len; 21 len=0; 22 } 23 else 24 { 25 len++; 26 } 27 } 28 if(len) 29 { 30 b[l-1]=l-len; 31 a[l-1]=len; 32 } 33 for(int i=l-1;i>=0;i--) 34 { 35 if(b[i]==-1) 36 { 37 b[i]=b[i+1]; 38 } 39 } 40 for(int i=l-1;i>=0;i--) 41 { 42 if(a[i]==-1) 43 { 44 a[i]=a[i+1]; 45 } 46 } 47 } 48 49 int solve(int x) 50 { 51 int ans=0; 52 int cur=0; 53 while(cur<l) 54 { 55 ans+=a[cur]+1; 56 if(cur+x>=l) break; 57 cur=b[cur+x]; 58 } 59 return ans-1; 60 } 61 int main() 62 { 63 gets(str); 64 l=strlen(str); 65 scanf("%d%d",&n,&m); 66 init(); 67 for(int i=n;i<=m;i++) 68 { 69 int ans=solve(i); 70 printf("%d ",ans); 71 } 72 return 0; 73 }