正题

题目链接:https://www.luogu.com.cn/problem/AT3950

题目大意

一个包含\(?,0,1\)的长度为奇数的序列，把\(?\)替换为\(0/1\)。每次可以选择三个数变成它们的中位数，求有多少种替换方案使得能够把序列最终变为一个\(1\)。

\(1\leq |S|\leq 3\times 10^5\)

解题思路

好像是\(XJ\)那边杂题选讲时候的题

考虑优先减少\(0\)的数量。考虑一些一定优的情况\(000->0,01->\varnothing\)。

这样序列就会变为前面都是\(1\)，后面是\(1/2\)个\(0\)的情况。此时如果\(1\)的数量不少于\(0\)的数量就可以了。

那么\(1\)的数量超过\(2\)的部分也没有意义，设\(f_{i,j}\)表示现在到底\(i\)个时抵消的前面有\(i\)个\(1\)，后面\(j\)个\(0\)时的方案数。显然\(i,j\in[0,2]\)，转移即可。

时间复杂度\(O(n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=3e5+10,P=1e9+7;

ll f[N][3][3],n,ans;

char s[N];

signed main()

{

	scanf("%s",s);n=strlen(s);

	f[0][0][0]=1;

	for(ll i=0;i<n;i++){

		for(ll j=0;j<3;j++)//num0

			for(ll k=0;k<3;k++){//num1 (0 on the 1)

				if(s[i]=='?'||s[i]=='0'){

					if(j==2)(f[i+1][1][k]+=f[i][j][k])%=P;

					else (f[i+1][j+1][k]+=f[i][j][k])%=P;

				}

				if(s[i]=='?'||s[i]=='1'){

					if(j)(f[i+1][j-1][k]+=f[i][j][k])%=P;

					else (f[i+1][j][min(k+1,2ll)]+=f[i][j][k])%=P;

				}

			}

	}

	for(ll j=0;j<3;j++)

		for(ll k=j;k<3;k++)

			(ans+=f[n][j][k])%=P;

	printf("%lld\n",ans);

	return 0;

}

巴特西

AT3950-[AGC022E]Median Replace【贪心,dp】

正题

题目大意

解题思路

code

最新文章

热门文章