4月2号网易互娱笔试2,3,4题题解

第三题意：有n个人坐电梯，电梯能承受最重w，给定n个人的重量，求怎么排列让电梯使用最多次。
样例：
输入：
6 11
1 2 4 7 9 10
输出：
5
当顺序为2 10 4 9 7 1时，需要使用5次电梯
解法：
贪心每次枚举大于w的一对(l, r)排在前面，必定要分成两次坐电梯

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main(){
    int n, w;
    scanf("%d%d", &n, &w);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    int l = 0, r = n - 1, ans = 0;
    while(l < r){
        if(a[l] + a[r] > w){
            ans += 2;
            l++; r--;
        }
        else{
            l++;
        }
    }
    ans += (n - ans) / 2 + (n - ans) % 2;
    printf("%d\n", ans);
}

第四题题意：有n个金蛋，每砸破一个可获得 a[left] * a[i] * a[right] 的金钱，默认a[0]和a[n + 1] 等于1.
样例：
输入：
3 1 5 8
输出：
167
3 1 5 8 --> 3 5 8 --> 3 8 --> 8
+15 +120 +24 +8 =167
dp[l][r]代表砸完区间(l,r)内所有蛋蛋只剩下两个边界l和r时获得的最大金钱，在输入的数据前面前后加入一个1记忆化搜索即可

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int dp[N][N];
int a[N];
int dfs(int l, int r){
    if(dp[l][r] != -1)return dp[l][r];
    if(r - l == 1){
        return dp[l][r] = 0;
    }
    int ans = 0;
    for(int i = l + 1; i < r; i++){
        ans = max(ans, dfs(l, i) + dfs(i, r) + a[l] * a[i] * a[r]);
    }
    return dp[l][r] = ans;
}
char s[N * 4];
int main(){
    int n = 0, res = 0;
    a[0] = 1;
    gets(s);
    int len = strlen(s);
    for(int i = 0; i < len; i++){
        if(s[i] >= '0' && s[i] <= '9'){
            res = res * 10 + s[i] - '0';
        }
        else{
            a[++n] = res;
            res = 0;
        }
    }
    a[++n] = res;
    a[++n] = 1;
    memset(dp, -1, sizeof(dp));
    printf("%d\n", dfs(0, n));
}

第二题意：给定n个数，求三元组$(a_i,a_j,a_k)$最大公约数等于1的个数。
其中n<=99999,0 <= a[i]<=99999
样例：
输入：
8
1 2 3 4 5 6 7 8
输出：
52
如果不知道莫比乌斯反演，第二题难度感觉比前面两题加起来还要大。。。
其实莫比乌斯反演到底怎么回事，别问我，百度去。。。
最终NlogN求解

#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
bool vis[N];
int mu[N], prime[N];
//求解莫比乌斯函数
void Moblus()
{
    memset(vis, false, sizeof(vis));
    mu[1] = 1;
    int tot = 0;
    for(int i = 2; i <= N; i++){
        if(!vis[i]){
            prime[tot++] = i;
            mu[i] = -1;
        }
        for(int j = 0;j < tot; j++){
            if(i * prime[j] > N)break;
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0){
                mu[i * prime[j]] = 0;
                break;
            }
            else{
                mu[i * prime[j]] = -mu[i];
            }
        }
    }
}
long long num[N], cnt[N];
int a[N];
int gcd(int x, int y){
    return x % y == 0 ? y : gcd(y, x % y);
}
//暴力检查一下结果
int check(int n){
    int res = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            for(int k = j + 1; k < n; k++){
                if(gcd(a[i],gcd(a[j], a[k])) == 1)res++;
            }
        }
    }
    return res;
}
int main(){
    int n, x;
    Moblus();
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        a[i] = x;
        num[x]++;
    }
    for(int i = 1; i < N; i++){
        for(int j = i; j < N; j += i){
            cnt[i] += num[j];
        }
    }
    long long ans = 0;
    for(int i = 1; i < N; i++){
        if(cnt[i] < 3)continue;
        ans += mu[i] * cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
    }
    printf("%lld\n", ans);
    printf("%d\n", check(n));
}

黑色三月太恐怖了，腾讯简历提前批一直被锁定却从未发起面试，头条简历投了杳无音信。。。
三月只有阿里和虎牙的面试机会。。。
今天早上面完虎牙hr面，昨天刚面完阿里交叉面，写个报告攒一下RP，希望offer碗里来。