Poj1733 Parity game & Poj1182 食物链 — 并查集的扩展域方法

Note: 本文最初于 2011年 在 hi.baidu.com/lydrainbowcat 发表。

Poj1733:

1. 把问题转化为并查集模型:
a b even等价于(0..a-1)与(0..b)同奇同偶
a b odd等价于(0..a-1)与(0..b)不同奇不同偶
我们用same和diff两个数组来代表每个点的相同和不同,比如令same[i]=i,diff[i]=i+10000(这个你随便加啦,只要不重复就好)。
对于集合的合并:
对于a b even,就union(same(a-1),same(b)),union(diff(a-1),diff(b)),表示a~b有偶数个的话,0~a-1必然和0~b是同奇同偶或异奇异偶。
对于a b odd,则union(same(a-1),diff(b)),union(diff(a-1),same(b))。
对于判断是否合法:
a b even,则find(same(a-1))=find(same(b)),此时必然同时有find(diff(a-1))=find(diff(b))
a b odd,则find(diff(a-1))=find(same(b)),此时必然同时有find(same(a-1))=find(diff(b))
这样就可以判断了.循环每个提问,先判断,不符合就writeln&break, 否则union;

2. 解决01串长的问题——利用哈希表:
经过上面的分析还是不行,01串长度为十亿,你直接存必然MLE,但注意到问答之后5000个所以使用哈希表(开散列),mod一个数,比如10009这样的质数。
这样的话经过映射就解决啦!不多说了,还不懂的话,去看程序。
总的来说,这道题综合了并查集和哈希表,而且需要一番思考才可以转化,是一道很有价值的题!

Source Code

Problem: 1733 User: lydliyudong
Memory: 1600K Time: 63MS
Language: Pascal Result: Accepted
    • Source Code
var
 same,diff,link,next:array[0..20000]of longint;
 fa:array[0..40000]of longint;
 head:array[0..99990]of longint;
 n,q,a,b,a1,b1,a2,b2,i,tot:longint;
 ch:char;

function find(x:longint):longint;
 begin
  if x=fa[x] then exit(x);
  fa[x]:=find(fa[x]);
  exit(fa[x]);
 end;

function hash(x:longint):longint;
 var
  i,p:longint;
 begin
  p:=x mod 99991;
  i:=head[p];
  while i<>0 do
   begin
    if link[i]=x then exit(i);
    i:=next[i];
   end;
  inc(tot);
  link[tot]:=x;
  next[tot]:=head[p];
  head[p]:=tot;
  exit(tot);
 end;

begin
 readln(n,q);
 if q=0 then writeln(0); 
 for i:=0 to 40000 do fa[i]:=i;
 for i:=0 to 20000 do begin same[i]:=i; diff[i]:=i+20000; end;
 for i:=1 to q do
  begin
   readln(a,b,ch,ch);
   dec(a);
   a:=hash(a);
   b:=hash(b);
   a1:=find(same[a]);
   a2:=find(diff[a]);
   b1:=find(same[b]);
   b2:=find(diff[b]);
   case ch of
    'o':
     begin
      if (a1=b1)or(a2=b2) then begin writeln(i-1); break; end;
      fa[a1]:=b2;
      fa[a2]:=b1;
     end;
    'e':
     begin
      if (a1=b2)or(a2=b1) then begin writeln(i-1); break; end;
      fa[a1]:=b1;
      fa[a2]:=b2;
     end;
   end;
   if i=q then writeln(q);
  end;
end.

Poj1182:

维护三个域:同类域(自身域)、吃域、被吃域。

若A吃B,B吃C,C吃A,则A的吃域=B的同类域=C的被吃域,A的被吃域=C的同类域=B的吃域,A的同类域=C的吃域=B的被吃域。

只需要通过维护这些域之间的关系便可判断生物之间的关系。

Source Code

Problem: 1182 User: lydliyudong
Memory: 1476K Time: 204MS
Language: Pascal Result: Accepted
    • Source Code
var
 fa:array[0..150000]of longint;
 n,m,x,y,z,x1,x2,x3,y1,y2,y3,ans,i:longint;
function find(x:longint):longint;
 begin
  if fa[x]=x then exit(x);
  fa[x]:=find(fa[x]);
  exit(fa[x]);
 end;
begin
 read(n,m);
 for i:=1 to 3*n do fa[i]:=i;
 for i:=1 to m do
  begin
   read(z,x,y);
   if (x>n)or(y>n) then begin inc(ans); continue; end;
   x1:=find(x); x2:=find(x+n); x3:=find(x+2*n);
   y1:=find(y); y2:=find(y+n); y3:=find(y+2*n);
   case z of
    1:
     begin
      if (x1=y2)or(y1=x2) then inc(ans)
      else begin
       fa[x1]:=y1;
       fa[x2]:=y2;
       fa[x3]:=y3;
      end;{else}
     end;
    2:
     begin
      if (x1=y1)or(x1=y2) then inc(ans)
      else begin
       fa[y1]:=x2;
       fa[y3]:=x1;
       fa[x3]:=y2;
      end;{else}
     end;
   end;{case}
  end;
 writeln(ans);
end.

发表评论

电子邮件地址不会被公开。 必填项已用*标注