[Noip2004]虫食算 dfs

搜索问题的关键：优秀的搜索策略以及行之有效的减枝

对于这道题我们阶乘搜肯定不行所以我们按位搜，我们对每一位的三个数进行赋值，然后判解。

对于此一类的搜索乘上一个几十的常数来减枝往往要比直接搜要快得多，因为这样的问题他们都会有一个庞大的"之后"，而且判断不存在较为容易，以我们多花一些时间进行减枝往往能达到剪掉许多枝的效果。

搜索还是看感觉，倒搜还是比正搜快......

#pragma GCC optimize("O3")

#include <cstdio>

#include <cstring>

char A[],B[],C[];

int a[],b[],c[],n;

int qian[],hou[],ans[],get[];

bool god;

inline void put_it(){

    int len=n;

    for(int i=len-;i>=;i--)

        a[len-i]=A[i]-'A';

    len=strlen(B);

    for(int i=len-;i>=;i--)

        b[len-i]=B[i]-'A';

    len=strlen(C);

    for(int i=len-;i>=;i--)

        c[len-i]=C[i]-'A';

    for(int i=;i<=n;i++)hou[i]=i+,qian[i+]=i;

    memset(get,-,sizeof(get)),memset(ans,-,sizeof(ans));

}

inline void dfs(int now,int up){

    if(now==n+){

        if(!up){

            god=;

            for(int i=;i<n;i++)printf("%d ",ans[i]);

        }

        return;

    }

    if(god)return;

    register int temp;

    if(ans[a[now]]!=-&&ans[b[now]]!=-){

        temp=(ans[b[now]]+ans[a[now]]+up)%n;

        if(ans[c[now]]==-&&get[temp]==-)

            get[temp]=,ans[c[now]]=temp,dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n),get[temp]=-,ans[c[now]]=-;

        else if(ans[c[now]]!=-&&(temp==ans[c[now]]))

            dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n);

        if(god)return;

        return;

    }

    if(ans[a[now]]==-&&ans[b[now]]==-){

        if(a[now]==b[now]){

            for(int i=qian[n+];i>;i=qian[i]){

                if(get[i-]!=-)continue;

                hou[qian[i]]=hou[i],qian[hou[i]]=qian[i],get[i-]=;

                ans[a[now]]=i-;

                temp=(ans[b[now]]+ans[a[now]]+up)%n;

                if(ans[c[now]]==-&&get[temp]==-)

                    get[temp]=,ans[c[now]]=temp,dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n),get[temp]=-,ans[c[now]]=-;

                else if(ans[c[now]]!=-&&(temp==ans[c[now]]))

                    dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n);

                if(god)return;

                ans[a[now]]=-;

                hou[qian[i]]=i,qian[hou[i]]=i,get[i-]=-;

            }

            return;

        }

        for(int i=qian[n+];i>;i=qian[i]){

            if(get[i-]!=-)continue;

            hou[qian[i]]=hou[i],qian[hou[i]]=qian[i],get[i-]=;

            ans[a[now]]=i-;

            for(int j=qian[n+];j>;j=qian[j]){

                if(get[j-]!=-)continue;

                hou[qian[j]]=hou[j],qian[hou[j]]=qian[j],get[j-]=;

                ans[b[now]]=j-;

                temp=(ans[b[now]]+ans[a[now]]+up)%n;

                if(ans[c[now]]==-&&get[temp]==-)

                    get[temp]=,ans[c[now]]=temp,dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n),get[temp]=-,ans[c[now]]=-;

                else if(ans[c[now]]!=-&&(temp==ans[c[now]]))

                    dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n);

                if(god)return;

                ans[b[now]]=-;

                hou[qian[j]]=j,qian[hou[j]]=j,get[j-]=-;

            }

            if(god)return;

            ans[a[now]]=-;

            hou[qian[i]]=i,qian[hou[i]]=i,get[i-]=-;

        }

        return;

    }

    if(ans[b[now]]!=-){

        for(int i=qian[n+];i>;i=qian[i]){

            if(get[i-]!=-)continue;

            hou[qian[i]]=hou[i],qian[hou[i]]=qian[i],get[i-]=;

            ans[a[now]]=i-;

            temp=(ans[b[now]]+ans[a[now]]+up)%n;

            if(ans[c[now]]==-&&get[temp]==-)

                get[temp]=,ans[c[now]]=temp,dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n),get[temp]=-,ans[c[now]]=-;

            else if(ans[c[now]]!=-&&(temp==ans[c[now]]))

                dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n);

            if(god)return;

            ans[a[now]]=-;

            hou[qian[i]]=i,qian[hou[i]]=i,get[i-]=-;

        }

        return;

    }

    if(ans[a[now]]!=-){

        for(int i=qian[n+];i>;i=qian[i]){

            if(get[i-]!=-)continue;

            hou[qian[i]]=hou[i],qian[hou[i]]=qian[i],get[i-]=;

            ans[b[now]]=i-;

            temp=(ans[b[now]]+ans[a[now]]+up)%n;

            if(ans[c[now]]==-&&get[temp]==-)

                get[temp]=,ans[c[now]]=temp,dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n),get[temp]=-,ans[c[now]]=-;

            else if(ans[c[now]]!=-&&(temp==ans[c[now]]))

                dfs(now+,(ans[b[now]]+ans[a[now]]+up)/n);

            if(god)return;

            ans[b[now]]=-;

            hou[qian[i]]=i,qian[hou[i]]=i,get[i-]=-;

        }

        return;

    }

}

int main(){

    scanf("%d%s%s%s",&n,A,B,C),put_it(),dfs(,);

    return ;

}

巴特西

[Noip2004]虫食算 dfs

最新文章

热门文章