set(NOIP模拟赛Round 4)

时间：2021-01-21 05:05:45

set(NOIP模拟赛Round 4)

这题很神奇，对吧。

标程还理解了好久，才明白。

这道题需要用状压DP。首先我们看到总共只有15个字符串，所以可以用hash存储状态。

然后我们还需要一维用来存储DP到第几个字符。

所以dp[i][j]表示填到第i位后满足字符串的状态为j的个数；

一开始我们将一个统计数定义为nj=j(j为状态);

每次更新答案的时候只要从a到z枚举一遍，如果有不符合的地方那么nj-当前字符串所对应的二进制位（nj-=1<<l）

统计答案的时候我们只需要for一遍，看看是否有一种状态的符合字符串的个数刚好为k，将dp答案加入总答案即可。

下面贴代码

#include<iostream>

#include<cstdio>

#include<cstring>

#define mod 1000003

#define mo(x)((x>=mod)?x-mod:x)

#define match(a,b)((a=='?')||(b=='?')||(a==b))

using namespace std;

char str[][];

int dp[][<<];

int n,k,ans;

int main(){

//    freopen("set.in","r",stdin);

//    freopen("set.out","w",stdout);

    scanf("%d%d",&n,&k);

    for(int i=;i<n;i++)scanf("%s",str[i]);

    int qaq=strlen(str[]);

    dp[][(<<n)-]=;

    for(int i=;i<qaq;i++)

    for(int j=;j<(<<n);j++)

        if(dp[i][j])

        {

            for(int k='a';k<='z';k++)

            {

                int nj=j;

                for(int l=;l<n;l++)

                {

                    if(((j>>l)&)&&(!match(str[l][i],k)))

                    nj-=(<<l);

                }

                dp[i+][nj]=mo(dp[i+][nj]+dp[i][j]);

            }

        }

    for(int i=;i<(<<n);i++)

    {

        int count=;

        for(int j=;j<n;j++)count+=((i>>j)&);

        if(count==k)ans=mo(ans+dp[qaq][i]);

    }

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

//    fclose(stdin);

//    fclose(stdout);

}

相关文章