当前位置: 代码迷 >> 综合 >> AT3950 [AGC022E] Median Replace
  详细解决方案

AT3950 [AGC022E] Median Replace

热度:15   发布时间:2023-12-06 00:07:13.0
AT3950 [AGC022E] Median Replace

考虑怎么判断一个串是否合法

如果当前串末尾有两个 0 ,那么再加一个 0 进去显然要把三个 0 合成一个。

所以我们维护的串末尾最多有 2 个 0 。

考虑要加 1 进去,如果当前的末尾是 0 ,显然可以把末尾 0 和这个 1 一起消掉,因为合并后是什么只和前面或者后面一个字符有关了。

这么操作的话,我们维护的串中的所有的 1 一定在 0 前面,否则就可以消掉。

又因为末尾 0 最多有 2 个,那么前面的 1 的个数超过 2 的部分就没有用了。

那么加 1 进去,如果前面已经有两个 1 了,转移的时候状态就不变。

f [ n ] [ i ] [ j ] f[n][i][j] f[n][i][j] 表示有多少种分配问号的方案使得前 n n n 个字符这么操作后有 i i i 个 1, j j j 个 0 。

因为状态数少,直接转移即可。省选前考过一道类似的题,状态数多就要dp套dp2333。

最后合法的就是操作后的串 1 的数量大于等于 0 的数量。(等于是因为字符 0 我们要么合并了要么和 1 抵消了,而有些 1 是被我们直接扔掉了的,所以如果相等时 1 一定是应该大于 0 的个数的

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

#include <bits/stdc++.h>
#define N 300005
using namespace std;
const int mod=1e9+7;
char s[N];
int n,f[N][3][3],ans;
int main(){
    
// freopen("test.in","r",stdin);scanf("%s",s+1);n=strlen(s+1);
// cout<<n<<'\n';f[0][0][0]=1;for(int i=1;i<=n;i++){
    for(int j=0;j<3;j++){
    for(int k=0;k<3;k++){
    if(!f[i-1][j][k]) continue;if(s[i]=='1'||s[i]=='?'){
    if(k==0) (f[i][min(2,j+1)][k]+=f[i-1][j][k])%=mod;else (f[i][j][k-1]+=f[i-1][j][k])%=mod;}if(s[i]=='0'||s[i]=='?'){
    if(k<2) (f[i][j][k+1]+=f[i-1][j][k])%=mod;else (f[i][j][1]+=f[i-1][j][k])%=mod;}}}}for(int j=0;j<3;j++)for(int k=0;k<3;k++)if(j>=k) (ans+=f[n][j][k])%=mod;cout<<ans;
}

一上午被whk的事情整自闭了(太菜了呗呜呜呜呜呜呜

做点简单题放松放松心情

额好像不太简单啊2333

  相关解决方案