笔试时间：2024年10月12日 秋招

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

第一题

题目：均衡

小明在研究一个有趣的数组翻转操作问题，其中为了考虑均衡，他会同时翻转相邻两个数。他有一个长度为N的数组a[]，并可以进行任意次操作:选择相邻的两个数，翻转这两个数的符号，即将a[i]和a[i+1] (0<= i< n-1)的符号都翻转。符号翻转的意思是正数变负数，负数变正数，在程序中即让num = -num，也即数学中的取相反数;当然0翻转后还是0。小明的任务是找到经过任意次数(可以为0次)这些操作后，能够获得的最大数组和。当然，只要小明觉得有必要，同一个数也可以被反复选择。

输入描述

第一行包含一个整数N，表示数组的长度；

第二行包含N个整数，a[1], a[2] ,..., a[N]。

输出描述

输出一个整数，表示经过任意次操作后数组的最大和。

样例输入

5

1 -2 3 -4 5

样例输出

15

参考题解

数据规模较小，直接排序+模拟。按绝对值大小降序排序，遇到负数就连带下一个元素一起改变符号，依次相加求和。（另一种方法是统计负号个数，如果是奇数就用元素绝对值之和减去绝对值最小的元素，如果是偶数就直接使用所有元素绝对值之和，这样可以避免排序。）

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

    // 按照元素的绝对值降序排序
    sort(a.begin(), a.end(), [](int x, int y) {
        return abs(x) > abs(y);
    });

    int res = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] >= 0) {
            res += a[i];
        } else {
            res -= a[i];
            a[i + 1] = -a[i + 1];
        }
    }
    res += a[n - 1];
    cout << res << endl;

    return 0;
}

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

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];

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

        // 按照元素的绝对值降序排序
        Arrays.sort(a, (x, y) -> Math.abs(y) - Math.abs(x));

        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            if (a[i] >= 0) {
                res += a[i];
            } else {
                res -= a[i];
                a[i + 1] = -a[i + 1];
            }
        }
        res += a[n - 1];
        System.out.println(res);
    }
}

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

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

# 按照元素的绝对值降序排序
a.sort(key=abs, reverse=True)

res = 0
for i in range(n - 1):
    if a[i] >= 0:
        res += a[i]
    else:
        res -= a[i]
        a[i + 1] = -a[i + 1]
res += a[n - 1]
print(res)

第二题

题目：宝石项链

小明正在欣赏他的一串宝石项链，这个项链还没有封口，是一条链，初始时从左到右宝石分别编号1,2,3,..., n。然而经过一段时间端详，小明觉得他应该把某颗宝石取下，然后放到某颗宝石的前面或者后面去。小明在正式进行调整前，想请你帮他模拟一下他的若干次调整，希望你能告诉他经过他若干次调整后宝石项链的样子。

输入描述

第一行2个空格隔开的整数n和q，表示宝石数量和操作次数。

第二行3q个空格隔开的整数a1,b1 op1,a2 b2,op2 , ... aq,bq opq ，对第i次操作，表示将编号为ai的宝石取下，放到编号为bi的宝石旁边，当opi=0时放到其前，否则放到其后。

输出描述

输出一行n个整数，表示调整后，从左到右宝石的编号。

样例输入

5 3

1 2 1 3 2 0 5 4 0

样例输出

3 2 1 5 4

参考题解

用两个数组分别记录每个编号的左边编号和右边编号，模拟双链表。调整宝石时更新这两个数组即可，最后找到头结点，根据记录右编号的数组依次向后遍历输出答案即可。

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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    vector<int> ops(3 * q);
    for (int i = 0; i < 3 * q; i++) {
        cin >> ops[i];
    }

    // 初始化每个元素的前后元素
    vector<int> pre(n + 1, -1);
    vector<int> nxt(n + 1, -1);

    for (int i = 1; i