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.