米哈游后端笔试题解

第一题是算联通块，两次dfs即可，太简单，不细说了

第二题 算添加删除mhy的，也挺简单的，不说了

第三题：

给你一个n的数组a，数组中元素不重复，1<= 元素大小 <=1000000

n为 [1,100000]

求从数组中挑选多于一个元素的子集（至少两个元素），使得子集中元素两两为倍数关系

的方案数 （mod 1000000007）

解法：

把数组a递增排序

预处理这个数组间 的倍数关系 （nlog1000000）

再nlog 去dp一下

dp含义 ：sum[x]表示以x元素作为结尾的方案数

转移方程：（条件：a中存在u，且a[i]是u倍数，u！=a[i]）

sum[a[i]] += sum[u]+1;

代表u结尾的所有合法子集均添加一个a[i] 的方案数： sum[u]

以及单一个u的集合加 a[i] 也能构成新的合法集合的方案数： 1

故u对a[i]的贡献为 sum[u]+1

记得mod一下 ：sum[a[i]]=(sum[a[i]]+sum[u]+1)%mod;

最后，c++ 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int n;
int a[1000007];
vector<int>r[1000007];
ll sum[10000007];
bool vis[1000007];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        vis[a[i]]=1;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=1000000;i++){
        if(vis[i]==0)continue;
        for(int j=i+i;j<=1000000;j+=i){
            if(vis[j])r[j].push_back(i);
        }
    }
    for(int i=2;i<=n;i++){
        for(auto u:r[a[i]]){
            if(vis[u])sum[a[i]]=(sum[a[i]]+sum[u]+1)%mod;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans=(ans+sum[a[i]])%mod;
    }
    cout<<ans;
}