题解 P2435 【染色】

RainFestival · 2019-05-04 21:34:47 · 题解

这道题一看就是其实是一个dp,轮廓线dp

设点i,j上一个轮廓线为u

那么如果u的第m位与第0位（二进制从低到高，第k位价值2^k）

都不与当前要填的数不同，就可以进行状态转移

我们再用滚动数组优化空间即可

附上带有简单优化常数的我不优化有一个点过不去代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#define mod 376544743
using namespace std;
long long dp[5][300000],a[15],ans,sp1[100005],sp2[100005];
int n,m,kk,now,maxs,s1,s2,can,bo;
inline void update(register int x1,register int x2,register int x,register int y)
{
    dp[now][x2]=(dp[now][x2]+dp[now^1][x1])%mod;
}
inline void put(register int x,register int y,register int can)
{
    if (y/a[m-1]!=x&&(y%kk!=x||can)) update(y,(y*kk+x)%a[m],x,y);
} 
inline int check(int x,int y)
{
    while (x>0||y>0)
    {
        if (x%kk==y%kk) return 0;
        x=x/kk,y=y/kk;
    }
    return 1;
}
int main()
{
    srand(time(NULL));
    scanf("%d%d%d",&n,&m,&kk);
    if (kk==2)
    {
        //printf("%d",rand()%2);
        //return 0;
        bo=1;
        for (register int i=1;i<=m;++i)
        {
            //scanf("%d",&sp1[i]);
            char ch=getchar();
            while (ch!='0'&&ch!='1') ch=getchar();
            sp1[i]=ch-48;
            if (sp1[i]==sp1[i-1]) bo=0;
        } 

        for (register int i=1;i<=m;++i)
        {
            //scanf("%d",&sp2[i]);
            char ch=getchar();
            while (ch!='0'&&ch!='1') ch=getchar();
            sp2[i]=ch-48;
            if (sp2[i]==sp2[i-1]) bo=0;
        }  
        for (int i=1;i<=m;++i)
            if ((sp1[i]+n)%2==sp2[i]) bo=0;
        printf("%d\n",bo);
        return 0;    
    }
    a[0]=1;
    maxs=1;
    for (int i=1;i<=m-1;++i)
        a[i]=a[i-1]*kk;
    a[m]=a[m-1]*kk;
    maxs=a[m]-1;
    for (int i=1;i<=m;++i)
    {
        int x,y=-1;
        scanf("%d",&x);
        if (i!=1&&x==y)
        {
            printf("%d\n",0);
            return 0;
        }
        s1=s1*kk+x;
        y=x;
    }
    for (int i=1;i<=m;++i)
    {
        int x,y=-1;
        scanf("%d",&x);
        if (i!=1&&x==y)
        {
            printf("%d\n",0);
            return 0;
        }
        s2=s2*kk+x;
        y=x;
    }
    dp[0][s1]=1;
    now=0;
    for (register int i=1;i<n;++i)
        for (register int j=1;j<=m;++j)
        {
            if (i==1&&j!=m) continue;
            if (i==n-1&&j==m) break;
            if (j==m) can=1;
            else can=0;
            now=now^1;
            for (register int k=0;k<=maxs;++k) dp[now][k]=0;
            for (register int k=0;k<=maxs;++k)
            {
                if (dp[now^1][k]==0) continue;//去掉对答案无贡献的状态，节约时间
                for (register int p=0;p<kk;++p)
                    put(p,k,can);
            }      
        }
    for (register int i=0;i<=maxs;++i)
        if (check(i,s2)) ans=(ans+dp[now][i])%mod;
    printf("%lld\n",ans);
    return 0;
}

然后就accepted了

时间808ms,内存3860KB,代码长度4.08KB

感谢大佬们的观赏