（alpha.pas）
By Withflying
2008-1-5
问题描述：
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#9865#045 + 8468#6633 = 44445506678 其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。
现在，我们对问题做两个限制：首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表示的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。
BADC + CBDA = DCCC 上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解.
输入格式 Input.txt
输入包含4行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。
输出格式 Output.txt
输出包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。
样例输入
5
ABCED
BDACE
EBBAA
样例输出
1 0 3 4 2
时间限制
每个测试点1s
来源
NOIp2004
解题思路：
这道题的主要算法是搜索，但当然还有解方程等其他方法，这里主要介绍搜索的方法。
深度搜索每个字母的值
显然O(n!)的复杂度会超时，那就必然要剪枝
下面来说一下优化
对于一个测试数据
5
ABCED
BDACE
EBBAA
一：剪枝：
如最后一列的D,E,A
如果D，E，A的值都已经搜出来一种方案了，那么A =(D+E) mod n 即D+E除以n的余数是A，因为D+E有可能〉n并且进位，所以要mod n，详细一点即，对于搜索出来的D，E，A如果上一位进位则 A=（D+E+1）mod n，不进位则A=（D+E）mod n,不知道是否进位则(A=（D+E+1）mod n)or( A=（D+E）mod n)，如果满足这些条件则继续，否则退出。
如果只知道D，E则（D+E）mod n（如进位则是（D+E+1）mod n）这个数没被赋值到其他的字母上去就可以继续搜，同样只知道E，A和D，A也可以这样剪枝。
E，A：[A-E mod n] (进位则是 (A-E-1) mod n)没被赋给除D外的其它字母
D，A：[A-D mod n] (进位则是 (A-D-1) mod n)没被赋给除E外的其它字母
二：优化：
还有一个优化就是从搜索顺序的优化：搜索顺序的改变也成为大大提高程序效率的关键：从右往左，按照字母出现顺序搜索，有很大程度上提高了先剪掉废枝的情况。
三：注意：
进位情况要特别注意：
（1）
如果D，E，A都知道，那么（D+E）DIV n<>0则进位否则不进（上一位进位则（D+E+1）DIV n<>0 ）
（2）
如果知道D，E那么（D+E）DIV n<>0则进位否则不进（上一位进位则（D+E+1）DIV n<>0 ） 特殊情况：如果上一位不确定是否进位那么又要分情况讨论：○1如果进位，不进位两种情况中只有一种情况合法（即所确定的数符合剪枝条件）,那么就按这种情况确定是不是进位。○2如果两种情况都合法则，如果两种情况的进位是否都相同，那么可以确定这一位是否进位，不同的话则进位状态赋值为待定。
（3）
知道A，E那么 Ａ<E则进位否则不进（上一位进位则（A-1）<E ） 特殊情况：同（２）。
（4）
知道A，Ｄ那么 Ｄ<E则进位否则不进（上一位进位则（A-1）<D ） 特殊情况：同（２）。
（5）
只知道D,E,A中一个的值，则进位状态待定。
代码：
program cao；
const
max=26；
var
f:array[A..Z] of longint； //f表示每个字母的值
a,b,c,order:array[-max..max] of char；//order表示搜索顺序
d,e,g,h,i,j,k,l,n,m,p,q:longint；
s,s1,s2,s3:string；
flag:array[A..Z] of boolean；//flag表示这个字母是否搜出解
hash:array[-max..max] of boolean；//hash表示这个数字是否搜过
ch:char；
procedure init；
begin
readln(n)；
readln(s1)；
readln(s2)；
readln(s3)；
fillchar(a,sizeof(a),0)；
fillchar(b,sizeof(b),0)；
fillchar(c,sizeof(c),0)；
fillchar(order,sizeof(order),0)；
fillchar(flag,sizeof(flag),false)；
for ch:=A to Z do
f[ch]:=0；
for i:=1 to n do
begin
a[i]:=s1[i]；
b[i]:=s2[i]；
c[i]:=s3[i]；
end；//以上都是初始化和读入
j:=0；
for i:=n downto 1 do
begin
if flag[a[i]]=false then begin inc(j)； order[j]:=a[i]； flag[a[i]]:=true； end；
if flag[b[i]]=false then begin inc(j)； order[j]:=b[i]； flag[b[i]]:=true； end；
if flag[c[i]]=false then begin inc(j)； order[j]:=c[i]； flag[c[i]]:=true； end；
end；//从右往左按照字母出现顺序
if j<>n then
for ch:=A toZ do
begin
if flag[ch]=false then begin inc(j)； flag[ch]:=true； order[j]:=ch； end；
if j>=n then break；
end；//如果有字母在字符串中没有出现，处理特殊情况
fillchar(flag,sizeof(flag),false)；
end；
procedure print；
var
i:longint；
begin
i:=0；
for ch:=A toZ do
begin
inc(i)；
write(f[ch], )；
if i>=n then halt；
end；
end；
function work:boolean；
var
i,j,k,l:longint；
up:array[-max..max] of integer； //up记录进位情况
begin
fillchar(up,sizeof(up),0)；
up[n]:=1；
for i:=n downto 1 do
begin
if flag[a[i]] and flag[b[i]] and flag[c[i]] then //如果A，B，C都知道
begin //A，B，C表示加数，被加数，和,的第i位
l:=f[a[i]]+f[b[i]]；
case up[i] of
0: begin //0表示不知道，1表示不进位，2表示进位
if (l mod n <>f[c[i]])and((l+1) mod n <>f[c[i]]) then exit(false)；//剪枝
if l div n <>0 then up[i-1]:=2 //进位
else
if(l+1) div n<> 0 then up[i-1]:=2
else up[i-1]:=1；
end；
1: begin
if l mod n <>f[c[i]] then exit(false)； //剪枝
if l div n <>0 then up[i-1]:=2 else up[i-1]:=1；
end；
2: begin
inc(l)；
if l mod n <>f[c[i]] then exit(false)； //剪枝
if l div n <>0 then up[i-1]:=2 else up[i-1]:=1；
end；
end；
end
else
if flag[a[i]] and flag[b[i]] then //只知道A，B
begin
l:=f[a[i]]+f[b[i]]；
case up[i] of
0: begin
if (hash[l mod n]=false)and(l div n <>0) then up[i-1]:=2 //进位
else
if ( hash[(l-1) mod n]=false )and((l+1) div n<> 0) then up[i-1]:=2
else up[i-1]:=1；
if (hash[l mod n]=false)and(hash[(l+1) mod n]=false)and(l=n-1) then up[i-1]:=0； //即上一位的进位直接关系到本位的进位的情况，而上一位是不知道的，所以本位是不是进位是待定的
if (hash[l mod n] )and(hash[(l+1) mod n]) then exit(false)； //剪枝
end；
1: begin
if l div n <>0 then up[i-1]:=2 else up[i-1]:=1； //进位
if hash[l mod n] then exit(false)； //剪枝
end；
2: begin
if l div n <>0 then up[i-1]:=2 else up[i-1]:=1； //进位
inc(l)；
if hash[l mod n] then exit(false)； //剪枝
end；
end；
end
else
if flag[a[i]] and flag[c[i]] then //只知道A，C
begin
l:=f[c[i]]-f[a[i]]；
case up[i] of
0: begin
if (hash[l mod n]=false)and(f[c[i]]<f[a[i]]) then up[i-1]:=2//进位
else
if(hash[(l-1) mod n]=false)and(f[c[i]]-1<f[a[i]]) then up[i-1]:=2
else up[i-1]:=1；
if (hash[l mod n]=false)and(hash[(l-1) mod n]=false)and(f[c[i]]=f[a[i]]) then up[i-1]:=0；
if l<0 then inc(l,n)；//减法有可能出现负数
if (hash[l mod n] )and(hash[(l-1) mod n]) then exit(false)； //剪枝
end；
1: begin
if f[c[i]]<f[a[i]] then up[i-1]:=2 else up[i-1]:=1； //进位
if l<0 then inc(l,n)；
if hash[l mod n] then exit(false)； //剪枝
end；
2: begin
if f[c[i]]-1<f[a[i]] then up[i-1]:=2 else up[i-1]:=1； //进位
dec(l)；
if l<0 then inc(l,n)；
if hash[l mod n] then exit(false)； //剪枝
end；
end；
end
else
if flag[b[i]] and flag[c[i]] then //只知道B，C
begin
l:=f[c[i]]-f[b[i]]；
case up[i] of
0: begin
if (hash[l mod n]=false)and(f[c[i]]<f[b[i]]) then up[i-1]:=2//进位
else
if(hash[(l-1) mod n]=false)and(f[c[i]]-1<f[b[i]]) then up[i-1]:=2
else up[i-1]:=1；
if (hash[l mod n]=false)and(hash[(l-1) mod n]=false)and(f[c[i]]=f[b[i]]) then up[i-1]:=0；
if l<0 then inc(l,n)；
if (hash[l mod n] )and(hash[(l-1) mod n]) then exit(false)； //剪枝
end；
1: begin
if f[c[i]]<f[b[i]] then up[i-1]:=2 else up[i-1]:=1； //进位
if l<0 then inc(l,n)；
if hash[l mod n] then exit(false)； //剪枝
end；
2: begin
if f[c[i]]-1<f[b[i]] then up[i-1]:=2 else up[i-1]:=1； //进位
dec(l)；
if l<0 then inc(l,n)；
if hash[l mod n] then exit(false)； //剪枝
end；
end；
end；
end；
work:=true；//都满足的话，返回true
end；
procedure main(depth:longint)； //简单的搜索
var
i,j,k,l:longint；
begin
if depth>n then print；
for i:=n-1 downto 0 do
if hash[i]=false then
begin
flag[order[depth]]:=true；//标记order[depth]这个字母搜过了
f[order[depth]]:=i；
hash[i]:=true； //标记i这个数字搜过了
if work=false then begin flag[order[depth]]:=false；hash[i]:=false； f[order[depth]]:=0； continue； end； //进行剪枝判断
hash[i]:=true；
main(depth+1)；
f[order[depth]]:=0； //回溯
hash[i]:=false；
flag[order[depth]]:=false；
end；
end；
begin
init；
main(1)；
end.
测试结果：
一：未剪枝裸搜：
编译通过...
├ 测试数据 01：运行超时...
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 806ms
├ 测试数据 05：运行超时...
├ 测试数据 06：运行超时...
├ 测试数据 07：运行超时...
├ 测试数据 08：运行超时...
├ 测试数据 09：运行超时...
├ 测试数据 10：运行超时...
-------------------------
Unaccepted 有效得分：30 有效耗时：806ms
二：按上文剪枝：
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
-------------------------
Accepted 有效得分：100 有效耗时：0ms
测试机vivid puppy （vijos）
Microsoft Windows NT 5.2.3790 Service Pack 1 Intel(R) Xeon(TM) CPU 3.20GHz Phys Memory : 2047MB & Virt Memory : 2048MB
测试数据见附件：
总结：
搜索解决这道题是最容易想到的，但普通的搜索显然会超时，所以剪枝非常重要。
剪枝的原则
1、正确性
枝条不是爱剪就能剪的。如果随便剪枝，把带有最优解的那一分支也剪掉了的话，剪枝也就失去了意义。所以，剪枝的前提是一定要保证不丢失正确的结果。 2、准确性 在保证了正确性的基础上，我们应该根据具体问题具体分析，采用合适的判断手段，使不包含最优解的枝条尽可能多的被剪去，以达到程序“最优化”的目的。可以说，剪枝的准确性，是衡量一个优化算法好坏的标准。 3、高效性 设计优化程序的根本目的，是要减少搜索的次数，使程序运行的时间减少。但为了使搜索次数尽可能的减少，我们又必须花工夫设计出一个准确性较高的优化算法，而当算法的准确性升高，其判断的次数必定增多，从而又导致耗时的增多，这便引出了矛盾。 因此，如何在优化与效率之间寻找一个平衡点，使得程序的时间复杂度尽可能降低，同样是非常重要的。倘若一个剪枝的判断效果非常好，但是它却需要耗费大量的时间来判断、比较，结果整个程序运行起来也跟没有优化过的没什么区别，这样就太得不偿失了。 综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。
还有搜索题除了要掌握一般的技巧，也要对每道题的内涵进行挖掘，找到其特性。对症下药才可有用。