集训队作业-9806解题报告

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);{统计根结点的个数}