TOI 1110 — 01字符串问题
这道题是山东2007年第二次省选的题目,和这道题几乎一样的题目还在这些地方出现过:POJ 1733; URAL 1003; Vijos 1112; CEOI 99 Bugs.
看出现在这么多地方就知道应该是道很经典的题目了…
当时jl刚跟我说这道题,我就反应到了食物链那道题,但是后来jl说有mlogn的算法我就没向并查集方面想…后来发现的确是部分和+并查集,和我最开始的想法一样.算法复杂度O(m*alpha()),近似看作O(m).不过mlogn的算法没想出来.
首先,对于一个条件x y z,如果z=0,相当于转换为,对于一个只存有0和1的数组a[],a[x-1]和a[y]数组中存储的数相同.那么z=1就是存储的数不同.这里很好用部分和和奇偶性的知识解释,不赘述.这样,每次判断z,并判断x和y的关系,根据关系进行合并.用mark[x]记录树x的”敌人”(就是和a[x]存储的数不同的某一个位置–可以知道这个位置一定最多只有一个,多于一个时可以合并).
然后进行各种合并,具体方法看程序(主程序)中的判断部分.顺便判当前条件是否与之前的条件冲突.
这道题1Y,其实还是比较简单的,只不过判断的地方恶心了些,写到一半删了重写了一次…
{ TOI 1110; 01字符串问题 - sqybi’s code - 部分和+并查集}//for my winsty{$APPTYPE CONSOLE}program str_sqybi; const fin = ’str.in’; fout = ’str.out’; nn = 50000;
var n, m, i, x, y, z, fx, fy, t, total: longint; father, mark, size: array[1..nn+1]of longint;
function getF(x: longint): [...]