首页 > 其他分享 >P2779 [AHOI2016初中组] 黑白序列题解

P2779 [AHOI2016初中组] 黑白序列题解

时间:2024-11-13 17:32:17浏览次数:1  
标签:const 小雪 AHOI2016 题解 黑白 P2779 int 序列

题意:
小可可准备了一个未完成的黑白序列,用 BW 表示黑色和白色,用 ? 表示尚未确定。
他希望知道一共有多少种不同的方法,在决定了每一个 ? 位置的颜色后可以得到一个小雪喜欢的黑白序列。
其中,小雪喜欢的黑白序列指的是对于任何正整数 \(n\),由连续 \(n\) 个黑接上连续 \(n\) 个白的序列拼接而成的序列。

例如,如果用字符 BW 分别表示黑色,W 表示白色,那么 BWBBWWBBBWWW 以及 BWBWBWBBWWBWBBWWBW 都是小雪喜欢的黑白序列。
WWWWBWBBW 以及 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

相关文章

  • 题解:CF2025E Card Game
    在这貌似和大部分做法不太一样(?)权当卡特兰数的复习题吧。不会卡特兰数的可以先看文末。如果没有花色\(1\)这道题就很简单了,对于每个别的花色都有\(C(m)\)种分配方案。\(C(n)\)表示卡特兰数的第\(n\)项,答案就是乘起来。发现除了花色\(1\)每种花色的牌都是独立的。这......
  • P6628 [省选联考 2020 B 卷] 丁香之路 题解
    P6628[省选联考2020B卷]丁香之路题解首先考虑题目中路径权值的含义:\(i,j\)两点之间的最短路就是\(|i-j|\)直接连边。题目要求从\(s\)遍历到每个点,到终点每个\(x\)的最短时间。于是我们不妨枚举每个\(x\),考虑在\(O(n)\)至\(O(n\logn)\)的时间复杂度里解决问题......
  • 《统计每个月兔子的总数》 递归、记忆化数组、动态规划题解
    目录题目描述输入描述输出描述解析完整代码描述有一对兔子,从出生后第3个月起每个月都生一对兔子,一对小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第n个月(n<=50)的兔子总数为多少对?输入描述输入1个整数n,表示第几个月输出描述第n个月兔子的总数量有多少?......
  • P10833 [COTS 2023] 下 Niz题解
    题意:给定长度为\(N\)的序列\(a\),求满足以下条件的\((l,r)\)对数:\(1\lel\ler\leN\);\(a_l,a_{l+1},\cdots,a_{r-1},a_r\)是\(1\simr-l+1\)的排列。\(1\leN\le10^6\);\(1\lea_i\leN\)。思路首先,“排列”本身这个性质是很强的。因为排列本身需要从1开......
  • AT_agc011_d [AGC011D] Half Reflector 题解
    用\(1\)表示A,\(0\)表示B,观察进行一次操作后字符串会发生什么变化。首先当第一个数为\(1\)时,只会将第一个数变为\(0\)。对于剩下的情况,手玩一下可以发现会将第一个数移到末尾,然后将所有数异或\(1\)。先考虑暴力怎么做,可以记一个指针\(i\)和当前应该给全体数异或的值\(......
  • P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces题解
    题意:给定一个长度为\(n=2^k\)的数组\(a\),下标从\(0\)开始,维护\(m\)次操作:给定\(x\),设数列\(a'\)满足\(a'_i=a_{i\oplusx}\),将\(a\)修改为\(a'\)。其中\(\oplus\)表示按位异或运算。给定\(l,r\),查询\(a\)的下标在\(l,r\)之间的子数组有多少颜色段。不保......
  • [题解]P3225 [HNOI2012] 矿场搭建
    P3225[HNOI2012]矿场搭建挖煤点坍塌相当于把该点和与其相连的边在图上删掉。借用wjyyy的题解,我们定义“叶子连通块”为“只包含\(1\)个割点的点双连通分量”,“非叶子连通块”为“包含\(\ge2\)个割点的点双连通分量”。如下图,橙色点是割点,红色框圈出的是点双,加粗的是叶子连通......
  • P2612 [ZJOI2012] 波浪 题解
    前置知识:连续段dp题目链接:P2612[ZJOI2012]波浪随机一个\(1\)到\(n\)的排列\(P_{1...n}\),问以下式子的值\(\lem\)的概率是多少?\[|P_1-P_2|+|P_2-P_3|+|P_3-P_4|+...+|P_{n-1}+P_n|\]输出一个答案表示概率。保留\(k\)位小数。对于\(40%\)......
  • P11071 「QMSOI R1」 Distorted Fate题解
    题意:给定一个序列,给定两种操作:将一个区间异或上一个给定的值。给定\(l,r\)求\[{\large(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}}\]\(0\lea_i,x<2^{30}\),\(1\lel\ler\len\)思路由于操作数以及区间过大,一位一位地去模拟肯定是不行的。因此考虑去离线......
  • [题解]CF1407D Discrete Centrifugal Jumps
    思路注意到第二个条件和第三个条件本质相似,可以用相同的维护方式处理,因此这个只讨论第二个条件的维护方式。定义\(dp_i\)表示走到\(i\)的最少步数。第一个条件的转移显然为\(dp_i\leftarrowdp_{i-1}\)。对于第二个条件,\(i\)能向\(j\)转移,当且仅当\(h_{i+1\sim......