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): longint;
var
y, z: longint;
begin
y := x;
while father[x] <> 0 do
x := father[x];
while father[y] <> 0 do begin
z := father[y];
father[y] := x;
y := z;
end;
getF := x;
end;
procedure combine(x, y: longint);
var
t: longint;
begin
if size[x] > size[y] then begin
t := x;
x := y;
y := t;
end;
father[x] := y;
size[y] := size[y] + size[x];
end;
begin
assign(input, fin);
assign(output, fout);
reset(input);
rewrite(output);
readln(n, m);
total := 0;
for i:=1 to n+1 do begin
father[i] := 0;
size[i] := 1;
end;
for i:=1 to m do begin
readln(x, y, z);
inc(y);
fx := getF(x);
fy := getF(y);
if z = 0 then begin
if mark[fx] = fy then begin
inc(total);
continue;
end;
if fx = fy then continue;
if (mark[fx] = 0) and (mark[fy] = 0) then begin
combine(fx, fy);
end
else if (mark[fx] <> 0) and (mark[fy] <> 0) then begin
combine(fx, fy);
combine(mark[fx], mark[fy]);
t := mark[fx];
mark[getF(t)] := getF(fx);
mark[getF(fx)] := getF(t);
end
else if mark[fy] = 0 then begin
combine(fx, fy);
t := mark[fx];
mark[t] := getF(fx);
mark[getF(fx)] := t;
end
else if mark[fx] = 0 then begin
combine(fx, fy);
t := mark[fy];
mark[t] := getF(fy);
mark[getF(fy)] := t;
end;
end
else begin
if fx = fy then begin
inc(total);
continue;
end;
if mark[fx] = fy then continue;
if (mark[fx] = 0) and (mark[fy] = 0) then begin
mark[fx] := fy;
mark[fy] := fx;
end
else if (mark[fx] <> 0) and (mark[fy] <> 0) then begin
combine(mark[fx], fy);
combine(mark[fy], fx);
mark[getF(fx)] := getF(fy);
mark[getF(fy)] := getF(fx);
end
else if mark[fy] = 0 then begin
combine(mark[fx], fy);
mark[fx] := getF(fy);
mark[getF(fy)] := fx;
end
else if mark[fx] = 0 then begin
combine(mark[fy], fx);
mark[fy] := getF(fx);
mark[getF(fx)] := fy;
end;
end;
end;
writeln(total);
close(input);
close(output);
end.
阅读(298 次)