【wikioi】1553 互斥的数(hash+set)

http://wikioi.com/problem/1553/

一开始我也知道用set来判a[i]/p是否在集合中,在的话就直接删掉。

但是我没有想到要排序,也没有想到当存在a,b使得a/p==b时到底删哪个。

所以我写出来后样例都过不了。

看题解。。

恩。。。先排序,然后依次扫过去,如果a[i]/p不是整数或者不在集合中,就将它加入到集合中,否则计数器-1(初始为n)

这样做的原因是。。当存在a和b使得a/p==b时,我们一定是删掉a(此时a>b),因为在后边几乎不会找到与b互斥的数(几乎是因为可能有重复),即找不到b*p了,但是有可能找到a*p,因为后边的数都比a大,设这个数为k,就有可能k/p==a

以此类推。。

集合我用set了。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getnum()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }
inline int getnum() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; }
set<int> s;
const int N=100005;
int n, a[N], p; int main() {
read(n); read(p);
int sum=n;
for1(i, 1, n) read(a[i]);
sort(a+1, a+1+n);
for1(i, 1, n) {
if(a[i]%p==0) {
if(s.count(a[i]/p)==0) s.insert(a[i]);
else --sum;
}
else s.insert(a[i]);
}
print(sum);
return 0;
}

题目描述 Description

有这样的一个集合,集合中的元素个数由给定的N决定,集合的元素为N个不同的正整数,一旦集合中的两个数x,y满足y = P*x,那么就认为x,y这两个数是互斥的,现在想知道给定的一个集合的最大子集满足两两之间不互斥。

输入描述 Input Description

输入有多组数据,每组第一行给定两个数N和P(1<=N<=10^5, 1<=P<=10^9)。接下来一行包含N个不同正整数ai(1<=ai<=10^9)。

输出描述 Output Description

输出一行表示最大的满足要求的子集的元素个数。

样例输入 Sample Input

4 2

1 2 3 4

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

上一篇:js闭包理解


下一篇:CentOS7 安装mysql 5.7