有这样的一个集合，集合中的元素个数由给定的N决定，集合的元素为N个不同的正整数，一旦集合中的两个数x,y满足y = P*x，那么就认为x,y这两个数是互斥的，现在想知道给定的一个集合的最大子集满足两两之间不互斥。
输入有多组数据，每组第一行给定两个数N和P（1<=N<=10^5, 1<=P<=10^9）。接下来一行包含N个不同正整数ai（1<=ai<=10^9）。
输出一行表示最大的满足要求的子集的元素个数。
4 2
1 2 3 4
3
#include<iostream> #include<map> #include<algorithm> using namespace std; int s[100000]; map<int,bool>d; int main() { int h,n,p; cin>>n>>p; h=0; for(int i=1;i<=n;++i) cin>>s[i]; sort(s+1,s+1+n); for(int i=1;i<=n;++i) { if(!d[s[i]]) { d[s[i]*p]=1; h++; } } cout<<h; }
哈希 做法 21ms 876KB 1213B
#include <algorithm> #include <cstdio> using namespace std; struct node { int to,next,cs; bool vis; }edge[50001]; int head[50001],n,p,a[100001],tot; int qr() { int x=0,f=1; char ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(int)ch-48;ch=getchar();} return x*f; } int get_hash1(int k) { return k*13%20047; } int get_hash2(int k) { return k*19%13831; } void add(int from,int to) { tot++; edge[tot].next=head[from]; edge[tot].to=to; head[from]=tot; } void change(int u,int v) { for(int j=head[u];j;j=edge[j].next) { if(edge[j].to==v) { edge[j].vis=1; } } } int pd(int u,int v) { for(int k=head[u];k;k=edge[k].next) { if(edge[k].to==v&&edge[k].vis==0) return true; } return false; } int main() { n=qr(); p=qr(); for(int i=0;i<n;++i) { a[i]=qr(); int x=get_hash1(a[i]); int y=get_hash2(a[i]); add(x,y); } sort(a,a+n); int h=0,ans=n; for(int i=0;i<n;++i) { int x=get_hash1(a[i]),y=get_hash2(a[i]); if(pd(x,y)) { int t=a[i]*p; int x=get_hash1(t),y=get_hash2(t); change(x,y); h++; } } printf("%d\n",h); return 0; }
原文：http://www.cnblogs.com/ruojisun/p/6415769.html
