比赛 |
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;
}