比赛 20120919dfs 评测结果 AAAAAAAAAA
题目名称 虫食算 最终得分 100
用户昵称 feng 运行时间 0.353 s
代码语言 C++ 内存使用 3.13 MiB
提交时间 2012-09-19 20:19:43
显示代码纯文本
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;

bool hash[27],used[27];
string a,b,c,word;
int ans[27],stk[27];
int n;
void cout_ans()
{
    for (int i=0;i<=n-1;i++) ans[word[i]-65]=stk[i];
    cout<<ans[0];
    for (int i=1;i<=n-1;i++) cout<<' '<<ans[i];
    cout<<endl;
    exit(0);
}
void add(char ch)
{
    if (!hash[ch-64])
    {
        hash[ch-64]=true;
        word+=ch;
    }
}
void pre_do()
{
    memset(hash,false,sizeof(hash));
    memset(used,false,sizeof(used));
    word="";
    for (int i=n-1;i>=0;i--)
    {
        add(a[i]); add(b[i]); add(c[i]);
    }
}
bool bad()
{
    int p,g=0;
    for (int i=n-1;i>=0;i--)
    {
        if (a[i]>=n || b[i]>=n || c[i]>=n) return false;
        p=a[i]+b[i]+g;
        if (p%n!=c[i]) return true;
        g=p/n; p%=n;
    }
    return false;
}
bool modcheck()
{
    int p,p1,p2;
    for (int i=n-1;i>=0;i--)
    {//a+b==c;
        if (a[i]>=n || b[i]>=n || c[i]>=n) continue;
        p=(a[i]+b[i])%n;
        if (!(p==c[i] || (p+1)%n==c[i])) return true;
    }
    for (int i=n-1;i>=0;i--)
    {//a+?==c;
        if (!(a[i]<n && b[i]>=n && c[i]<n)) continue;
        p1=(c[i]-a[i]+n)%n;
        p2=(p1-1)%n;
        if (used[p1] && used[p2]) return true;
    }
    for (int i=n-1;i>=0;i--)
    {//?+b==c;
        if (!(a[i]>=n && b[i]<n && c[i]<n)) continue;
        p1=(c[i]-b[i]+n)%n;
        p2=(p1-1)%n;
        if (used[p1] && used[p2]) return true;
    }
    for (int i=n-1;i>=0;i--)
    {//a+b==?;
        if (!(a[i]<n && b[i]<n && c[i]>=n)) continue;
        p1=(a[i]+b[i])%n;
        p2=(p1+1)%n;
        if (used[p1] && used[p2]) return true;
    }
    return false;
}
string change(string str,char x,char y)
{
    for (int i=0;i<=n-1;i++)
        if (str[i]==x) str[i]=y;
    return str;
}
void dfs(int dep)
{
    string a1,b1,c1;
    if (bad()) return ;
    if (modcheck()) return ;
    if (dep==n) cout_ans();
    for (int i=n-1;i>=0;i--)
        if (!used[i])
        {
            used[i]=true;
            a1=a; b1=b; c1=c;
            a=change(a1,word[dep],i);
            b=change(b1,word[dep],i);
            c=change(c1,word[dep],i);
            stk[dep]=i;
            dfs(dep+1);
            a=a1; b=b1; c=c1;
            used[i]=false;
        }
}
int main()
{
	freopen("alpha.in","r",stdin);
	freopen("alpha.out","w",stdout);
    cin>>n;
    cin>>a>>b>>c;
    pre_do();
    dfs(0);
    return 0;
}