笔试时间：2025年9月13日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

给定一个正整数n，请你构造一个长度为n的排列{a₁, a₂, ..., aₙ}，满足对任意位置i（从1开始），i ⊕ aᵢ为奇数。

输入描述

输出描述

样例输入

2

1

2

样例输出

-1

2 1

样例说明：

• 对于n=1，无论a₁取1，均有1⊕1=0为偶数，因此无解，输出-1
• 对于n=2，取排列{2, 1}：1⊕2=3、2⊕1=3，均为奇数，合法

参考题解

解题思路：

1. 异或运算结果为奇数当且仅当两个数的奇偶性不同
2. 位置i与aᵢ的奇偶性必须相反：奇数位置放偶数，偶数位置放奇数
3. 当n为奇数时，奇数位置比偶数位置多1个，但1到n中奇数和偶数个数相等（奇数时），无解
4. 当n为偶数时，可以构造：对于位置2k-1和2k，分别放置2k和2k-1

C++：

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n % 2 == 1) {
            cout << "-1" << endl;
        } else {
            for (int i = 1; i <= n; i += 2) {
                cout << i + 1 << " " << i;
                if (i + 2 <= n) cout << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            if (n % 2 == 1) {
                System.out.println("-1");
            } else {
                StringBuilder sb = new StringBuilder();
                for (int i = 1; i <= n; i += 2) {
                    sb.append(i + 1).append(" ").append(i);
                    if (i + 2 <= n) sb.append(" ");
                }
                System.out.println(sb.toString());
            }
        }
    }
}

Python：

import sys

input_data = sys.stdin.read().strip().split()
t = int(input_data[0])
idx = 1
out_lines = []

for _ in range(t):
    n = int(input_data[idx])
    idx += 1
    if n % 2 == 1:
        out_lines.append("-1")
    else:
        perm = []
        for i in range(1, n+1, 2):
            perm.append(str(i+1))
            perm.append(str(i))
        out_lines.append(" ".join(perm))

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

第二题

给定长度为n的数组a和数组b，可以分别对两数组进行任意重排。设重排后的数组分别为a'和b'，记dᵢ = a'ᵢ - b'ᵢ。要求对所有1 < i < n，均满足dᵢ₋₁ ≥ dᵢ ≤ dᵢ₊₁或dᵢ₋₁ ≤ dᵢ ≥ dᵢ₊₁。

输入描述

输出描述

样例输入

2

5

1 2 3 4 5

1 1 1 1 1

4

5 2 8 1

3 4 1 2

样例输出

3 1 5 2 4

1 1 1 1 1

5 1 8 2

3 4 1 2

参考题解

解题思路：

1. 先将两个数组分别排序
2. 使用贪心策略交替配对极值： 偶数位置：a的最大值配b的最小值（产生较大差值）奇数位置：a的最小值配b的最大值（产生较小差值）
3. 这样构造能保证差值序列呈现波浪形交替变化

C++：

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    vector<int> a_prime(n), b_prime(n);
    int la = 0, ra = n - 1, lb = 0, rb = n - 1;
    
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            a_prime[i] = a[ra--];
            b_prime[i] = b[lb++];
        } else {
            a_prime[i] = a[la++];
            b_prime[i] = b[rb--];
        }
    }
    
    for (int i = 0; i < n; i++) {
        cout << a_prime[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
    
    for (int i = 0; i < n; i++) {
        cout << b_prime[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        for (int i = 0; i < n; i++) b[i] = sc.nextInt();
        
        Arrays.sort(a);
        Arrays.sort(b);
        
        int[] aPrime = new int[n];
        int[] bPrime = new int[n];
        int la = 0, ra = n - 1, lb = 0, rb = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                aPrime[i] = a[ra--];
                bPrime[i] = b[lb++];
            } else {
                aPrime[i] = a[la++];
                bPrime[i] = b[rb--];
            }
        }
        
        for (int i = 0; i < n; i++) {
            System.out.print(aPrime[i]);
            if (i < n - 1) System.out.print(" ");
        }
        System.out.println();
        
        for (int i = 0; i < n; i++) {
            System.out.print(bPrime[i]);
            if (i < n - 1) System.out.print(" ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) solve(sc);
    }
}

Python：

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    a.sort()
    b = list(map(int, sys.stdin.readline().split()))
    b.sort()
    
    a_prime = [0] * n
    b_prime = [0