自动搬运

查看原文

来自洛谷，原作者为

	laocong **

搬运于2025-08-24 22:14:06，当前版本为作者最后更新于2021-10-31 14:29:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5758 [NOI2000] 算符破译

为什么这题没有题解？（疑惑

那就来交一个，祝NOIP2021 RP++

写在前面

构造一组数据

Input:

3
abcdefabcde
ghijkfghijk
lmakgflmakg

Output:

f=

本题所提交的代码均在时限 $1s$ 内跑完，跑得最快的大约 $230s$，即本题解。

暂时想不出什么更高效的优化来解决这类数据。

正文

观察到数据范围很小，显然搜索。

虽然黑题，其实难度不大。不要被题目颜色吓怕了啊

对于一个数学表达式，最重要的是两边相等，因此首先确定 "=" 的位置：

• 在表达式首尾出现过的排除；

• 在同一表达式中出现过至少两次的排除。

• 并不是在每个表达式中都出现的排除

我们筛选后枚举其余可能结果，可以大量减少搜索量。

为了尽早判断我们枚举的结果是否正确，我们把待确定的表达式按照涉及字符的数量排序，同时确定字符枚举的优先顺序。

例如两个表达式分别涉及 $4$ 个和 $9$ 个字符，我们先枚举第一个表达式所涉及的 $4$ 个字符，于是枚举 $4$ 次后便可以筛去大量不合法结果，以获得大量剪枝的效果。

然后可以快乐暴搜，枚举每一个字符所对应的数字或运算符。

注意表达式求值的一些细节问题。

当我们求得一合法解时，若当前位已有其他解，则该位记为多解。若当前位原先无解，则将该解加入。

特别注意：当有十二个字符可以确定时，那么最后一个也肯定可以确定，特判一下即可。

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