2022年4月16日网易笔试

第二题（想法）：构建数组，在[1, k]范围内选出n个不重复的数和为x（首先明确：对于数组[1, ......, n]整体右移为[2, ......, n + 1]时，后者的和比前者大n）

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
void wangyi_4_16_second(long long n, long long k, long long x){
    long long maximum = 0, minimum = 0;
    for(int i = 1; i <= n; ++i){
        minimum += i;
        if(maximum <= 1e9) maximum += (k - i + 1);
    }
    // n > k , x大于可能的最大值或小于可能的最小值时无解，例：[1, 2, 3, 4, 5, 6, 7], n = 3，k = 7，x = 3和x = 19时无解   
     if(n > k || x < minimum || maximum < x) {
        printf("-1\n");
        return ;
    }
        // 可以证明经上面的判断后一定有解
    int a = (x - minimum) / n;// a为x和最小可能值差几个n，差几个就整体向后移动几次，并可以证明最大的数不会移动出k
    int b = (x - minimum) % n;// b为余数，就是移动过后的数组还和x差多少，差多少我就用刚好比移动过后的数组中最大的数大一的这个数替换数组中的一个数
                                         // 显然被替换的数为n + a + 1 - b,可以证明 刚好比移动过后的数组中最大的数大一的这个数 也不会超出k的范围
    int res[100005], cnt = 0;
        // 将1-n这n个数每个数加a，并将n + a + 1 - b这个数替换成n + a + 1 即为最终答案
    for(int i = 1;i <= n; ++i)
        if(i + a != n + a + 1 - b) res[cnt++] = i + a;
    if(cnt != n) res[cnt++] = n + a + 1;
    for(int i = 0 ; i < cnt - 1; ++i) printf("%d ",res[i]);
    printf("%d\n", res[cnt - 1]);
}

int main()
{
    wangyi_4_16_second(4, 6, 15);
    return 0;
}

第三题（最小生成树）：一个连通无向图，edge为图中的m条边，a数组为n个节点的值，定义收益为：删除一条边将获得的收益为一条边相连的两个节点的值相乘所得结果中末尾0的个数（2 * 5 = 10，收益为1），求在使图连通的情况下能获得的最大收益（不断删边又要保证图连通的情况下获得的最大收益）

function getValue(a1, a2){
    let two = 0;
    let five = 0;
    while(a1 % 2 == 0){
        two += 1;
        a1 /= 2;
    }
    while(a1 % 5 == 0){
        five += 1;
        a1 /= 5;
    }
    while(a2 % 2 == 0){
        two += 1;
        a2 /= 2;
    }
    while(a2 % 5 == 0){
        five += 1;
        a2 /= 5;
    }
    return Math.min(two, five);// 2因子和 5因子 少的
}
function getFather(father, x){
    if(father[x] == x) return x;
    father[x] = getFather(father, father[x]);
    return father[x];
}
function wangyi_4_16_third(n, m, a, edge){
    let res = 0;
    let sum = 0;
    // 边按照收益从小到大排序
    edge.sort(function(e1, e2){
        return getValue(a[e1[0] - 1], a[e1[1] - 1]) - getValue(a[e2[0] - 1], a[e2[1] - 1]);
    });
    // 初始化父亲数组
    let father = [0];
    for(let i = 1; i <= n; i += 1) father.push(i);
    // 合并
    for(let i = 0; i < m; i += 1){
        let value = getValue(a[edge[i][0] - 1], a[edge[i][1] - 1]);
        // sum 计算删除所有边的收益
        sum += value;
        // 分别计算当前边的两个节点是否连同 
        let f1 = getFather(father, edge[i][0]);  
        let f2 = getFather(father, edge[i][1]);
        // 如果不连通，则连通他们，res为连通此图的最小收益
        if(f1 != f2){
            father[f1] = f2;
            res += value;
        } 
    }
    return sum - res;// 所有边的收益-连通此图的最小收益 即为删掉边的最大收益
}