luogu P2779 [AHOI2016初中组]黑白序列

传送门

注:本题解中下标从1开始

这题可以想出一个\(O(n^2)\)的dp,只要考虑每个偶数位置可以从前面的哪个位置加上一个"B...W..."转移过来

然而数据范围有5e5,,,

打表找规律(误),可以发现转移的时候,能够转移位置构成的集合可能会向前多一个元素,向后多一个元素,或者中间少掉一些或全部元素

简化问题,如果现在在\(i\)位置有一个W,同时前面的\(j\)位置到\(i\)之间没有W,那么在往后转移的过程中,如果转移到了\(2i-j\),那么\(j\)就无法向后贡献答案了

就像这样

可以发现因为\(i\)位置为W,所以\(j\)最多只能贡献到位置\(2i-j-2\)

所以求出每个位置\(j\)后面最近的W位置\(i\),然后在\(2i-j\)处像存图一样跟\(j\)连边

转移的时候,用一个变量\(sum\)存储能够转移的所有\(f_j\)之和,如果当前位置为B就无法转移,否则如果前一个位置为B就只能从这个位置往前两个的位置转移过来,其他情况,用一个指针\(tl\)表示当前转移区间的左端点,每次往左移动加入答案;还要记得把该位置所连出去的点,也就是无法贡献答案位置贡献扣除,每次把\(f_i\)加到\(sum\)里去

这里参考了之前大佬的思路和代码

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define inf 2099999999

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define db double

#define eps (1e-5)

using namespace std;

const int N=500000+10,mod=1000000009;

il LL rd()

{

    re LL x=0,w=1;re char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int n,f[N],nxt[N],tl,sum;

int to[N],nt[N],hd[N],tot=1;

il void add(int x,int y)

{

  if(x<=n) ++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;

}

il void del(int x)

{

  for(int i=hd[x];i;i=nt[i])

    {

      if(to[i]>=tl) sum=(sum-f[to[i]]+mod)%mod;

      f[to[i]]=0;

    }

}

char cc[N];

int main()

{

  scanf("%s",cc+1);

  n=strlen(cc+1);

  if(n&1) {puts("0");return 0;}

  nxt[n]=n+1;

  for(int i=n-1;i>=0;i--) nxt[i]=(cc[i+1]=='W')?i+1:nxt[i+1];

  for(int i=0;i<=n;i+=2) add((nxt[i]<<1)-i,i);

  f[0]=sum=1;

  for(int i=2;i<=n;i+=2)

    {

      del(i);

      if(cc[i]=='B') sum=0,tl=i;

      else if(cc[i-1]=='B') sum=f[i-2],tl=i-2;

      else

        {

          tl-=2;

          if(tl>=0) sum=(sum+f[tl])%mod;

        }

      sum=(sum+(f[i]=sum))%mod;

    }

  printf("%d\n",f[n]);

  return 0;

}

巴特西

luogu P2779 [AHOI2016初中组]黑白序列

最新文章

热门文章