首页 > 代码库 > 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(哈希表)