有這樣的一個(gè)集合，集合中的元素個(gè)數(shù)由給定的N決定，集合的元素為N個(gè)不同的正整數(shù)，一旦集合中的兩個(gè)數(shù)x,y滿足y = P*x，那么就認(rèn)為x,y這兩個(gè)數(shù)是互斥的，現(xiàn)在想知道給定的一個(gè)集合的最大子集滿足兩兩之間不互斥。

輸入有多組數(shù)據(jù)，每組第一行給定兩個(gè)數(shù)N和P（1<=N<=10^5, 1<=P<=10^9）。接下來一行包含N個(gè)不同正整數(shù)ai（1<=ai<=10^9）。

輸出一行表示最大的滿足要求的子集的元素個(gè)數(shù)。

4 2

1 2 3 4

3

題解：dfs+map 

這道題剛開始一直在想2-sat，但是發(fā)現(xiàn)只能判斷是否有合法的解，并不能找出滿足條件的最大子集（最起碼我不會(huì)）。

然后開始想hash，又不是什么序列，hash個(gè)屁啊，根本不可做么。

然后開始分析互斥關(guān)系，發(fā)現(xiàn)所有的互斥關(guān)系形成的都是互不相交的鏈，對(duì)于鏈的話我們希望相鄰的元素不能同時(shí)入選，那么我們至少需要放棄n/2個(gè)點(diǎn)（其中n是鏈中點(diǎn)的個(gè)數(shù)）

所有只要找出鏈計(jì)算一下就好了。

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<map>#define N 100003#define LL long long using namespace std;map<int,int> mp;int n,p,a[N],b[N],nxt[N],vis[N],cnt,ans;int cmp(int x,int y){	return a[x]<a[y];}void dfs(int x){	//cout<<x<<" ";	++cnt;	vis[x]=1;	if (!nxt[x]) return;	dfs(nxt[x]);}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&p);	for (int i=1;i<=n;i++) 	 scanf("%d",&a[i]),b[i]=i,mp[a[i]]=i;	sort(b+1,b+n+1,cmp);	for (int i=1;i<=n;i++) {		LL t=(LL)a[i]*p;		if (t>1000000000) continue;	    nxt[i]=mp[t];	}	for (int i=1;i<=n;i++)	 if (!vis[b[i]]) {	  cnt=0;	  dfs(b[i]);	  ans+=cnt/2;	//  cout<<endl;    }    PRintf("%d/n",n-ans);}