列表

详情

MMT6. k倍多重正整数集合

描述

k倍多重正整数集合的定义是：在一个多重集合（元素可以重复）中，不存在一个正整数是另一个正整数的k倍。

现在小M有n个正整数，你可以选择其中一些数构成k倍多重正整数集合。请求出最多能选出多少数来构成它。

输入描述

第一行有两个整数n, k(1 <= n <= 10^5, 1 <= k <= 10^9)。

接下来一行有n个正整数a1, a2, ..., an (1 <= ai <= 10^9)。

输出描述

最多能选出多少数构成k倍多重正整数集合。

示例1

输入: 

6 2
2 3 6 5 4 10

输出: 

3

说明:

第一个样例中，我们选择2，3，5即可满足要求，因为k == 2，不存在一个数是另一个数的两倍。

示例2

输入: 

2 2
2 2

输出: 

2

说明:

第二个样例中，我们选择2，2即可满足要求，因为k == 2，2也不是2的两倍，注意多重集合元素可以重复。

原站题解

C++ 解法, 执行用时: 37ms, 内存消耗: 10204KB, 提交时间: 2020-07-28 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <fstream>
#define INF 0x3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
const int maxm=1e5+5;
const ll mod=1e9+7;
const int inf=1e9;
const double eps=1e-9;
const double PI=acos(-1.0);
int a[maxn],vis[maxn],flag[maxn],cnt[maxn];
int dp[maxn][2];
map<int,int> mp;
vector<int> v[maxn];
   
inline int max(int x,int y){
    return x>y?x:y;
}
   
void dfs(int u){
    vis[u]=1;       //标记已经处理过的点;
    dp[u][1]=cnt[u];
    dp[u][0]=0;
   
    if(v[u].size()==0){
        return;
    }
    //dp[i][0]表示不选这个点能拿的最大值,dp[i][1]表示选这个点能拿的最大值;
    for(int i=0;i<v[u].size();i++){
        dfs(v[u][i]);
        dp[u][0]+=max(dp[v[u][i]][1],dp[v[u][i]][0]);
        dp[u][1]=max(dp[u][1]+dp[v[u][i]][0],dp[u][1]);
    }
}
   
int main(){
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(flag,0,sizeof(flag));
       
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
   
    int tot=1;          //去重后的点数;
    cnt[tot]=1;
    for(int i=2;i<=n;i++){      //去重;
        if(a[i]==a[tot]){
            cnt[tot]++;
        }else{
            a[++tot]=a[i];
            cnt[tot]++;
        }
    }
   
    if(k==1){
        cout<<tot<<endl;
        return 0;
    }
   
    for(int i=1;i<=tot;i++){
        mp[a[i]]=i;
        if(a[i]%k==0&&mp.count(a[i]/k)!=0){
            v[mp[a[i]/k]].push_back(i);
            flag[i]=1;       //标记在树上的点;
            flag[mp[a[i]/k]]=1;      //标记在树上的点;
        }
    }
   
    int ans=0;
    for(int i=1;i<=tot;i++){
        if(!flag[i]){       //单个点;
            ans+=cnt[i];
        }else if(!vis[i]){
            dfs(i);
            ans+=max(dp[i][0],dp[i][1]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

C++ 解法, 执行用时: 41ms, 内存消耗: 9516KB, 提交时间: 2020-11-01 

/*
    小学生一发努力备战Pony ai笔试篇;
 
*/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <fstream>
#define INF 0x3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
const int maxm=1e5+5;
const ll mod=1e9+7;
const int inf=1e9;
const double eps=1e-9;
const double PI=acos(-1.0);
int a[maxn],vis[maxn],flag[maxn],cnt[maxn];
int dp[maxn][2];
map<int,int> mp;
vector<int> v[maxn];
 
inline int max(int x,int y){
    return x>y?x:y;
}
 
void dfs(int u){
    vis[u]=1;       //标记已经处理过的点;
    dp[u][1]=cnt[u];
    dp[u][0]=0;
 
    if(v[u].size()==0){
        return;
    }
    //dp[i][0]表示不选这个点能拿的最大值,dp[i][1]表示选这个点能拿的最大值;
    for(int i=0;i<v[u].size();i++){
        dfs(v[u][i]);
        dp[u][0]+=max(dp[v[u][i]][1],dp[v[u][i]][0]);
        dp[u][1]=max(dp[u][1]+dp[v[u][i]][0],dp[u][1]);
    }
}
 
int main(){
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(flag,0,sizeof(flag));
     
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
 
    int tot=1;          //去重后的点数;
    cnt[tot]=1;
    for(int i=2;i<=n;i++){      //去重;
        if(a[i]==a[tot]){
            cnt[tot]++; 
        }else{
            a[++tot]=a[i];
            cnt[tot]++;
        }
    }
 
    if(k==1){
        cout<<tot<<endl;
        return 0;
    }
 
    for(int i=1;i<=tot;i++){
        mp[a[i]]=i;
        if(a[i]%k==0&&mp.count(a[i]/k)!=0){
            v[mp[a[i]/k]].push_back(i);
            flag[i]=1;       //标记在树上的点;
            flag[mp[a[i]/k]]=1;      //标记在树上的点;
        }
    }
 
    int ans=0;
    for(int i=1;i<=tot;i++){
        if(!flag[i]){       //单个点;
            ans+=cnt[i];
        }else if(!vis[i]){
            dfs(i);
            ans+=max(dp[i][0],dp[i][1]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

C++ 解法, 执行用时: 41ms, 内存消耗: 9560KB, 提交时间: 2020-10-31 

/*
    小学生一发努力备战Pony ai笔试篇;
 
*/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <fstream>
#define INF 0x3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
const int maxm=1e5+5;
const ll mod=1e9+7;
const int inf=1e9;
const double eps=1e-9;
const double PI=acos(-1.0);
int a[maxn],vis[maxn],flag[maxn],cnt[maxn];
int dp[maxn][2];
map<int,int> mp;
vector<int> v[maxn];
 
inline int max(int x,int y){
    return x>y?x:y;
}
 
void dfs(int u){
    vis[u]=1;       //标记已经处理过的点;
    dp[u][1]=cnt[u];
    dp[u][0]=0;
 
    if(v[u].size()==0){
        return;
    }
    //dp[i][0]表示不选这个点能拿的最大值,dp[i][1]表示选这个点能拿的最大值;
    for(int i=0;i<v[u].size();i++){
        dfs(v[u][i]);
        dp[u][0]+=max(dp[v[u][i]][1],dp[v[u][i]][0]);
        dp[u][1]=max(dp[u][1]+dp[v[u][i]][0],dp[u][1]);
    }
}
 
int main(){
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(flag,0,sizeof(flag));
     
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
 
    int tot=1;          //去重后的点数;
    cnt[tot]=1;
    for(int i=2;i<=n;i++){      //去重;
        if(a[i]==a[tot]){
            cnt[tot]++; 
        }else{
            a[++tot]=a[i];
            cnt[tot]++;
        }
    }
 
    if(k==1){
        cout<<tot<<endl;
        return 0;
    }
 
    for(int i=1;i<=tot;i++){
        mp[a[i]]=i;
        if(a[i]%k==0&&mp.count(a[i]/k)!=0){
            v[mp[a[i]/k]].push_back(i);
            flag[i]=1;       //标记在树上的点;
            flag[mp[a[i]/k]]=1;      //标记在树上的点;
        }
    }
 
    int ans=0;
    for(int i=1;i<=tot;i++){
        if(!flag[i]){       //单个点;
            ans+=cnt[i];
        }else if(!vis[i]){
            dfs(i);
            ans+=max(dp[i][0],dp[i][1]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

C++14 解法, 执行用时: 43ms, 内存消耗: 9572KB, 提交时间: 2020-04-27 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <fstream>
#define INF 0x3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
const int maxm=1e5+5;
const ll mod=1e9+7;
const int inf=1e9;
const double eps=1e-9;
const double PI=acos(-1.0);
int a[maxn],vis[maxn],flag[maxn],cnt[maxn];
int dp[maxn][2];
map<int,int> mp;
vector<int> v[maxn];
  
inline int max(int x,int y){
    return x>y?x:y;
}
  
void dfs(int u){
    vis[u]=1;       //标记已经处理过的点;
    dp[u][1]=cnt[u];
    dp[u][0]=0;
  
    if(v[u].size()==0){
        return;
    }
    //dp[i][0]表示不选这个点能拿的最大值,dp[i][1]表示选这个点能拿的最大值;
    for(int i=0;i<v[u].size();i++){
        dfs(v[u][i]);
        dp[u][0]+=max(dp[v[u][i]][1],dp[v[u][i]][0]);
        dp[u][1]=max(dp[u][1]+dp[v[u][i]][0],dp[u][1]);
    }
}
  
int main(){
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(flag,0,sizeof(flag));
      
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
  
    int tot=1;          //去重后的点数;
    cnt[tot]=1;
    for(int i=2;i<=n;i++){      //去重;
        if(a[i]==a[tot]){
            cnt[tot]++;
        }else{
            a[++tot]=a[i];
            cnt[tot]++;
        }
    }
  
    if(k==1){
        cout<<tot<<endl;
        return 0;
    }
  
    for(int i=1;i<=tot;i++){
        mp[a[i]]=i;
        if(a[i]%k==0&&mp.count(a[i]/k)!=0){
            v[mp[a[i]/k]].push_back(i);
            flag[i]=1;       //标记在树上的点;
            flag[mp[a[i]/k]]=1;      //标记在树上的点;
        }
    }
  
    int ans=0;
    for(int i=1;i<=tot;i++){
        if(!flag[i]){       //单个点;
            ans+=cnt[i];
        }else if(!vis[i]){
            dfs(i);
            ans+=max(dp[i][0],dp[i][1]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

C++ 解法, 执行用时: 43ms, 内存消耗: 9704KB, 提交时间: 2019-04-23 

/*
    小学生一发努力备战Pony ai笔试篇;
 
*/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <fstream>
#define INF 0x3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
const int maxm=1e5+5;
const ll mod=1e9+7;
const int inf=1e9;
const double eps=1e-9;
const double PI=acos(-1.0);
int a[maxn],vis[maxn],flag[maxn],cnt[maxn];
int dp[maxn][2];
map<int,int> mp;
vector<int> v[maxn];
 
inline int max(int x,int y){
    return x>y?x:y;
}
 
void dfs(int u){
    vis[u]=1;       //标记已经处理过的点;
    dp[u][1]=cnt[u];
    dp[u][0]=0;
 
    if(v[u].size()==0){
        return;
    }
    //dp[i][0]表示不选这个点能拿的最大值,dp[i][1]表示选这个点能拿的最大值;
    for(int i=0;i<v[u].size();i++){
        dfs(v[u][i]);
        dp[u][0]+=max(dp[v[u][i]][1],dp[v[u][i]][0]);
        dp[u][1]=max(dp[u][1]+dp[v[u][i]][0],dp[u][1]);
    }
}
 
int main(){
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(flag,0,sizeof(flag));
     
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
 
    int tot=1;          //去重后的点数;
    cnt[tot]=1;
    for(int i=2;i<=n;i++){      //去重;
        if(a[i]==a[tot]){
            cnt[tot]++; 
        }else{
            a[++tot]=a[i];
            cnt[tot]++;
        }
    }
 
    if(k==1){
        cout<<tot<<endl;
        return 0;
    }
 
    for(int i=1;i<=tot;i++){
        mp[a[i]]=i;
        if(a[i]%k==0&&mp.count(a[i]/k)!=0){
            v[mp[a[i]/k]].push_back(i);
            flag[i]=1;       //标记在树上的点;
            flag[mp[a[i]/k]]=1;      //标记在树上的点;
        }
    }
 
    int ans=0;
    for(int i=1;i<=tot;i++){
        if(!flag[i]){       //单个点;
            ans+=cnt[i];
        }else if(!vis[i]){
            dfs(i);
            ans+=max(dp[i][0],dp[i][1]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

上一题

© 2024 nowcoder.com