單詞方程 解題報告

題目描述

單詞方程

二元詞是一個由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} 
当前页阅读量为: