题意:
小可可准备了一个未完成的黑白序列,用 B
和 W
表示黑色和白色,用 ?
表示尚未确定。
他希望知道一共有多少种不同的方法,在决定了每一个 ?
位置的颜色后可以得到一个小雪喜欢的黑白序列。
其中,小雪喜欢的黑白序列指的是对于任何正整数 \(n\),由连续 \(n\) 个黑接上连续 \(n\) 个白的序列拼接而成的序列。
例如,如果用字符 B
和 W
分别表示黑色,W
表示白色,那么 BW
,BBWW
,BBBWWW
以及 BWBW
,BWBBWW
,BWBBWWBW
都是小雪喜欢的黑白序列。
而 W
,WW
,WB
,WBBW
以及 BBBWW
都不是小雪喜欢的黑白序列。
输入长度不超过 \(500000\)
- 此题数据本身很水,水到 \(n^2\) 都可以过,但还是要尽量写正解
思路
- 发现对于任意两点 \(l,r\),如果其之间的这个序列是合法的,那么
从 \(l\) 开始,至少有 \(\frac{r-l+1}{2}\) 个格子可以被涂成白色;从 \(r\) 开始向前,至少有 \(\frac{r-l+1}{2}\) 个格子可以被涂黑
- 这么看来,我们就可以将其分开维护,即预处理出向前向后最多能涂的黑白颜色,然后去维护区间和。
由于只需要单点修改以及区间求和,因此树状数组成了不错的选择。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+7;
const int p=1e9+9;
char s[N];int n,b[N],w[N],f[N],tr[N];
vector <int> ed[N];
int lowbit(int x){return x&(-x);}
void modify(int x,int val)
{
x+=2;while(x<=n+2) tr[x]=(tr[x]+val)%p,x+=lowbit(x);
}
int query(int x)
{
x+=2;int res=0;while(x) res=(res+tr[x])%p,x-=lowbit(x);//x+=2:small strick
return res;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>s+1;n=strlen(s+1);
for(int i=1;i<=n;i++) if(s[i]=='B') w[i]=0;else w[i]=w[i-1]+1;
for(int i=n;i>=0;i--) {if(s[i]=='W') b[i]=0;else b[i]=b[i+1]+1;ed[min(2*b[i+1]+i,n+1)].push_back(i);}
f[0]=1;modify(0,1);
for(int i=1;i<=n;i++)
{
if(s[i]!='B'&&i%2==0) f[i]=(query(i)-query(max(i-2*w[i]-2,-1ll))+p)%p,modify(i,f[i]);//注意这里可能小于零,设为-1后在树状数组中需要整体向右平移两格
int len=ed[i].size();for(int x=0;x<len;x++) modify(ed[i][x],-f[ed[i][x]]);
}
cout<<f[n]%p<<'\n';
return 0;
}
标签:const,小雪,AHOI2016,题解,黑白,P2779,int,序列
From: https://www.cnblogs.com/allforgod/p/18544415