單詞方程 解題報告
題目描述
單詞方程
二元詞是一個由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}
© 轉載需附帶本文連結，依 CC BY-NC-SA 4.0 釋出。