笔试时间：2023年9月23日 秋招

备注：第四题暂无题解

第一题

题目：小红的有序数组

小红有一个长度为n的数组，数组下标为0到n - 1，每次可以交换下标为i和(i + 2)%n的数，请问小红能否通过有限次交换使得数组变成一个单调不减的数组。

输入描述

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

接下来t组数据，每组数据第一行一个整数n，表示数组长度。

每组数据第二行n个整数ai;，表示数组的值。

1<= t <= 10

1 <= n <= 10^5

1 <= ai <= 10^9

输出描述

对于每组数据，如果能够通过有限次交换使得数组变成一个单调不减的数组，输出"YES”，否则输出"NO”。

样例输入

2

4

1 4 3 2

4

4 3 2 1

样例输出

YES

NO

提示

第一组数据，交换下标为1和3的数，变成[1,2,3,4]单调不减。

参考题解

交换的传递性，即a与b能够交换，b与c能够交换，那么a与c能够交换。对于n的奇偶分情况讨论。

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

import java.util.*;

public class Main {

    public static String isPossibleToSort(int n, int[] a) {
        if (n % 2 == 1) {
            return "YES";
        }

        List<Integer> b0 = new ArrayList<>();
        List<Integer> b1 = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                b0.add(a[i]);
            } else {
                b1.add(a[i]);
            }
        }

        Collections.sort(b0);
        Collections.sort(b1);

        for (int i = 0; i < n; ++i) {
            a[i] = (i % 2 == 0) ? b0.get(i / 2) : b1.get(i / 2);
        }

        for (int i = 1; i < n; ++i) {
            if (a[i] < a[i - 1]) {
                return "NO";
            }
        }

        return "YES";
    }

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

        while (T-- > 0) {
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = scanner.nextInt();
            }

            System.out.println(isPossibleToSort(n, arr));
        }
    }
}

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

def is_possible_to_sort(n, a):
    if n % 2 == 1:
        return "YES"

    b0 = sorted(a[::2])
    b1 = sorted(a[1::2])

    sorted_arr = [0] * n
    for i in range(n):
        sorted_arr[i] = b0[i // 2] if i % 2 == 0 else b1[i // 2]

    return "YES" if sorted_arr == sorted(a) else "NO"


T = int(input())
for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    print(is_possible_to_sort(n, arr))

第二题

题目：小红的相似字符串

小红认为两个字符串相似，需要这两个字符串的每个字母的个数都相等。如"abcbd"和"dbcba"相似，"abcd"和"abcd"相似，而"abb"和"aab"不相似，"ac"和"cca"不相似。现在小红有n个字符串，她想知道有多少对字符串是相似的