BZOJ4295 : [PA2015]Hazard

第i轮，a[i%n]+=b[i%m]。

枚举i，计算它变为0的次数，假设为t，那么有t=i+kn。

对于所有的i和k，(i+kn)%m形成了若干个总长度为m的环。

对于每个a[i]，先在环中求出一轮最多可以减少多少，以及一轮的增量是多少，由此可以求出在几轮后变为0。

再在前缀后缀分类讨论一下即可求出具体是在哪一局变为0。

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

#include<cstdio>

#define N 1000010

typedef long long ll;

const ll inf=2000000000000000000LL;

int n,m,i,j,k,x,a[N],b[N],v[N],t,q[N],s[N],pre[N],suf[N],g[N],c[N+N];ll f[N],ans=inf;char ch[N];

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

inline int min(int a,int b){return a<b?a:b;}

inline ll min(ll a,ll b){return a<b?a:b;}

int main(){

  for(read(n);i<n;i++)read(a[i]),f[i]=inf,g[i]=N;

  for(read(m),scanf("%s",ch),i=0;i<m;i++)b[i]=ch[i]=='W'?1:-1;

  for(i=0;i<N+N;i++)c[i]=N;

  for(i=0;i<n;i++)if(!v[i%m]){

    for(t=0,j=i%m;!v[j];j=(j+n)%m)v[q[++t]=j]=1;

    for(j=1;j<=t;j++)s[j]=s[j-1]+b[q[j]];

    pre[0]=suf[t+1]=N;

    for(j=1;j<=t;j++)pre[j]=min(pre[j-1],s[j]);

    for(j=t;j;j--)suf[j]=min(suf[j+1],s[j]);

    for(j=1;j<=t;j++){

      x=min(pre[j-1]+s[t],suf[j])-s[j-1];

      for(k=q[j];k<n;k+=m)if(x+a[k]<=0)g[k]=0;else if(s[t]<0)g[k]=(x+a[k])/(-s[t])+((x+a[k])%(-s[t])>0);

    }

    for(j=1;j<=t;j++){

      for(k=q[j];k<n;k+=m)if(g[k]<N){

        x=c[s[j-1]-g[k]*s[t]-a[k]-s[t]+N];

        if(x<=t)f[k]=min(f[k],(1LL*g[k]*t+x-j+t)*n+k);

      }

      if(c[s[j]+N]>j)c[s[j]+N]=j;

    }

    for(j=1;j<=t;j++)c[s[j]+N]=N;

    for(j=t;j;j--){

      c[s[j]+N]=j;

      for(k=q[j];k<n;k+=m)if(g[k]<N){

        x=c[s[j-1]-g[k]*s[t]-a[k]+N];

        if(x<=t)f[k]=min(f[k],(1LL*g[k]*t+x-j)*n+k);

      }

    }

    for(j=1;j<=t;j++)c[s[j]+N]=N;

  }

  for(i=0;i<n;i++)ans=min(ans,f[i]+1);

  if(ans<inf)printf("%lld",ans);else puts("-1");

  return 0;

}