首页 > 代码库 > BZOJ2268 : Wormly

BZOJ2268 : Wormly

2024-10-25 10:20:01   209人阅读

考虑头部，一定是能向前就向前，因此是最左边的腿往右$b-1$个位置。

头部移动之后，腿部就要相应地移动到区间内最靠右的$l$个$1$之上。

若头部和腿部都不能移动，检查是否到达终点即可。

用前缀和以及对前缀和做映射来支持查询。

时间复杂度$O(n)$。

 

#include<cstdio>const int N=1000010;int T,l,b,n,i,h,f,nh,nf,s[N],p[N];char a[N];long long ans;int main(){  scanf("%d",&T);  while(T--){    scanf("%d%d%d%s",&l,&b,&n,a+1);    for(i=1;i<=n;i++)if(a[i]==‘0‘)s[i]=s[i-1];else p[s[i]=s[i-1]+1]=i;    ans=n-b,h=b,f=l;    while(1){      nh=p[s[f]-l+1]+b-1;      if(nh>n)nh=n;      nf=p[s[nh]];      if(nh==h&&nf==f)break;      h=nh;      if(nf>f)f=nf,ans+=l;    }    if(h<n)puts("IMPOSSIBLE");else printf("%lld\n",ans);  }  return 0;}

　　

BZOJ2268 : Wormly


联系
我们