//写在前面 To二鸣君：鉴于你让我来贴代码，过后要再请我吃一顿饭才行~
题目大意：给出用字母代表数字的加法等式，求出满足等式的字母对应数字的方案数。
思路： 搜索+剪枝。
我的几点优化：
1. 算出每个字母对应的系数，减少搜索时的计算。
2. 计算上下界时很暴力的按照每个字母上界为9，下界为当前搜索的数字（我是按照数字1-9搜的）来算。（感谢二鸣君。）
代码：
#include#include #include using namespace std;char s[13][10],c[10];int n,m,val[256],score[256],ans;int calc(int t){ //计算二进制中1的个数 int ans = 0; while (t){ ans += (t&1); t = t>>1; } return ans;}int max(int state,int d){//估计上界 int ans = 0; int max = 9,min = d; for (int x = 0;x < m;++x) if((state & (1 << x)) == 0){ if (score[c[x]]>0) ans += score[c[x]]*(max); else ans += score[c[x]]*(min); } return ans;}int min(int state,int d){//估计下界 int ans = 0; int max = 9,min = d; for (int x = 0;x < m;++x) if((state & (1 << x)) == 0){ if (score[c[x]]>0) ans += score[c[x]]*(min); else ans += score[c[x]]*(max); } return ans;}void solve(int d, int state, int sum){//d为当前搜索的数字；state为状态，表示每个字母是否对应了数字；sum为当前的总和 if (sum + min(state,d)>0 || sum + max(state,d)<0) return;//上下界剪枝 if(m - calc(state) > 10 - d) return;//未知的数字个数少于未知的字母，剪枝 if(state == (1 << m) - 1){ //边界 if(sum == 0) ++ans; //sum==0 符合等式 return; } solve(d + 1,state,sum); for(int i = 0;i < m;++i){//枚举…… if((state & (1 << i)) == 0){ solve(d + 1,state | (1 << i),sum + score[c[i]] * d); } }}int main(){ bool used[256],cantzero[256]; while(cin>>n,n){ memset(used,0,sizeof used); memset(cantzero,0,sizeof cantzero); memset(score,0,sizeof score); for(int i = 0;i < n;++i){ cin>>s[i]; int L = strlen(s[i]); if(L > 1) cantzero[s[i][0]] = true; for(int j = L - 1,pow10 = 1;j >= 0;--j,pow10 *= 10){ used[s[i][j]] = true; score[s[i][j]] += (i == n - 1? -pow10 : pow10); } } m = 0; for(int i = 'A';i <= 'Z';++i) if(used[i]) c[m++] = i; ans = 0; solve(1,0,0); for(int i = 0;i < m;++i){ if(!cantzero[c[i]]){ solve(1,(1 << i),0); } } cout< <