笔试时间：2025年04月19日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：折返

小美有一个长度为 n 的数组 a，数组中所有元素的值互不相同，且数组的下标从 1 开始。她计划对这个数组中的每个元素进行“数数”，她会从数组中数值最小的元素的索引开始。每次数数时，她会选择第一个值大于当前位置元素值的元素，直到所有元素都被数过为止。例如，假设数组 a = [3, 1, 5]，小美一开始选择的是索引 i = 2（此时 a_2 = 1 ），她会接着找到第一个比 1 大的元素 3 （索引 i = 1），然后再找到第一个比 3 大的元素 5 （索引 i = 3）。整个数数过程为：a_2 -> a_1 > a_3。在这一过程中，如果小美的操作是从较小索引移动到较大索引（即 j > i），我们称之为正向传送；如果是从较大索引移动到较小索引（即 j < i），则称之为逆向传送。你的任务是帮助小美计算她在整个数数过程中需要进行多少次正向传送和多少次逆向传送。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数 T(1\leq T\leq 1000),代表数据组数,每组测试数据描述如下： 对于每一组测试数据:第一行一个整数 n(1\leq n\leq 2\times 10^5)，表示数组长度。第二行 n 个整数，第 i 个数为 a_i(1\leq a_i\leq 10^9)，表示数组元素。单个测试文件 \sum n\leq 2\times 10^5。

输出描述

共 T 行，每行两个整数，分别表示正向传送和逆向传送的次数，以空格隔开。

样例输入

2

3

1 2 3

3

3 2 1

样例输出

2 0

0 2

参考题解

将 原数字和原数字对应的下标 组成一个新的元素，按照数值进行排序。接着从头到尾遍历即可，遍历过程中，判断是在前还是在后，更新正向和逆向的次数即可。

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

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

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

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

        // 创建带索引的元组 (值, 原始位置)
        vector<pair<int,int>> ele;
        ele.reserve(n);
        for (int i = 0; i < n; i++) {
            ele.emplace_back(a[i], i + 1);
        }

        // 按值升序排序
        sort(ele.begin(), ele.end(),
             [](const pair<int,int>& x, const pair<int,int>& y) {
                 return x.first < y.first;
             });

        int frw = 0, rve = 0;
        // 遍历相邻对，比较原始索引
        for (int i = 1; i < n; i++) {
            if (ele[i].second > ele[i-1].second)
                frw++;
            else
                rve++;
        }

        cout << frw << " " << rve << "\n";
    }

    return 0;
}

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

// Java 版本
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int T = Integer.parseInt(in.readLine().trim());
        while (T-- > 0) {
            int n = Integer.parseInt(in.readLine().trim());
            StringTokenizer st = new StringTokenizer(in.readLine());
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            // 创建带索引的列表 (值, 原始位置)
            List<int[]> ele = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                ele.add(new int[]{a[i], i + 1});
            }

            // 按值升序排序
            ele.sort(Comparator.comparingInt(o -> o[0]));

            int frw = 0, rve = 0;
            // 遍历相邻对，比较原始索引
            for (int i = 1; i < n; i++) {
                if (ele.get(i)[1] > ele.get(i - 1)[1]) {
                    frw++;
                } else {
                    rve++;
                }
            }

            out.println(frw + " " + rve);
        }

        out.flush();
    }
}

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

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    # 创建带索引的元组列表（元素值，原始索引）
    ele = [(val, i + 1) for i, val in enumerate(a)]  
    # 按元素值升序排序
    sorted_ele = sorted(ele, key=lambda x: x[0])  # [6,8](@ref)
    frw = 0
    rve = 0
    # 遍历排序后的元素对
    for i in range(1, n):
        prev_idx = sorted_ele[i - 1][1]
        curr_idx = sorted_ele[i][1]
        if curr_idx > prev_idx:
            frw += 1
        else:
            rve += 1
    print(frw, rve)

第二题

题目：字符交换

小美现在有一个字符串 s，她现在进行恰好一次操作-交换两个索引的字母，即选定 x,y (x != y)，交换 s_x 和 s_y。她想知道能不能使得 s 满足 s_0 <= s_1<= s_2<= .... <= s_{n-1}。你能帮帮她吗？

输入描述

第一行一个整数 t，表示有 t 组数据。

每组数据第一行一个整数 n，表示字符串的长度。

每组数据第二行一个字符串 s。

1< t<10001< n<100000s 仅包含小写字母且单个测试文件满足 Σ n < 10^5。

输出描述

对于每组数据，如果可以使得 s 满足 s_0<s_1< s_2< ..... < s_{n-1}，则输出 YES，否则输出 NO。

样例输入

2

3

acb

3

bca

样例输出

YES

NO

参考题解

题目要求恰好一次，也就是无论如何都要做一次。如果说原数组天生就满足递增，什么情况下可以满足上述条件呢？ 存在相同的字符即可。如果说原数组不满足递增，那么可以与排序后的数组进行比较，当不同的字符数量恰好为2的时候，即可满足条件。

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

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

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        string sorted_s = s;
        sort(sorted_s.begin(), sorted_s.end());

        int cnt = 0;
        bool same = false;
        for (int i = 0; i < n; i++) {
            if (s[i] != sorted_s[i]) {
                cnt++;
            }
            if (i > 0 && s[i] == s[i - 1]) {
                same = true;
            }
        }

        if (cnt == 2 || (cnt == 0 && same)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

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

// Java 版本
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int T = Integer.parseInt(in.readLine().trim());
        while (T-- > 0) {
            int n = Integer.parseInt(in.readLine().trim());
            String s = in.readLine().trim();

            char[] arr = s.toCharArray();
            char[] sortedArr = s.toCharArray();
            Arrays.sort(sortedArr);

            int cnt = 0;