单词方程 解题报告
题目描述
单词方程
二元词是一个由0和1组成的非空串。一个单词方程是一个形如X1X2..Xl=Y1Y2..Yr的等式，其中 Xi 和Yj 是二进制数字 (0 和 1) 或者变量（小写英文字母）。每个变量都代表某个固定长度的二元词，这个长度被称作该变量的长度。要解一个单词方程，我们必须赋给每个变量一个适当长度的二元词（这个二元词的长度必须和变量的长度相等），使得当所有变量都用所对应的二元词替换完毕后，等式两边（替换的来的二元词）相同。
请计算一个给定的单词方程的所有解的总数。
例如：
假设a、b、c、d、e 是长度分别为4、2、4、4、2的变量（a的长度是4，b的长度是2……）。则方程1bad1 = acbe有16组不同的解。
求解任务：
请设计一个程序，从文件ROW.IN中读入方程的总数以及每个方程的信息； 求出每个方程解的个数； 将结果写到文件ROW.OUT中。
输入： 在输入文件ROW.IN的第一行是一个整数x（1<=x<=5），表示文件中包含的方程的总数。
接下来的部分包含对于这x个方程的描述。每个方程的描述由6行组成，描述之间没有多余的空行。
每个方程用以下格式描述：第一行是一个整数k，0 <= k <= 26，表示当前方程中变量的数目。这k个变量用前k个小写英文字母表示。第二行有k个由空格分隔的正整数，表示变量a、b、…… 的长度。第三行是一个整数l，表示方程左端的长度（即由0、1以及小写英文字母组成的串的长度）。方程左端在下一行中以一个数字和字母组成的串的形式给出，中间不含空格。
接下来的两行包含对于方程右端的描述。首先是一个正整数r，表示方程右端的长度。接下来的一行给出方程的右端，表示的方法与左端相同。
对于方程的左右两端，所有数字的总数加上所有变量的长度之和（变量每出现一次都计入总长）不会超过10000。
输出： 请将第1..x个方程的解的总数写到输出文件ROW.OUT的第1..x行。
样例输入： 1 5 4 2 4 4 2 5 1bad1 4 acbe
样例输出： 16
解题思路
这道题是典型的并查集。将每个字母的每一位和0、1看作一个节点，然后将左右两端的每一位的节点合并。
如果出现0，1同父或字母数为0但左右输入字符串却不相等则输出0，否则输出 q*2 q*2，其中q代表父亲不重复并且父亲和0、1不同的个数。和0、1父亲相同的均被固定，所以结果乘以1，等于没乘。
问题
通过 FreePascal IDE 编译测试无问题，但 Cena 每次评测都随机出错，出错的地点和错误的类型每次都不一样，不知道是什么原因。调查中。如某位神牛能够从鄙人的代码中发现问题，也请提醒一下，谢谢。
//本解题报告的代码版权归 Ceeji 所有，如需转载请注明出处和本注释。
//By Ceeji
//HAOI Test 4 - Problem 2 : Row
//Type: Union-find Sets
//Date: 2009-4-5
//States: Programing
Program Row;
Const inf='row.in';
ouf='row.out';
maxn=26;
maxl=10000;
Var n,u,k:longint;
len:array[1..maxn]of integer;
str1,str2:ansistring;
f1:array['a'..'z',-1..maxl]of char;
f2:array['a'..'z',-1..maxl]of integer;
ls1,rs1:array[1..maxl]of char;
ls2,rs2:array[1..maxl]of integer;
b:array['a'..'z',-1..maxl]of boolean;
Procedure init;
begin
assign(input,inf); reset(input);
assign(output,ouf); rewrite(output);
readln(n);
end;
Procedure getFather(c:char; p:longint;var d:char;var q:longint);
begin
if (f1[c,p]=c)and(f2[c,p]=p) then begin d:=c; q:=p; exit; end;
getFather(f1[c,p],f2[c,p],d,q);
f1[c,p]:=d; f2[c,p]:=q;
end;
Procedure work;
var i,j,l,p,q,y,ff1,ff2,ff3,ff4:longint;
c,c1,c2,c3,c4:char;
ans:longint;
begin
readln(k);
fillchar(f1,sizeof(f1),0);
fillchar(f2,sizeof(f2),0);
fillchar(len,sizeof(len),0);
fillchar(ls1,sizeof(ls1),0);
fillchar(rs1,sizeof(rs1),0);
fillchar(ls2,sizeof(ls2),0);
fillchar(rs2,sizeof(rs2),0);
f1['a',-1]:='a'; f2['a',-1]:=-1;
f1['a',0]:='a'; f2['a',0]:=0;
for i:=1 to k do
begin
read(len[i]);
c:=chr(96+i);
for j:=1 to len[i] do
begin
f1[c,j]:=c;
f2[c,j]:=j;
end;
end;
readln(l);
readln(str1);
readln(l);
readln(str2);
if (k=0) then
begin
if str1=str2 then writeln('1')
else writeln('0');
exit;
end;
p:=length(str1);
j:=0;
for i:=1 to p do
begin
c:=str1[i];
if c='0' then
begin
inc(j);
ls1[j]:='a'; ls2[j]:=0;
continue;
end
else if c='1' then
begin
inc(j);
ls1[j]:='a'; ls2[j]:=-1;
continue;
end
else
begin
q:=len[ord(c)-96];
for y:=1 to q do
begin
inc(j); ls1[j]:=c; ls2[j]:=y;
end;
end;
end;
p:=length(str2);
j:=0;
for i:=1 to p do
begin
c:=str2[i];
if c='0' then
begin
inc(j);
rs1[j]:='a'; rs2[j]:=0;
continue;
end
else if c='1' then
begin
inc(j);
rs1[j]:='a'; rs2[j]:=-1;
continue;
end
else
begin
q:=len[ord(c)-96];
for y:=1 to q do
begin
inc(j); rs1[j]:=c; rs2[j]:=y;
end;
end;
end;
for i:=1 to j do
begin
getFather(ls1[i],ls2[i],c1,ff1);
getFather(rs1[i],rs2[i],c2,ff2);
f1[c1,ff1]:=c2; f2[c1,ff1]:=ff2;
end;
y:=0; q:=0;
fillchar(b,sizeof(b),0);
getFather('a',0,c3,ff3); getFather('a',-1,c4,ff4);
if (c3=c4)and(ff3=ff4) then begin writeln('0'); exit; end;
for i:=1 to k do
begin
if i=1 then p:=-1 else p:=1;
for j:=p to len[i] do
begin
getFather(chr(96+i),j,c1,ff1);
if (b[c1,ff1]=false)and(((c1=c3)and(ff1=ff3))=false)and(((c1=c4)and(ff1=ff4))=false) then
begin
inc(q);
b[c1,ff1]:=true;
end
else if (c1<>'a')or(ff1>0) then
inc(y);
end;
end;
writeln(2**q);
end;
Procedure endPro;
begin
close(input); close(output);
exit;
end;
{main}
begin
init;
for u:=1 to n do
work;
endPro;
end.{main}
题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。
© 转载需附带本文链接，依据 CC BY-NC-SA 4.0 发布。