讨论 / 解题思路
stone! 2014-05-12 00:46:23
点我顶贴 收藏 删除
测试点1 Accepted / 13ms / 236kB

测试点2 Accepted / 12ms / 236kB

测试点3 Accepted / 9ms / 236kB

测试点4 Accepted / 6ms / 236kB

测试点5 Accepted / 7ms / 236kB

测试点6 Accepted / 20ms / 236kB

测试点7 Accepted / 7ms / 236kB

测试点8 Accepted / 173ms / 236kB

测试点9 Accepted / 9ms / 236kB

测试点10 Accepted / 4ms / 236kB

var i,q,n:integer;

ss1:string;

s:array[0..3,0..400]of integer;

p:array[0..400]of integer;

f:array[-1..400]of boolean;

function exam(j:integer):boolean;

var i,t1,t2,t3:integer;

begin

exam:=true;

for i:=1 to j-1 do

begin

t1:=p[s[1,i]]; t2:=p[s[2,i]]; t3:=p[s[3,i]];

if (f[t1])and(f[t2])and(f[t3]) then //当某列三行都枚举了数字时

begin

if ((t1+t2)mod n<>t3)and((t1+t2+1)mod n<>t3)

//如果这个枚举是正确的,那么a+b mod n或者a+b+1 mod n一定等于c

then exit(false);

end;

end;

end;

function cut(j:integer):integer; //判断当1,2字符串数字已经确定,3字符串对应的数字

var sp,ad:integer;

begin

ad:=0;

for sp:=length(ss1) downto j+1 do //由于存在进位,需从右到左走一遍

ad:=(ad+p[s[1,sp]]+p[s[2,sp]]) div n;

cut:=(p[s[1,j]]+p[s[2,j]]+ad)mod n;

end;

procedure solve(i,j:integer);

var ii,jj,tt,ft:integer;

begin

tt:=s[i,j];

if j=0 then //结束输出结果

begin

for ii:=ord('A') to ord('A')+n-2 do

write(p[ii],' ');

write(p[ii+1]);

halt;

end

else

begin

if p[tt]<>-1 then //如果当前字符已经确认了对应的数字

begin

if (i=1)or(i=2) then solve(i+1,j);

if (i=3)and(cut(j)=p[s[3,j]]) then solve(1,j-1); //剪枝,如果是第三行需要确认是否正确

end

else

begin

if (i=1)or(i=2)then

begin

for ii:=n-1 downto 0 do //逆序枚举效率高,0出现可能性极低

if (f[ii]=false)and(exam(j)) then //如果是新的字符,则递归枚举求解,exam是重要剪枝

begin

p[tt]:=ii;f[ii]:=true;

solve(i+1,j);

p[tt]:=-1;f[ii]:=false;

end;

end

else

begin

ft:=cut(j); //如果处于第三行,又没有枚举过,则直接计算出第三行的数字

if not(f[ft]) then

begin

p[tt]:=ft;f[ft]:=true;

solve(1,j-1);

p[tt]:=-1;f[ft]:=false;

end;

end;

end;

end;

end;

begin

readln(n);

for i:=1 to 3 do

begin

readln(ss1);

for q:=1 to length(ss1) do

s[i,q]:=ord(ss1[q]);

end;

for i:=ord('A') to ord('A')+n do

p[i]:=-1;

solve(1,length(ss1));

end.

代码不超过90行,整体上代码的效率非常高,没做编写优化,大家参考即可。

p数组用来表示每个字符对应的数字,f数组解决每个字符只能一个数字的占位问题。

递归求解,是字符串从右到左,从上到下。优化点在代码中做简单的解释。

查看更多回复
提交回复