0%

[洛谷 P1978] 集合

题目

题目链接

题目大意:给出有 $n$ 个元素的集合 $A$,要求选出一个集合 $S \subseteq A$ 且满足 $\forall x \in S, kx \notin S$。求出 $|S|$ 的最大值。$1 \le n, k \le 10^5, 1 \le a_i \le 2^{63} - 1$。

思路

十分裸的一道题。不难发现题目中的约束关系实际上构成了一条链,且只能选中链上不相邻的两个点。

然后贪心就完了。

我怎么卡都会爆 uLL,无奈参考了下题解判爆上限的实现方法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;
typedef unsigned long long uLL;

std::map<uLL, bool> mp;
uLL a[100010];
uLL n, k, ans, max;

int main() {
read(n), read(k);
max = 9223372036854775807 / k;
for (int i = 1; i <= n; ++i) read(a[i]), mp[a[i]] = true;
std::sort(a + 1, a + n + 1);
for (std::map<uLL, bool>::iterator it = mp.begin(); it != mp.end(); ++it) {
if (it -> second == true) {
int x = 0, y = 0, j = 1;
uLL now = it -> first;
while (mp[now]) {
if (j % 2) ++x;
else ++y;
++j;
mp[now] = false;
if (now >= max) break;
now *= k;
}
ans += std::max(x, y);
}
}
printf("%llu\n", ans);
return 0;
}