NC16866. [NOI2000]算符破译
描述
考古学发现，几千年前古梅文明时期的数学非常的发达，他们懂得多位数的加法和乘法，其表达式和运算规则等都与现在通常所用的方式完全相同（如整数是十进制，左边是高位，最高位不能为零；表达式为中缀运算，先乘后加等），唯一的区别是其符号的写法与现在不同。有充分的证据表明，古梅文明的数学文字一共有13个符号，与 0,1,2,3,4,5,6,7,8,9,+,*,= 这13个数字和符号（称为现代算符）一一对应。为了便于标记，我们用13个小写英文字母a,b,…m代替这些符号（称为古梅算符）。但是，还没有人知道这些古梅算符和现代算符之间的具体对应关系。
在一个石壁上，考古学家发现了一组用古梅算符表示的等式，根据推断，每行有且仅有一个等号，等号左右两边为运算表达式（只含有数字和符号），并且等号两边的计算结果相等。
假设这组等式是成立的，请编程序破译古梅算符和现代算符之间的对应关系。
输入描述
第一行为等式的个数N（1≤ N ≤ 1000），以下N行每行为一个等式。
每个等式的长度为5个字符到11个字符。
输出描述
如果不存在对应关系能够满足这组等式，输出“noway”和一个换行/回车符。
如果有对应关系能够满足这组等式，输出所有能够确定的古梅算符和现代算符的对应关系。每一行有两个字符，其中第一个字符是古梅算符，第二个字符是对应的现代算符。输出按照字典顺序排序。
示例1
输入:
2 abcdec cdefe
输出:
a6 b* d= f+
说明:
在上例中，可能对应的现代表达式为{6*2=12，2=1+1}，{6*4=24，4=2+2}，{6*8=48，8=4+4}。可见，能够确定的对应关系只有a对应6，b对应*，d对应=，f对应+，应该输出；而{c,e}虽然能够找到对应的现代算符使得等式成立，但没有唯一的对应关系，不能输出。其他古梅算符{g,h…m}完全不能确定，也不能输出。C++14(g++5.4) 解法, 执行用时: 1420ms, 内存消耗: 372K, 提交时间: 2019-01-07 16:55:27
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXL=12,MAXN=1001,LETTER=15,LT=13;
const int EQUAL=-1,PLUS=-2,MULTIPLY=-3,NO=-4,UND=-5;
using namespace std;
struct equation
{
int len;
int s[MAXL];
}E[MAXN];
int adjl[LETTER][LETTER];
bool adjm[LETTER][LETTER];
bool ce[LETTER];//可以为等号的字母
bool op[LETTER],appear[100],ava[LETTER],Noway=true;
bool used[LETTER],opu[2];
int Mapp[LETTER],Sp[LETTER];
int P[2][MAXL],L[2];
int N;
void print();
inline int cmp(const void *a,const void *b)
{
return ((equation *)a)->len-((equation *)b)->len;
}
inline int Max(int a,int b)
{
return a>b?a:b;
}
void init()
{
int i,j;
int te[LETTER];
char W[MAXL];
memset(adjm,0,sizeof(adjm));
scanf("%d",&N);
for (i=1;i<=LT;i++)
ce[i]=true;
for (i=1;i<=N;i++)
{
scanf("%s",W);
E[i].len=strlen(W);
memset(te,0,sizeof(te));
for (j=1;j<=E[i].len;j++)
{
E[i].s[j]=W[j-1]-'a'+1;
ava[E[i].s[j]]=true;
if (j!=1 && j!=E[i].len)
te[E[i].s[j]]++;
if (j>1)
adjm[E[i].s[j]][E[i].s[j-1]]=adjm[E[i].s[j-1]][E[i].s[j]]=true;
}
adjm[E[i].s[1]][0]=adjm[0][E[i].s[1]]=true;
adjm[E[i].s[E[i].s[j]]][0]=adjm[0][E[i].s[E[i].s[j]]]=true;
for (j=1;j<=LT;j++)
if (te[j]!=1)
ce[j]=false;
}
for (i=0;i<=LT+1;i++)
{
for (j=0;j<=LT+1;j++)
if (adjm[i][j])
adjl[i][ ++adjl[i][0] ]=j;
Mapp[i]=Sp[i]=UND;
}
op[0]=true;
qsort(E+1,N,sizeof(E[0]),cmp);
}
void debug()
{
int i,j,c;
for (i=1;i<=N;i++)
{
for (j=1;j<=E[i].len;j++)
{
c=Mapp[E[i].s[j]];
if (c>=0) c+='0';
else if (c==EQUAL) c='=';
else if (c==PLUS) c='+';
else if (c==MULTIPLY) c='*';
printf("%c",c);
}
printf("n");
}
printf("n");
}
void solution()
{
int i;
//debug();
if (Sp[1]==UND)
for (i=1;i<=LT;i++)
{
Sp[i]=Mapp[i];
appear[Sp[i]+10]=true;
}
else
for (i=1;i<=LT;i++)
if (Sp[i]!=Mapp[i])
{
Sp[i]=NO;
appear[Sp[i]+10]=true;
}
}
int compute(int *P,int L)
{
int stack[MAXL],top=0,i;
for (i=1;i<=L;i++)
{
if (P[i]>=0)
stack[++top]=P[i];
else if (P[i]==MULTIPLY)
stack[top]=stack[top]*P[++i];
}
for (;top>1;top--)
stack[top-1]+=stack[top];
return stack[1];
}
void makeequation(int p)
{
int i,k=0,v;
L[0]=L[1]=0;
memset(P,0,sizeof(P));
for (i=1;i<=E[p].len;i++)
{
v=Mapp[E[p].s[i]];
if (v==EQUAL)
{
k=1;
continue;
}
if (v>=0)
{
if (i==1 || Mapp[E[p].s[i-1]]<0)
L[k]++;
P[k][L[k]]=P[k][L[k]]*10+v;
}
else
{
P[k][++L[k]]=v;
}
}
}
bool check(int p)
{
int R[2];
makeequation(p);
R[0]=compute(P[0],L[0]);
R[1]=compute(P[1],L[1]);
return (R[0]==R[1]);
}
void fillequation(int p,int f)
{
int i,k=0,v;
L[0]=L[1]=0;
memset(P,0,sizeof(P));
for (i=1;i<=E[p].len;i++)
{
v=Mapp[E[p].s[i]];
if (v==EQUAL)
{
k=1;f=10-f;
continue;
}
if (v>=0)
{
if (i==1 || Mapp[E[p].s[i-1]]<0)
L[k]++;
P[k][L[k]]=P[k][L[k]]*10+f;
}
else
{
P[k][++L[k]]=v;
}
}
}
bool limit()
{
int i;
int R[2];
for (i=1;i<=N;i++)
{
fillequation(i,1);//左小右大
R[0]=compute(P[0],L[0]);
R[1]=compute(P[1],L[1]);
if (R[0]>R[1])
return false;
fillequation(i,9);//左大右小
R[0]=compute(P[0],L[0]);
R[1]=compute(P[1],L[1]);
if (R[0]<R[1])
return false;
}
return true;
}
void computelen(int *P,int L,int &a,int &b)
{
int stacka[MAXL],stackb[MAXL],top=0,i;
for (i=1;i<=L;i++)
{
if (P[i]>=0)
{
stacka[++top]=P[i];
stackb[top]=P[i];
}
else if (P[i]==MULTIPLY)
{
stacka[top]=stacka[top]+P[++i]-1;
stackb[top]=stackb[top]+P[i];
}
}
for (;top>1;top--)
{
stacka[top-1]=Max(stacka[top-1],stacka[top]);
stackb[top-1]=Max(stackb[top-1],stackb[top])+1;
}
a=stacka[1];b=stackb[1];
}
bool lenequation(int p)
{
int i,k=0,v,l0,l1,r0,r1;
L[0]=L[1]=0;
memset(P,0,sizeof(P));
for (i=1;i<=E[p].len;i++)
{
v=Mapp[E[p].s[i]];
if (v==EQUAL)
{
k=1;
continue;
}
if (v>=0 || v==UND)
{
if (i==1 || Mapp[E[p].s[i-1]]<0)
L[k]++;
P[k][L[k]]=P[k][L[k]]+1;
}
else
{
P[k][++L[k]]=v;
}
}
computelen(P[0],L[0],l0,r0);
computelen(P[1],L[1],l1,r1);
return !(r0<l1 || r1<l0);
}
bool possible()
{
int i;
for (i=1;i<=N;i++)
{
if (!lenequation(i))
return false;
}
return true;
}
void search_number(int p,int k)//第p个等式 第k个字符
{
int i,C=E[p].s[k];
bool rfs,lfs;
for (i=1;i<=LT;i++)
if (ava[i])
if (!(Mapp[i]==Sp[i] || Sp[i]==NO))
break;
if (i>LT)
return;
if (p>N)
{
Noway=false;
solution();
return;
}
rfs= k==E[p].len || Mapp[E[p].s[k+1]]<0;
lfs= k==1 || Mapp[E[p].s[k-1]]<0;
if (Mapp[C]==0 && !rfs && lfs)
return;
while (Mapp[C]!=UND && k<=E[p].len)
{
C=E[p].s[--k];
rfs= k==E[p].len || Mapp[E[p].s[k+1]]<0;
lfs= k==1 || Mapp[E[p].s[k-1]]<0;
if (Mapp[C]==0 && !rfs && lfs)
return;
}
if (k==0)
{
if (check(p))
search_number(p+1,E[p+1].len);
return;
}
for (i=0;i<=9;i++)
{
if (used[i])
continue;
rfs= k==E[p].len || Mapp[E[p].s[k+1]]<0;
lfs= k==1 || Mapp[E[p].s[k-1]]!=UND;
if (i==0 && !rfs && lfs)
continue;
Mapp[C]=i;
used[i]=true;
search_number(p,k-1);
used[i]=false;
}
Mapp[C]=UND;
}
void search_operator(int k)
{
int i,j;
while ((!ava[k] || Mapp[k]!=UND) && k<=LT) k++;
if (k>LT)
{
if (possible() && limit())
search_number(1,E[1].len);
return;
}
for (i=1;i<=adjl[k][0];i++)
{
j=adjl[k][i];
if (op[j])
break;
}
if (i>adjl[k][0])
{
op[k]=true;
if (!opu[0])
{
opu[0]=true;
Mapp[k]=PLUS;
search_operator(k+1);
opu[0]=false;
}
if (!opu[1])
{
opu[1]=true;
Mapp[k]=MULTIPLY;
search_operator(k+1);
opu[1]=false;
}
op[k]=false;
Mapp[k]=UND;
}
search_operator(k+1);
}
void solve()
{
int i;
for (i=1;i<=LT;i++)
{
if (ce[i] && !adjm[i][0])
{
op[i]=true;
Mapp[i]=EQUAL;
search_operator(1);
Mapp[i]=UND;
op[i]=false;
}
}
}
void print()
{
int i,ud=0,j,other;
for (i=1;i<=LT;i++)
{
if (Sp[i]==UND)
{
ud++;
j=i;
}
if (!appear[i])
other=i;
}
for (i=1;i<=LT;i++)
{
if (ud==1 && i==j)
{
int c=other-10;
if (c==EQUAL) c='=';
else if (c==PLUS) c='+';
else if (c==MULTIPLY) c='*';
else c-='+';
printf("%c%c\n",i+'a'-1,c);
continue;
}
if (Sp[i]==UND || Sp[i]==NO )
continue;
if (Sp[i]==EQUAL) printf("%c=\n",i+'a'-1);
else if (Sp[i]==PLUS) printf("%c+\n",i+'a'-1);
else if (Sp[i]==MULTIPLY) printf("%c*\n",i+'a'-1);
else printf("%c%d\n",i+'a'-1,Sp[i]);
}
if (Noway)
printf("noway");
exit(0);
}
int main()
{
init();
solve();
print();
return 0;
}
C++ 解法, 执行用时: 40ms, 内存消耗: 516K, 提交时间: 2022-06-09 20:55:11
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=int(1e9);
const int MaxN=1010;
int T;
char a[MaxN][15];
int len[MaxN],lg2[(1<<10)+10];
int w[15],Ans[15],st[15],cnt[15][MaxN];
bool c1[15],c2[15],mark[15],Map[150][1150];
char Equ,Mul,Add;
bool Solved;
inline int Id(char x) { return x-'a'; }
int calc()
{
int i,sum=0;
for(;mark[st[0]-1];st[0]--)
st[st[0]-1]=st[st[0]-1]*st[st[0]];
for (int i=1; i<=st[0]; i++) sum+=st[i]; st[0]=0;
return sum;
}
bool check(int d)
{
int Last=-1,L=-1,R=-1; st[0]=0;
for (int i=1; i<=len[d]; i++)
{
int c=w[Id(a[d][i])];
if(c>=0)
if(Last>=0)st[st[0]]=st[st[0]]*10+c;
else st[++st[0]]=c;
else
{
if(st[0]==0) return 0;
for(;mark[st[0]-1];st[0]--)
st[st[0]-1]=st[st[0]-1]*st[st[0]];
if(c==-3) mark[st[0]]=1;
else if(c==-1)L=calc();
else mark[st[0]]=0;
}
Last=c;
}
R=calc();
return L==R;
}
void Dfs(int d,int Now,int S)
{
bool Flag=1;
for (int i=0; i<=12; i++)
if(!(Ans[i]==w[i] || Ans[i]==-200)){ Flag=0; break; }
if(Flag) return;
if(d>T)
{
Solved=1;
for (int i=0; i<=12; i++) if(w[i]!=INF)
{
if(Ans[i]==-100) Ans[i]=w[i];
else if(Ans[i]!=w[i])Ans[i]=-200;
}
else Ans[i]=-200;
return;
}
else
{
if(Now>len[d])
{
if(check(d)) Dfs(d+1,1,S);
return;
}
int ch=Id(a[d][Now]);
if(w[ch]==INF)
{
for(int S2=S; S2; S2-=S2&-S2)
{
int t=lg2[S2&-S2];
if(Now==1 && t==0 && w[Id(a[d][2])]>0)continue;
w[ch]=t;
Dfs(d,Now+1,S-(S2&-S2));
w[ch]=INF;
}
}
else Dfs(d,Now+1,S);
}
}
int M,lw[15],rw[15];
void Get_Range(int &L, int &R)
{
L=R=0;
for (;M;M--) L=max(L,lw[M]),R=max(rw[M],R)+(R>0);
}
bool Pre_Dfs()
{
int Last,L_l,L_r,R_l,R_r;
for (int d=1; d<=T; d++)
{
M=0;Last=-1;
for (int i=1; i<=len[d]; i++)
{
int c=w[Id(a[d][i])];
if(c==INF)
{
if(Last<0) M++,lw[M]=rw[M]=0;
lw[M]++,rw[M]++;
}
else
{
if(M==0)return 0;
for(; mark[M-1]; M--) lw[M-1]+=lw[M]-1,rw[M-1]+=rw[M];
if(c==-3) mark[M]=1;
else if(c==-2) mark[M]=0;
else if(c==-1) Get_Range(L_l,L_r);
}
Last=c;
}
Get_Range(R_l,R_r);
if(L_r<R_l || R_r<L_l)
{
return 0;
}
}
return 1;
}
int main()
{
scanf("%d",&T);
for (int i=1; i<=T; i++) scanf("%s",a[i]+1),len[i]=strlen(a[i]+1);
for (int i=0; i<=15; i++) lg2[1<<i]=i,Ans[i]=-100;
memset(c1,1,sizeof(c1));
for(char i='a';i<='m';i++)
for (int j=1; j<=T; j++)
{
bool Flag=1;
for (int k=1; k<=len[j]; k++)
{
if(k<len[j]) Map[a[j][k]][a[j][k+1]]=Map[a[j][k+1]][a[j][k]]=1;
if(a[j][k]==i) cnt[Id(i)][j]++;
}
if(cnt[Id(i)][j]!=1) Flag=0;
if(a[j][1]==i || a[j][len[j]]==i){ c1[i-'a']=0; Flag=0; }
c2[Id(i)]=Flag;
}
for(Equ='a'; Equ<='m'; Equ++) if(c2[Id(Equ)])
for(Mul='a'; Mul<='m'; Mul++) if(c1[Id(Mul)])
for(Add='a'; Add<='m'; Add++) if(c1[Id(Add)])
if(Equ!=Mul && Add!=Mul && Equ!=Add)
if(!Map[Equ][Mul] && !Map[Equ][Add] && !Map[Mul][Add])
{
for (int i=0; i<=12; i++) w[i]=INF;
w[Id(Equ)]=-1; w[Id(Add)]=-2; w[Id(Mul)]=-3;
if(!Pre_Dfs()) continue;
Dfs(1,1,(1<<10)-1);
}
for (int i=0; i<=12; i++)
if(Ans[i]>=-3)
{
putchar('a'+i);
if(Ans[i]==-3)putchar('*');
else if(Ans[i]==-2)putchar('+');
else if(Ans[i]==-1)putchar('=');
else putchar('0'+Ans[i]);
putchar('\n');
}
if(!Solved) printf("noway\n");
return 0;
}