题解 CF1475G 【Strange Beauty】

Cutest_Junior · 2021-02-07 09:40:58 · 题解

题解 CF1475G 【Strange Beauty】

题意

有 n 个数 a；
选取子集，要求子集内任意两个数 a_i,a_j 都有 a_i|a_j 或 a_j|a_i；
求最大子集的大小；

做法

最容易想到的做法是先把所有数排序，设 dp_i 表示以第 i 个数为最大数的最大集合大小，O(N^2)dp，显然超时。

然后 Virtual participation 时候我只想到上面的做法，果然我还是太菜了。

接下来想想怎么优化。

因为每个数的状态只可能由它的因数转移过来，而枚举因数的复杂度是 O(\sqrt{N}) 的，所以可以设 dp_i 为以 i 为最大数（注意和上一个做法的区别）的最大集合的大小，总复杂度 O(N\sqrt{N})，可过本题。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2e5 + 5;

int arr[N];
int dp[N];

void run() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }
    sort(arr + 1, arr + n + 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j * j <= arr[i]; ++j) {
            if (arr[i] % j == 0) {
                dp[arr[i]] = max(dp[arr[i]], max(dp[j], dp[arr[i] / j]));
            }
        }
        ++dp[arr[i]];
        ans = max(ans, dp[arr[i]]);
    }
    printf("%d\n", n - ans);
    memset(dp, 0, sizeof dp);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        run();
    }
}

再优化

然后发现时间 3462ms，跑得飞慢（~~当然也不排除我人傻常数大~~）。

可以想到每个数的倍数均摊 O(\log N)，而因数却是 O(\sqrt{N}) 级别的，所以我们可以对每个数往后转移，可以减少很多不必要的计算。

期望复杂度 O(N\log N)。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2e5 + 5;

int arr[N];

int dp[N];

void run() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }
    sort(arr + 1, arr + n + 1);
    memset(dp, 0, sizeof dp);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ++dp[arr[i]];
        ans = max(ans, dp[arr[i]]);
        for (int j = arr[i] + arr[i]; j < N; j += arr[i]) {
            dp[j] = max(dp[j], dp[arr[i]]);
        }
    }
    printf("%d\n", n - ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        run();
    }
}

Time limit exceeded on test 7

？？？

再再优化

复杂度不是更优了吗？怎么会 TLE？？？

我们看到之前的一句话：

期望复杂度 O(N\log N)。

只有当数据随机时才是 O(N\log N)。

那什么时候不能过呢？

考虑如果有 n 个 2，那复杂度是——

\Huge{O(N^2)}

把你人都整傻掉。

那这样要怎么优化呢？

我们发现其实是有了很多重复的计算，那可不可以把所有数丢进一个桶，设 dp_i 表示以第 i 个数为最大数的最大集合大小（然后发现优化着优化着又优化回去了）。

复杂度 O(N\log N)，421ms，跑得飞快。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2e5 + 5;

int arr[N];

int dp[N];

void run() {
    int n;
    scanf("%d", &n);
    memset(arr, 0, sizeof arr);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        ++arr[x];
    }
    memset(dp, 0, sizeof dp);
    int ans = 0;
    for (int i = 1; i <= N; ++i) {
        dp[i] += arr[i];
        ans = max(ans, dp[i]);
        for (int j = i + i; j < N; j += i) {
            dp[j] = max(dp[j], dp[i]);
        }
    }
    printf("%d\n", n - ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        run();
    }
}