笔试时间：2024年09月07日 秋招

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

第一题

题目

小美有一个长度为n的数组，她每次操作会执行如下：选定一个ai，把这个数加上一个任意的x(x > 0)，花费的代价为ai + x。现在小美想要把整个数组变成全部奇数或者全部偶数的最小代价是多少？

输入描述

第一行输入一个整数n，代表数组的长度

第二行输入n个数

输出描述

输出最小花费

样例输入

3

1 2 3

样例输出

3

参考题解

对变成奇数和变成偶数的两种情况分别进行计算。

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

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int oddCost = 0, evenCost = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 1) {
            evenCost += a[i] + 1;
        }else {
            oddCost += a[i] + 1;
        }
    }

    cout << min(oddCost, evenCost) << "\n";
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            a.add(scanner.nextInt());
        }

        int oddCost = 0, evenCost = 0;
        for (int i = 0; i < n; i++) {
            if (a.get(i) % 2 == 1) {
                evenCost += a.get(i) + 1;
            } else {
                oddCost += a.get(i) + 1;
            }
        }

        System.out.println(Math.min(oddCost, evenCost));
    }
}

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

n = int(input())
a = list(map(int, input().split()))

odd_cost = 0
even_cost = 0

for i in range(n):
    if a[i] % 2 == 1:
        even_cost += a[i] + 1
    else:
        odd_cost += a[i] + 1

print(min(odd_cost, even_cost))

第二题

题目

对于给定的由n个节点构成，根结点为1的有根树中，我们定义节点u和v是相似的节点，当且仅当节点u的子节点数量与节点v的子节点数量相等。输出相似节点的对数。

输入描述

每个测试文件均包含多组测试数据；

第一行输入一个整数T(1 <= T <= 10^4)，代表数据的组数，每组测试数据描述如下：

第一行输入一个整数n，表示节点数量；

此后n - 1行，第i行输入两个整数ui和vi(1 <= ui, vi <= n)，表示树上第i条边连接ui和vi，保证数联通，没有重边。

除此之外，保证所有n之和不超过2 * (10 ^ 5)。

输出描述

对于每一个测试用例，输出相似节点的对数。

样例输入

1

7

1 2

1 3

3 5

3 7

2 4

2 6

样例输出

9

参考题解

根结点的子节点数量为根节点的度数，其他节点的子节点数量为度数 - 1。根据子节点数量分组，然后对每一组计算对数即可。

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

#include<vector>
#include<iostream>
#include<unordered_map>
using namespace std;
void solve() {
    int n;
    cin >> n;
    vector<int> deg(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        deg[u]++;
        deg[v]++;
    }

    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++) {
        if (i == 0) mp[deg[i]]++;
        else mp[deg[i] - 1]++;
    }

    int ans = 0;
    for (auto &[k, v] : mp) {
        ans += v * (v - 1) / 2;
    }

    cout << ans << "\n";
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

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

import java.util.*;

public class Main {
    public static void solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] deg = new int[n];
        for (int i = 0; i < n - 1; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            u--; 
            v--;
            deg[u]++;
            deg[v]++;
        }

        Map<Integer, Integer> mp = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                mp.put(deg[i], mp.getOrDefault(deg[i], 0) + 1);
            } else {
                mp.put(deg[i] - 1, mp.getOrDefault(deg[i] - 1, 0) + 1);
            }
        }

        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            int v = entry.getValue();
            ans += v * (v - 1) / 2;
        }

        System.out.println(ans);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            solve();
        }
    }
}

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

from collections import defaultdict

def solve():
    n = int(input())
    deg = [0] * n
    for _ in range(n - 1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        deg[u] += 1
        deg[v] += 1

    mp = defaultdict(int)
    for i in range(n):
        if i == 0:
            mp[deg[i]] += 1
        else:
            mp[deg[i] - 1] += 1

    ans = 0
    for v in mp.values():
        ans += v * (v - 1) // 2

    print(ans)

t = int(input())
for _ in range(t):
    solve()

第三题

题目

小美和小团在玩一个卡牌游戏，初始时桌面上有n种卡牌，每种卡牌有ai张，这些牌都是背面朝上的。玩家操作时会翻两张牌，如果这两张牌的类型相同，则获胜，否则，将两张