P5758 [NOI2000] 算符破译
P5758 [NOI2000] 算符破译
为什么这题没有题解？（疑惑
那就来交一个，祝NOIP2021 RP++
写在前面
构造一组数据
Input:
3
abcdefabcde
ghijkfghijk
lmakgflmakgOutput:
f=本题所提交的代码均在时限
暂时想不出什么更高效的优化来解决这类数据。
正文
观察到数据范围很小，显然搜索。
虽然黑题，其实难度不大。不要被题目颜色吓怕了啊
对于一个数学表达式，最重要的是两边相等，因此首先确定 "=" 的位置：
-
在表达式首尾出现过的排除；
-
在同一表达式中出现过至少两次的排除。
-
并不是在每个表达式中都出现的排除
我们筛选后枚举其余可能结果，可以大量减少搜索量。
为了尽早判断我们枚举的结果是否正确，我们把待确定的表达式按照涉及字符的数量排序，同时确定字符枚举的优先顺序。
例如两个表达式分别涉及
然后可以快乐暴搜，枚举每一个字符所对应的数字或运算符。
注意表达式求值的一些细节问题。
当我们求得一合法解时，若当前位已有其他解，则该位记为多解。若当前位原先无解，则将该解加入。
特别注意：当有十二个字符可以确定时，那么最后一个也肯定可以确定，特判一下即可。
Code
#include <bits/stdc++.h>
using namespace std;
int n,cnt,pos;
bool g[15][15],v[15];
string str[1005];
int ans[15],u[15],a[15],ed[1005],p[15];
//ans数组表示最终可确定字符所对应的数字，未确定则是 -1，多解则是 -2
//a数组表示搜索结果，ed数组表示当搜完多少个数字时可以验证一个等式
//为了方便，本代码中用 10表示符号 +，11表示符号 *，12表示符号 =
string l,r;
bool cmp(string x,string y) {
int vis[30];
int cnt1=0,cnt2=0,i;
memset(vis,0,sizeof(vis));
for (i=0;i<x.size();i++) vis[x[i]-'a']++;
for (i=0;i<26;i++) if (vis[i]) cnt1++;
memset(vis,0,sizeof(vis));
for (i=0;i<x.size();i++) vis[y[i]-'a']++;
for (i=0;i<26;i++) if (vis[i]) cnt2++;
return cnt1<cnt2;
}
int work(string x) { //处理字符串对应表达式的值
int sum=0,last=1,single=0,i;
bool mult=0;
if (a[x[0]-'a']>9) return -1;
if (a[x[x.size()-1]-'a']>9) return -1;
for (i=0;i<x.size()-1;i++)
if (a[x[i]-'a']==0 && a[x[i+1]-'a']<10 && (i==0||a[x[i-1]-'a']>9)) return -1;
for (i=0;i<x.size();i++) {
if (a[x[i]-'a']==10) {
if (mult) sum+=last*single, mult=0, last=1;
else sum+=single;
single=0;
continue;
}
if (a[x[i]-'a']==11) {
mult=1, last*=single, single=0;
continue;
}
single=single*10+a[x[i]-'a'];
}
if (mult) sum+=last*single;
else sum+=single;
return sum;
}
void dfs(int k,int t) {
int i,tmp1,tmp2;
if (k==pos) ++k;
while (ed[t]==k-1 && t<=n) {
l=""; r="";
for (i=0;i<str[t].size();i++)
if (a[str[t][i]-'a']!=12) l=l+str[t][i];
else break;
++i;
for (;i<str[t].size();i++)
r=r+str[t][i];
tmp1=work(l); tmp2=work(r);
if (tmp1==-1 || tmp2==-1) return;
if (tmp1!=tmp2) return;
++t;
}
if (k>cnt && t>n) {
if (cnt==12) { //若有 12个可以确定，那么第 13个也可以
int s=0;
for (i=0;i<13;i++)
if (a[i]!=-1) s+=a[i];
for (i=0;i<13;i++)
if (a[i]==-1) a[i]=78-s;
}
for (i=0;i<13;i++)
if (ans[i]==-2 && cnt<12) continue;
else if (ans[i]==-1) ans[i]=a[i];
else if (ans[i]!=a[i]) ans[i]=-2;
return;
}
for (int i=0;i<12;i++) {
if (v[i] || !g[p[k]][i]) continue;
a[p[k]]=i; v[i]=1;
dfs(k+1,t);
v[i]=0; a[p[k]]=-1;
}
}
int main() {
int i,j;
scanf("%d",&n);
for (i=1;i<=n;i++)
cin>>str[i];
sort(str+1,str+n+1,cmp);
for (i=0;i<13;i++)
for (j=0;j<13;j++)
g[i][j]=1;
for (i=0;i<13;i++)
a[i]=-1;
for (i=1;i<=n;i++) { //判断什么字符不可以是 '='
memset(u,0,sizeof(u));
for (j=1;j<str[i].size()-1;j++)
u[str[i][j]-'a']++;
for (j=0;j<13;j++)
if (u[j]!=1) g[j][12]=0;
g[str[i][0]-'a'][10]=g[str[i][0]-'a'][11]=g[str[i][0]-'a'][12]=0;
j=str[i].size()-1;
g[str[i][j]-'a'][10]=g[str[i][j]-'a'][11]=g[str[i][j]-'a'][12]=0;
}
memset(v,0,sizeof(v));
for (i=1;i<=n;i++) { //求解 ed数组
for (j=0;j<str[i].size();j++)
if (!v[str[i][j]-'a']) p[++cnt]=str[i][j]-'a', v[p[cnt]]=1;
ed[i]=cnt;
}
//一个小优化：使得在最短时间内确定更多等式的正确性，p数组记录字符搜索的优先级
if (cnt!=12) {
for (i=1;i<=cnt;i++) ans[p[i]]=-1;
for (i=0;i<13;i++) if (ans[i]==0) ans[i]=-2;
}
else for (i=0;i<13;i++) ans[i]=-1;
memset(v,0,sizeof(v));
for (i=1;i<=cnt;i++)
if (g[p[i]][12]!=0) { //枚举等于号的位置，开始搜索
a[p[i]]=12;
pos=i;
dfs(1,1);
for (j=0;j<13;j++)
a[j]=-1;
}
for (i=0;i<13;i++)
if (ans[i]==-1) { cout<<"noway\n"; return 0; }
for (i=0;i<13;i++)
if (ans[i]>=0) {
cout<<char(i+'a');
if (ans[i]==12) cout<<"=";
else if (ans[i]==11) cout<<"*";
else if (ans[i]==10) cout<<"+";
else cout<<ans[i];
cout<<endl;
}
return 0;
}