menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[思维+DP]AtCoder Grand Contest 022E【Median Replace】题解
apps AtCoder
local_offer 查看标签
comment 0 条评论

题目概述

有一个长度为奇数的 $01$ 串(有些位待定),每次可以把相邻三个合并成 $01$ 中数量多的,求最终能够变成 $1$ 的方案数。

解题报告

题解好像是大力分类,不过我们可以膜LPA20020220方便的解法。

首先先考虑如果要把一个串变成 $1$ 的策略,可以发现肯定尽量把相邻的 $000$ 都干掉,且尽量留下 $111$ ,由于其他方案都可以看做一个 $1$ 和一个 $0$ 抵消,所以可以直接消去,不需要管之前如何操作。

上面看起来正确,实际上漏了两种情况:$111$ 和 $100$ ,如果出现了 $111$ ,那么后面直接就不用管了,因为不管怎么合并都可以把 $111$ 和后面合并成 $1$ 。还有就是 $100$ ,我们不会想立刻消去 $100$ ,因为有可能会出现 $1000$ 。

由此可以设计一个自动机(其实就是转移,图片是盗来的QAQ):

绿色边表示加 $0$ ,红色边表示加 $1$ ,其中特殊的点就是 $11$ 和 $100$ 。DP就好了。

示例程序

#include<cstdio>
using namespace std;//0:NULL,1:0,2:1,3:00,4:01,5:10,6:11,7:100
const int maxn=300000,MOD=1e9+7,son[8][2]={{1,2},{3,4},{5,6},{1,1},{1,2},{7,2},{6,6},{5,5}};

int n,f[maxn+5][8];char s[maxn+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%s",s+1);for (n=1;s[n];n++);n--;f[0][0]=1;
    for (int i=1;i<=n;i++)
        for (int j=0;j<8;j++){
            if (s[i]!='0') AMOD(f[i][son[j][1]],f[i-1][j]);
            if (s[i]!='1') AMOD(f[i][son[j][0]],f[i-1][j]);
        }
    AMOD(f[n][2],f[n][6]);printf("%d\n",f[n][2]);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up