[洛谷 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，无奈参考了下题解判爆上限的实现方法。

代码

#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;
}