单词方程解题报告 | 宁心勉学，慎思笃行

题目描述

单词方程

二元词是一个由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发布，转载需附带本文链接。

题目描述

解题思路

问题

猜你喜欢