测试点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数组解决每个字符只能一个数字的占位问题。
递归求解,是字符串从右到左,从上到下。优化点在代码中做简单的解释。