(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那么 A<E则进位否则不进(上一位进位则(A-1)<E ) 特殊情况:同(2)。
(4)
知道A,D那么 D<E则进位否则不进(上一位进位则(A-1)<D ) 特殊情况:同(2)。
(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、高效性 设计优化程序的根本目的,是要减少搜索的次数,使程序运行的时间减少。但为了使搜索次数尽可能的减少,我们又必须花工夫设计出一个准确性较高的优化算法,而当算法的准确性升高,其判断的次数必定增多,从而又导致耗时的增多,这便引出了矛盾。 因此,如何在优化与效率之间寻找一个平衡点,使得程序的时间复杂度尽可能降低,同样是非常重要的。倘若一个剪枝的判断效果非常好,但是它却需要耗费大量的时间来判断、比较,结果整个程序运行起来也跟没有优化过的没什么区别,这样就太得不偿失了。 综上所述,我们可以把剪枝优化的主要原则归结为六个字:正确、准确、高效。
还有搜索题除了要掌握一般的技巧,也要对每道题的内涵进行挖掘,找到其特性。对症下药才可有用。