【BZOJ1966】[AHOI2005]病毒检测（动态规划）

题面

题解

我就蒯了一份代码随便改了改怎么就过了？？？

从这道题目蒯的

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAX 505

#define ull unsigned long long

const int base=2333;

ull h1[MAX],h2[MAX],pw[MAX];

char ch[MAX],s[MAX];

int P[505],tot,n,m,ans;

bool f[505][MAX];

int main()

{

    scanf("%s",s+1);n=strlen(s+1)+1;s[n]='?';

    pw[0]=1;for(int i=1;i<MAX;++i)pw[i]=pw[i-1]*base;

    for(int i=1;i<=n;++i)h1[i]=h1[i-1]*base+s[i];

    for(int i=1;i<=n;++i)if(s[i]=='*'||s[i]=='?')P[++tot]=i;

    int T;scanf("%d",&T);

    while(T--)

    {

        memset(f,0,sizeof(f));f[0][0]=1;

        scanf("%s",ch+1);m=strlen(ch+1);ch[++m]='#';

        for(int i=1;i<=m;++i)h2[i]=h2[i-1]*base+ch[i];

        for(int j=0;j<=tot;++j)

        {

            if(s[P[j]]=='*')

                for(int i=1;i<=m;++i)f[j][i]|=f[j][i-1];

            for(int i=0;i<=m;++i)

            {

                if(!f[j][i])continue;

                int l1=i+1,r1=i+(P[j+1]-P[j])-1;

                int l2=P[j]+1,r2=P[j+1]-1;

                if(h2[r1]-h2[l1-1]*pw[r1-l1+1]==h1[r2]-h1[l2-1]*pw[r2-l2+1])

                {

                    if(s[P[j+1]]=='?')f[j+1][r1+1]|=f[j][i];

                    else f[j+1][r1]|=f[j][i];

                }

            }

        }

        ans+=f[tot][m]?0:1;

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

【BZOJ1966】[AHOI2005]病毒检测（动态规划）

【BZOJ1966】[AHOI2005]病毒检测（动态规划）

题面

题解

最新文章

热门文章