虫食算

虫食算是一种用字母或者说空格来代替数字的算式，由做题者复原算式。现在，我们一般称其为"数字谜"或者说"数字谜题"。它对于开发智力具有一定的作用。

• 中文名称 虫食算
• 属于 算式
• 包含 用字母或者说空格来代替数字
• 对于 开发智力具有一定的作用

出处

　　NOIP2004提高组复赛最后一题:虫食算。

　　虫食算

　　(alpha.pas/dpr/c/cpp)

问题描述

　　所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子:

　　43#98650#45

　　+ 8468#6633

来自　　44445506978

　　其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断:第一行的两个数字分别是5和3，第二行的数字是5。

　　我们对问题做两个限制:

　　浓选首先，我们只考虑加法的虫食算。司犯这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。

　　突铁前快势对难其次，虫子把所有的数都啃光了，360百科我们只知道哪些数字是相同的造针够严上，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个比族站方直大写字母来表示这个算式中的0到N-1这N个不同的数字:但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母养我热行分别至少出现一次。

　　BADC

　　+ CBDA

　　DCCC

　　上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别府备可代表的数字，使得该加你治集和十八承将书法算式成立。输入数据保证有且仅有一组采类概办事乡跟都指写活解，

输入文记件

　　输入文件包含4行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组命属阻乡么通谁未成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。

输出文件

　　输出文件alpha.out包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的:输出N个数字，分别表示A，B，C……所代表的数字，相邻治怎等混重判纪言的两个数字用一个空格隔开，不能有多余的空格。

样例输入

　　5

　　A来自BCED

　　BDACE

　　E雷普钱她BBAA

样例输出

　360百科　1 0 3 4 2

数据规模

　　对于30%的数据，保证有N<=10;

　　对于50%的数据，保证有N<=15;

　　对于全部的数据，保证有N<=26。

解题报告

　　经典的搜索题。最单纯的搜索的时间复杂度为O(n!)，是会非常严重的超时的。计算机是很"笨"的，它不会思考，在盲目呢搜索的过程中，很容易出现这种情况:

　　计算机在某一位搜索出了一个算式1 + 1 = 3，并且继续搜索。

　　明显，人眼很容易就看出这是不合法的，但计算机不会。于是，我们想到了第一个剪枝:每次搜索的时候，从最后向前判入内贵多断是否有不合法的式子。

　　这拿同钢一个剪枝非常简单，但是效果却非常的好。因为它士五剪去了很多不必要的搜索。为了配合这一种剪枝更好的实行，搜索顺序的改变也成为大大提高程序效率的关键:从右往左，按照字母出现顺序搜索，有很大程度上提高了先剪掉废枝的情况，使程序的效率得到大大的提高。

　　有了以上两个剪枝，程序就已经可以通过大部分测试点了。但是有没有更多的剪枝呢?答案是肯定的。

　　粮亚室振百编若到反全根据前面的剪枝，我们可以找到类似的几个剪枝:

　　对于a + b = c的形式，假如:

　　A***?**指白常百通住教质哪*

　　+ B*?**?**

　　C***???*

　　其中*代表已知，?代表未知。那么，A + B与C的情况并不能直接确定。但是，假如(A + B) % N与(A + B + 1) % N都不等于C的话，那么这个等式一定是不合法的。因为它只有进位和不进位的两种情况。

　　同样，我们在一个数卷组里记录了Used表示一个和学模音祖决转京他数字有没有用过，那么，对于某一位A + B = C的等式，如果已经得到了两个数，另一个数还待搜索的时候，我们还可以根据这个加入一个剪枝:

　　例免须需义如A + ? = C的形式，

　　考虑不技棉似某在往成图兵度进位的情况，则?处为P1 = (C - A + N) % N

　　假如考虑进位的情况，则?处为P2 = (C - A - 1 + N) % N

　　假如P1、P2均被使用过，那么这个搜索一定是无效的坏别查布，可以剪去。

　　有了以上的剪枝，就可以很轻松地通过所有的测试数据了。当然，还有很多值得思考的剪枝以及其他的思路办及却注密延伟钱，例如枚举进位、解方程(但是可能需要枚举)等，在这里就不详细讨老论了。

代码清单

　　C++语言实现

　　pascal实现

　　v效作孔假县根盾ar

　　a:Array[1..3,1..26]of char;

　　b:array['A'..'Z']of longint;

　　c:array[0..25]of boolean;

　　i,j,n:longint;

　　function check(x,m:longint):boolean;

　　var

　　yy:boolean;

　　i,j:longint;

　　begin

　　if ((b[a[1,x]]+b[a[2,x]]+m)mod n<>b[a[3,x]]) then exit(false);

　　for i:=1 to x-1 do

　　if (b[a[1,i]]<>-1)and(b[a[2,i]]<>-1)and(b[a[3,i]]<>-1)then

　　begin

　　yy:=true;

　　for j:=0 to 1 do

　　if (b[a[1,i]]+b[a[2,i]]+j)mod n=b[a[3,i]] then yy:=false;

　　if yy then exit(false);

　　end;

　　check:=true;

　　end;

　　procedure dfs(x,m:longint);

　　var i,j,d,p,mm:longint;

　　aa,bb,cc:boolean;

　　begin

　　if x=0 then begin

　　if m=0 then

　　begin

　　for i:=1 to n do write(b[chr(i+64)],' ');

　　close(input);close(output);

　　halt;

　　end;

　　exit;

　　end;

　　aa:=false;

　　bb:=false;

　　cc:=false;

　　if b[a[1,x]]<>-1 then aa:=true;

　　if b[a[2,x]]<>-1 then bb:=true;

　　if b[a[3,x]]<>-1 then cc:=true;

　　if (aa and bb and cc) then

　　begin

　　if check(x,m) then dfs(x-1,(m+b[a[1,x]]+b[a[2,x]])div n);

　　end

　　else if aa and bb then

　　begin

　　d:=(b[a[1,x]]+b[a[2,x]]+m)mod n;

　　if c[d] then

　　begin

　　b[a[3,x]]:=d;

　　c[d]:=false;

　　mm:=(b[a[1,x]]+b[a[2,x]]+m)div n;

　　if check(x,m) then dfs(x-1,mm);

　　c[d]:=true;

　　b[a[3,x]]:=-1;

　　end;

　　end

　　else if aa and cc then

　　begin

　　d:=(b[a[3,x]]-m-b[a[1,x]]+n)mod n;

　　if c[d] then

　　begin

　　b[a[2,x]]:=d;

　　c[d]:=false;

　　mm:=(d+b[a[1,x]]+m)div n;

　　if check(x,m) then dfs(x-1,mm);

　　m:=mm;

　　c[d]:=true;

　　b[a[2,x]]:=-1;

　　end;

　　end

　　else if bb and cc then

　　begin

　　d:=(b[a[3,x]]-m-b[a[2,x]]+n)mod n;

　　if c[d] then

　　begin

　　b[a[1,x]]:=d;

　　c[d]:=false;

　　mm:=(d+b[a[2,x]]+m)div n;

　　if check(x,m) then dfs(x-1,mm);

　　m:=mm;

　　c[d]:=true;

　　b[a[1,x]]:=-1;

　　end;

　　end

　　else if (not aa)and(not bb)and(not cc) then

　　begin

　　if a[1,x]<>a[2,x] then

　　begin

　　for i:=n-1 downto 0 do

　　for j:=n-1 downto 0 do

　　if (c[i] and c[j])and(i<>j) then

　　begin

　　c[i]:=false;

　　c[j]:=false;

　　b[a[1,x]]:=j;

　　b[a[2,x]]:=i;

　　dfs(x,m);

　　c[i]:=true;

　　c[j]:=true;

　　b[a[1,x]]:=-1;

　　b[a[2,x]]:=-1;

　　end;

　　end

　　else

　　for i:=n-1 downto 0 do

　　if c[i] then

　　begin

　　b[a[1,x]]:=i;

　　c[i]:=false;

　　dfs(x,m);

　　b[a[p,x]]:=-1;

　　c[i]:=true;

　　end;

　　end

　　else begin

　　for i:=n-1 downto 0 do

　　if c[i] then

　　begin

　　if not aa then p:=1

　　else if not bb then p:=2

　　else if not cc then p:=3;

　　b[a[p,x]]:=i;

　　c[i]:=false;

　　dfs(x,m);

　　b[a[p,x]]:=-1;

　　c[i]:=true;

　　end;

　　end;

　　end;

　　begin

　　readln(n);

　　for i:=1 to 3 do

　　begin

　　for j:=1 to n do

　　read(a[i,j]);

　　readln;

　　end;

　　fillchar(b,sizeof(b),255);

　　fillchar(c,sizeof(c),true);

　　dfs(n,0);

　　end.

　　总结

　　搜索题的框架往往不难找到，关键就是在搜索的优化上，本文的主要篇幅也就是讨论了几种有效的优化。搜索问题的优化更多的需要选手的经验和思考、分析问题的能力，所以搜索剪枝也是竞赛中经久不衰的经典问题。