2020北京ICPC网络选拔赛Round1-A

2020北京ICPC网络选拔赛Round1-A

十月 25, 2020

Intelligent Warehouse

  • 题意

给出一个长度为n<1e5的数组a

其中ai<1e7

求一个它的最大子集

使得其中的任意两数互为倍数因子关系

1
2
3
4
5
6
7
//input
6
1 4 2 8 5 7
//output
4

//hint:One possible choice is {1, 4, 2, 8}.

  • 题解

设dp[i]表示当前选的所有数都是i的因子的最优解(最大值)

此题能开int 1e7大小的数组

最直观的转移就是用dp[i]更新所有i的倍数的dp值 即

1
2
3
4
5
6
7
8
for(int i=1;i<=Max;i++){
    dp[i]+=cnt[i];
    if(!cnt[i])continue;
    for(int j=2*i;j<=Max;j+=i)dp[j]=max(dp[j],dp[i]);
    ///取max表示数j有多个因子但不能取它的所有因子
    ///例如10有因子5和2但5和2不能放在一个集合中
    ans=max(ans,dp[i]);
}

这样极限复杂度超过1e8

实际上就只用枚举i的素数倍就可以 因为合数可以倍若干个素数乘积凑出来

没必要再枚举

比如 i=30

我只用枚举它的素数倍即更新

dp[30×2]=max(dp[30×2],dp[30])…..dp[30×5]=max(dp[30×5],dp[30])

那为什么不用更新dp[30×6]？

因为在枚举它的素数倍时已经更新了dp[30×2]和dp[30×3]

dp[30×6] 会在之后dp[60×3]和dp[90×2]被更新到

复杂度和埃氏筛相同(?个人记得这个是nlogn的复杂度) 为O(XloglogX) 其中X=1e7

1e7内的素数可以通过欧拉筛或埃氏筛处理

1
2
3
4
5
6
for(int i=2;i<=Max;i++){
    if(isprime[i]){
        for(int j=2*i;j<=Max;j++)isprime[i]=0;
    }
}
///埃氏筛

不加埃氏筛直接处理它的所有倍数 可以卡进1s但是理论复杂度超过1e8

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
#include <bits/stdc++.h>
#include <time.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=1e7+5;
const int Mod=998244353;
const int inf=0x3f3f3f3f;
/*
*/
int dp[Max],cnt[Max];
int main() {
    Turnoff;
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int temp;cin>>temp;
        cnt[temp]++;
    }
    int ans=0;
    ///枚举所有倍数转移极限复杂度较高
    for(int i=1;i<=Max;i++){
        dp[i]+=cnt[i];
        if(!cnt[i])continue;
        for(int j=2*i;j<=Max;j+=i)dp[j]=max(dp[j],dp[i]);
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;

}