首页 > 代码库 > CODEVS1533(哈希表)
CODEVS1533(哈希表)
给定一个集合,要求一个最大子集,满足两两之间不互斥。对两个数x,y互斥的定义是,y=p*x。
先对集合中的数从小到大排序后线性扫,若一个数x可以取则取,取完之后p*x这个数不可取。由于数字较大,使用哈希表来判断。
1 Program CODEVS1533; 2 const maxn=1000007; 3 var a,f:array[0..maxn] of longint; 4 num,m,n,i,j,k,x,y,z:longint; 5 procedure sort(l,r: longint); 6 var 7 i,j,x,y: longint; 8 begin 9 i:=l;10 j:=r;11 x:=a[(l+r) div 2];12 repeat13 while a[i]<x do14 inc(i);15 while x<a[j] do16 dec(j);17 if not(i>j) then18 begin19 y:=a[i];20 a[i]:=a[j];21 a[j]:=y;22 inc(i);23 j:=j-1;24 end;25 until i>j;26 if l<j then27 sort(l,j);28 if i<r then29 sort(i,r);30 end;31 procedure insert(x:longint);32 var h:longint;33 begin34 h:=x mod maxn;35 while (f[h]<>0) and (f[h]<>x) do36 h:=(h+1) mod maxn;37 f[h]:=x;38 end;39 function find(x:longint):boolean;40 var h:longint;41 begin42 h:=x mod maxn;43 while (f[h]<>0) and (f[h]<>x) do44 h:=(h+1) mod maxn;45 if f[h]=0 then exit(false) else exit(true);46 end;47 begin48 readln(n,m);49 for i:=1 to n do read(a[i]);50 sort(1,n);51 num:=0;52 for i:=1 to n do53 begin54 if find(a[i]) then continue;55 inc(num);56 insert(a[i]*m);57 end;58 writeln(num);59 end.
CODEVS1533(哈希表)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。