笔试时间：2024年08月03日

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

第一题

题目：数组价值

米小游有一个长度为 n 的数组，其中第 i 个元素为 ai。现在定义数组的价值是最大的相邻数字的乘积。例如数组为 [3,5,1,2] ，相邻元素的乘积分别是 35=15,51=5和1*2=2 ，则数组的价值是这些数字中的最大值，即 15。现在米小游想要任选数组中的某两个相邻的元素进行交换（你必须使用这次交换机会），他想知道最大可以将数组的价值更改为多少？

输入描述

第一行输入一个整数 n(2<=n<=10^5) 表示数组的长度。

第二行输入 n 个整数 a1,a2,.....,an (1<=ai<=10^5) 表示数组中的值。

输出描述

在一行上输出一个整数表示答案。

样例输入一

3

3 1 10

样例输出一

30

说明

交换 3 和 1 ，则数组变为 [1,3,10] ，此时最大价值为 3*10=30 。交换 1 和 10 也可以达到相同的最大价值。

样例输入二

4

1 2 10 8

样例输出二

80

说明

如果交换 2 和 10 ，则数组的价值会减少。但是由于必须使用交换机会，所以可以交换 1 和 2 ，这样数组的价值仍为 80。

参考题解

模拟。

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

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<ll> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    ll res = 0;
    for (int i = 0; i < n - 1; ++i) {
        res = max(res, A[i] * A[i + 1]);
    }

    for (int i = 0; i < n - 1; ++i) {
        ll left = (i > 0) ? A[i - 1] * A[i + 1] : 0;
        ll right = (i < n - 2) ? A[i + 1] * A[i + 2] : 0;
        res = max(res, max(left, right));
    }

    cout << res << endl;
    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] A = new long[n];
        for (int i = 0; i < n; ++i) {
            A[i] = sc.nextLong();
        }

        long res = -1;
        for (int i = 0; i < n - 1; ++i) {
            res = Math.max(res, A[i] * A[i + 1]);
        }

        for (int i = 0; i < n - 1; ++i) {
            long left = (i > 0) ? A[i - 1] * A[i + 1] : 0;
            long right = (i < n - 2) ? A[i + 1] * A[i + 2] : 0;
            res = Math.max(res, Math.max(left, right));
        }

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

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

n = int(input())
A = [int(c) for c in input().split()]

res = max(A[i] * A[i + 1] for i in range(n - 1))

for i in range(n - 1):
    # 计算交换 A[i] 和 A[i + 1] 后的最大相邻乘积
    # 只需要考虑交换位置及其相邻位置的乘积
    left = A[i - 1] * A[i + 1] if i > 0 else 0
    right = A[i + 1] * A[i + 2] if i < n - 2 else 0

    # 更新全局最大值
    res = max(res, max(left, right))

print(res)

第二题

题目：米小游买商品

商店里有 n个商品，分别编号为 1~n ，每个商品都有一个价值 vali和体积 wi，米小游有一个有一个 m 容量的背包，他能够装得下任意多个体积之和不超过 m 的商品。

米小游认为有些东西一起购买会带来灾难，比如可莉的角色立牌和蹦蹦炸弹的小手办，所以他设定了 k组互斥关系，每组关系给定两个数字 a,b，表示编号为 a 的商品和编号为 b的商品不能同时购买。

米小游希望装下的物品的价值之和最大，请你帮帮他求出最大价值。

输入描述

第一行输入三个整数 n,m,k(1<=n<=15;1<=m<=10^9;0<=k<=15)表示商品数量、背包容量和互斥关系数量。

接下来 n行，每行输入两个整数 wi,vali(1<=wi,vali<=10^9) 表示每个物品的体积和价值。

接下来 k行，每行输入两个整数 a,b(1<=a,b<=n,a≠b)，描述一组互斥关系。

输出描述

在一行上输出一个整数表示答案。

样例输入一

3 100 2

15 19

20 30

15 19

1 2

2 3

样例输出一

38

说明：

根据两组互斥关系，买了 2 就不能买 1 和 3，所以我们可以购买物品 1 和物品 3，这样达到最大价值 。

样例输入二

3 20 2

15 19

20 30

15 19

1 2

2 3

样例输出二

30

说明：

背包容量只有20，只能装下一个物品，选择第二个物品，价值30。

参考题解

暴力枚举+哈希表。

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

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <unordered_set>
using namespace std;

int n, m, k;
vector<pair<int, int>> stocks; // (weight, value)
vector<unordered_set<int>> mutexes;
int res = 0;

bool check(int i, const unordered_set<int>& vst) {
    for (int v : vst) {
        if (mutexes[v].count(i)) {
            return false;
        }
    }
    return true;
}

void backtrace(int i, int cur_value, int cur_weight, unordered_set<int> vst) {
    if (i >= n) {
        res = max(res, cur_value);
        return;
    }
    // Not take the current stock
    backtrace(i + 1, cur_value, cur_weight, vst);

    // Take the current stock if possible
    if (check(i, vst) && cur_weight + stocks[i].first <= m) {
        vst.insert(i);
        backtrace(i + 1, cur_value + stocks[i].second, cur_weight + stocks[i].first, vst);
        vst.erase(i);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    stocks.resize(n);
    mutexes.resize(n);

    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        stocks[i] = {a, b};
    }

    for (int i = 0; i < k; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        mutexes[a].insert(b);
        mutexes[b].insert(a);
    }

    unordered_set<int> vst;
    backtrace(0, 0, 0, vst);

    cout << res << endl;
    return 0;
}

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

import java.util.*;

public class Main {
    private static int n, m, k;
    private static int[][] stocks; // {weight, value}
    private static Set<Integer>[] mutexes;
    private static int res = 0;

    private static boolean check(int i, Set<Integer> vst) {
        for (int v : vst) {
            if (mutexes[v].contains(i)) {
                return