笔试时间：2025年8月16日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

你有一个长度为n的序列A: a₁,a₂,…,aₙ，你需要进行如下操作至多一次: 选择一个区间[L,R] (1≤L≤R≤n)，将a_L,a_{L+1},…,a_R全部加1。即a_L,a_{L+1},…,a_R均变为a_L+1,a_{L+1}+1,…,a_R+1 设变化后的序列为B: b₁,b₂,…,bₙ，你需要最大化inv(A)-inv(B)，其中inv()函数表示该序列的逆序对数量，即满足i<j，a_i>a_j的二元组(i,j)个数。换句话说，你需要尽可能地减小序列A的逆序对数量。

输入描述

第一行一个正整数T，表示数据组数; 对于每一组数据，第一行一个正整数n;

第二行n个正整数a₁,a₂,…,aₙ，表示序列A。 1≤n≤10⁵; 1≤T≤5; 1≤a_i≤n。

输出描述

对于每一组数据，输出一个整数，表示最大的inv(A)-inv(B)。

样例输入

3

5

4 2 3 1 5

5

1 2 3 4 5

3

2 1 1

样例输出

2

0

2

说明： 第一组数据，选择区间[3,4]，变化后的序列为[4 2 4 2 5]，逆序对数量为3;变化前逆序对数量为5。 第二组数据，选择任意区间都不会减小逆序对数量。 第三组数据，选择区间[2,3]，变化后的序列为[2 2 2]，逆序对数量为0;变化前逆序对数量为2。

参考题解

我们只在一个连续区间把所有数都加 1。对位置 i 的值 v 来说，这个操作只影响两种配对： (1) 右边等于 v−1 的元素会让原本的逆序对消失（赚到的收益 = 右侧 v−1 的个数）； (2) 左边等于 v+1 的元素会新产生逆序对（损失 = 左侧 v+1 的个数）。 所以位置 i 的净收益 = 右侧(v−1)数量 − 左侧(v+1)数量。预处理每个取值的全局出现次数 totalCount[·]，边扫边维护左侧计数 seenPrefix[·]，就能在 O(1) 得到当前位置的增量，把这些增量累加得到把区间一直向右扩的总收益，遍历过程中取到的最大值就是答案。时间复杂度 O(n)，空间 O(n)。

C++：

#include <bits/stdc++.h>
using namespace std;

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

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) cin >> arr[i];

        vector<int> totalCount(n + 2, 0);
        for (int v : arr) ++totalCount[v];

        vector<int> seenPrefix(n + 3, 0);
        long long currentGain = 0;
        long long bestGain = 0;

        for (int i = 0; i < n; ++i) {
            bestGain = max(bestGain, currentGain);
            int v = arr[i];
            currentGain += (long long)totalCount[v - 1] - seenPrefix[v - 1] - seenPrefix[v + 1];
            ++seenPrefix[v];
        }
        bestGain = max(bestGain, currentGain);

        cout << bestGain << "\n";
    }
    return 0;
}

Java：

import java.io.*;
import java.util.*;

public class Main {
    // 快速读入
    private static final class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { this.in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32 && c != -1);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32 && c != -1) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();

        int T;
        try { T = fs.nextInt(); } catch (Exception e) { return; }
        for (int _t = 0; _t < T; _t++) {
            int n = fs.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = fs.nextInt();

            int[] totalCount = new int[n + 2];
            for (int v : arr) ++totalCount[v];

            int[] seenPrefix = new int[n + 3];
            long currentGain = 0L;
            long bestGain = 0L;

            for (int i = 0; i < n; i++) {
                if (currentGain > bestGain) bestGain = currentGain;
                int v = arr[i];
                currentGain += (long) totalCount[v - 1] - seenPrefix[v - 1] - seenPrefix[v + 1];
                ++seenPrefix[v];
            }
            if (currentGain > bestGain) bestGain = currentGain;

            out.append(bestGain).append('\n');
        }

        System.out.print(out.toString());
    }
}

Python：

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    try:
        T = next(it)
    except StopIteration:
        return

    out_lines = []
    for _ in range(T):
        n = next(it)
        arr = [next(it) for _ in range(n)]

        total = [0] * (n + 2)
        for v in arr:
            total[v] += 1

        seen = [0] * (n + 3)
        current = 0
        best = 0

        for v in arr:
            if current > best:
                best = current
            current += total[v - 1] - seen[v - 1] - seen[v + 1]
            seen[v] += 1

        if current > best:
            best = current

        out_lines.append(str(best))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

第二题

在一场跳水比赛中，共有n位裁判依次为选手打分（打分为非负整数）。根据比赛规则，需要从所有裁判的打分中，选取连续的m个打分来计算选手的