比赛 20120919dfs 评测结果 AAAAATTTAA
题目名称 虫食算 最终得分 70
用户昵称 苏轼 运行时间 3.207 s
代码语言 C++ 内存使用 3.13 MiB
提交时间 2012-09-19 20:56:46
显示代码纯文本
#include<iostream>
#include<stdio.h>
using namespace std;
int number,a[27],b[27],c[27],r[27],answer=0,biao,j[27],used[27];
int p,p1,p2;
char q[27],w[27],e[27];
void first();
void dfs(int x);
void out();
int check(int x);
int main()
{
    freopen ("alpha.in","r",stdin);
    freopen ("alpha.out","w",stdout);
    first();
    dfs(-1);
    out();
    return 0;
}
void first()
{
    cin>>number>>q>>w>>e;
    for (int i=0;i<number;i++)
    {
        a[i]=q[i]-'A';
        b[i]=w[i]-'A';
        c[i]=e[i]-'A';
        r[i]=-1;
        j[i]=0;
        used[i]=1;
    }
    j[number]=0;
}
void out()
{
    for (int i=0;i<number;i++)
    {
        cout<<r[i]<<' ';
    }
}
void dfs(int x)
{
    biao=x;
    if (x==number-1)
    {
        if (check(x))
        {
            answer++;
        }
    }
    else
    {
        if (answer!=0)
        {
            return;
        }
        else
        {
            if (!check(x))
            {
                return;
            }
            else
            {
                for (int i=0;i<number;i++)
                {
                    biao=x;
                    if (!used[i])
                    {
                        continue;
                    }
                    x++;
                    r[x]=i;
                    used[i]=0;
                    dfs(x);
                    x--;
                    used[i]=1;
                    if (answer!=0)
                    {
                        return;
                    }
                }
            }
        }
    }
}
int check(int x)
{
    if (x==number-1)
    {
        for (int i=number-1;i>=0;i--)
        {
            if ((r[a[i]]+r[b[i]]+j[i+1])%number!=r[c[i]])
            {
                return false;
            }
            else
            {
                j[i]=(r[a[i]]+r[b[i]]+j[i+1])/number;
            }
        }
    }
    else
    {
        for (int i=number-1;i>=0;i--)
        {
            if (a[i]<=x&&b[i]<=x&&c[i]<=x)
            {
                p=(r[a[i]]+r[b[i]])%number;
                if (p==r[c[i]]||(p+1)%number==r[c[i]])
                {
                }
                else
                {
                    return false;
                }
            }
        }
        for (int i=number-1;i>=0;i--)
        {
            if (a[i]>x&&b[i]<=x&&c[i]<=x)
            {
                p1=(r[c[i]]-r[b[i]]+number)%number;
                if (p1==0)
                {
                    p2=number-1;
                }
                else
                {
                    p2=(p1-1)%number;
                }
                if (!used[p1]&&!used[p2])
                {
                    return false;
                }
            }
        }
        for (int i=number-1;i>=0;i--)
        {
            if (a[i]<=x&&b[i]>x&&c[i]<=x)
            {
                p1=(r[c[i]]-r[a[i]]+number)%number;
                if (p1==0)
                {
                    p2=number-1;
                }
                else
                {
                    p2=(p1-1)%number;
                }
                if (!used[p1]&&!used[p2])
                {
                    return false;
                }
            }
        }
        for (int i=number-1;i>=0;i--)
        {
            if (a[i]<=x&&b[i]<=x&&c[i]>x)
            {
                p1=(r[a[i]]+r[b[i]])%number;
                p2=(p1+1)%number;
                if (!used[p1]&&!used[p2])
                {
                    return false;
                }
            }
        }
    }
    for (int i=0;i<number;i++)
    {
        j[i]=0;
    }
    return (true);
}