POIVStage2Problem2Wordequations《單詞等式》解題報張家復旦大學附屬中就變得復雜起來了。那么首先讓來研究一下這種對應之間的關系。12345678911每一列的對應并不是單獨的，a114a447聯系了起來，1112聯系了起來，所以得到位置1，4，7，12是彼此相關聯的，又其中有1出現所以這四個位1。……（1，4，7，12（2，5，9（3，6，10（8（1）142^4=16。通過上面的例子可以看到：這道題實際上就是求這樣兩個01串中有幾個位置是可以互不相關的隨機取值的，或者說就是確定有幾個如上例中的位置可以用并查集來實現。注意：如果0與1被放入了同一個集合則應該失敗退將所有的字母每一位上（字母代表多個數字）所在集合放入一個數組s中，并用s[0]表示數字0的所在集合，s[1]表示數字1的。舉個例子說，對abcde長度分別為42442時，s[2]表示a[1]的，s[3]a[2]的，s[6]表示b[1]的，而s[16]e[1]的。s（下標： s ： ： ： ： ： ： ： ： 最終檢查一下所在集合仍為自己本身的集合個數，注意要除去s[0]與基本上在O(n)的時間內出解。關于并查集的具體算法，詳見POI9816《矩形》解時間復雜度：O(na(n));a(n)n增長極為緩慢，可以認為是一個常數。programconst :array[0..2*maxn]ofinteger;{用于并查 :array[0..25,1..2]of{字母在數組s中的起始位置以及字母代表的01串長度 :array[1..maxn]ofinteger;{等式 :array[0..25]ofproceduremake;{ procedurereadin;{讀入過程}vari,j,k,now,m fori:=0ton-1doread(long[i,2]);fori:=1tondolong[i,1]:=long[i-1,1]+long[i-1,2];forj:=1tomdoif(x='1')or(x='0')thent[i]:=ord(x)-fork:=itoi+long[now,2]-1dofunction vari,j,k whiles[i]<>i:=s[i];whiles[i]<>jdobegink:=s[i];s[i]:=j;i:=k;end;procedureadd(x,y varx1,x2 ifx1<>x2thens[x2]:=x1;procedure forj:=1tomdoif(x='1')or(x='0')thenadd(ord(x)-fork:=itoi+long[now,2]-1do{集合合并}ifi<>t1thens[1]:=s[0];{如果等式兩邊長度不同，失敗退出}procedurewriteout(ansvara :array[1..10000]ofinteger; procedurecheng;{var fori:=1toaadoy:=(a[i]*1024+x)diva[i]:=(a[i]*1024+x)mod10; x<>0dobegininc(aa);a[aa]:=xmod10;x:=xdiv10;end;ifans=0thenbeginwrin('1');exit;end;fori:=1to(ansmod10)dofori:=1to(ansdiv10)dofori:=aadownto1dofori:=0tonndos[i]:=i;iffa(0)=fa(1)thenbeginwrifori:=0ton-1doifnotv[i]thenforj:=long[i,1]tolong[i,1]+long[i,2]-1dofori:=2tonnfs[i]=itheninc(ans);{統計根結點的個數}