笔试时间：2024年08月25日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

多多有一颗 n 个节点的树，树中每一条边都有一个权值。多多还有一个长度为 n 的正整数序列：v1,v2,v3.....vn。删除树中若干条边之后（或者不删），就会变成一个有 x 个连通块的图，此时的得分为：剩余边权和 +vi （（两个可以互相到达的节点属于同一个连通块，注意一个孤点也是一个连通块）。多多可以删除图中若干条边（可以不删）。现在多多想知道，最多能够得到多少分。现在请你告诉多多答案。

输入描述

第一行一个正整数 T

接下来有 T 组数据每组数据第一行一个整数 n

第二行 n 个整数：v1,v2,v3.....vn

接下来 n-1 行，每行3个数:a,b,w。表示节点 a 与节点 b 之间有一条权值为 w 的边。

输出描述

对于每组数据输出一行一个数，表示最多的能够得到多少分。

样例输入

1

3

1 3 4

1 2 1

2 3 2

样例输出

5

参考题解

因为是树，每次删边都会多一个联通块，所以相同数量的联通块，一定是从最小的边开始删更优。比较联通块数量为1～n时的答案，求最大值。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005],v[100005];
int main() {
    int T;
    cin>>T;
    while (T--)
    {
        int n;
        cin>>n;
        int s=0;
        for (int i=0; i<n; i++) cin>>v[i];
        for (int i=1; i<n; i++)
        {
            int x,y;
            cin>>x>>y>>a[i];
            s+=a[i];
        }
        int res=0;
        sort(a+1,a+n);
        for (int i=0; i<n; i++) 
        {
            s-=a[i];
            res=max(res,s+v[i]);
        }
        cout<<res<<endl;
    }
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int[] v = new int[n];
            int[] a = new int[n];
            int s = 0;

            for (int i = 0; i < n; i++) {
                v[i] = sc.nextInt();
            }

            for (int i = 1; i < n; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                a[i] = sc.nextInt();
                s += a[i];
            }

            int res = 0;
            Arrays.sort(a, 1, n);

            for (int i = 0; i < n; i++) {
                s -= a[i];
                res = Math.max(res, s + v[i]);
            }

            System.out.println(res);
        }
        sc.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def main():
    T = int(input())
    while T > 0:
        T -= 1
        n = int(input())
        v = list(map(int, input().split()))
        a = [0] * n
        s = 0

        for i in range(1, n):
            x, y, a[i] = map(int, input().split())
            s += a[i]

        res = 0
        a = sorted(a[1:n])

        for i in range(n):
            s -= a[i]
            res = max(res, s + v[i])

        print(res)

if __name__ == "__main__":
    main()

第二题

题目

多多有一列正整数组成的数列，支持两种操作：选取一个偶数，使其值减半选取两个数字，移除并替换为两个数字的和多多希望最终能够得到一个全为奇数的数列，请计算最少需要操作几次。

输入描述

第一行一个数字T,代表测试用例组数

对于每个测试用例：第一行为n，代表数组长度

第二行n个正整数：a1,a2,...an

输出描述

对于每个测试用例，输出一个数字，代表最少需要操作次数。

样例输入

2

3

2 4 4

5

1 2 5 4 6

样例输出

3

2

参考题解

如果有奇数，让所有偶数依次和他相加就可以变成奇数了。没有奇数的话就先找一个除2最快变成奇数的偶数，变成奇数。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005],v[100005];
int main() {
    int T;
    cin>>T;
    while (T--)
    {
        int n;
        cin>>n;
        int s=0;
        for (int i=0; i<n; i++) cin>>v[i];
        for (int i=1; i<n; i++)
        {
            int x,y;
            cin>>x>>y>>a[i];
            s+=a[i];
        }
        int res=0;
        sort(a+1,a+n);
        for (int i=0; i<n; i++) 
        {
            s-=a[i];
            res=max(res,s+v[i]);
        }
        cout<<res<<endl;
    }
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 读取测试用例的数量

        while (T-- > 0) {
            int n = sc.nextInt(); // 读取n
            int[] v = new int[n]; // 创建数组v
            int[] a = new int[n]; // 创建数组a
            int s = 0; // 初始化s为0

            // 读取数组v的值
            for (int i = 0; i < n; i++) {
                v[i] = sc.nextInt();
            }

            // 读取数组a的值并计算s的和
            for (int i = 1; i < n; i++) {
                int x = sc.nextInt()