笔试时间：2025年9月2日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：Zeeman的异或数组

Zeeman有一个长度为n的数组{a}。他想构造一个长度为n的数组{b}，满足：对于全部的下标i,j，有a_i⊕b_i = a_j⊕b_j成立。其中，⊕表示按位异或运算。请你求出满足条件的字典序最小的数组{b}。

输入描述

第一行输入一个正整数n (1≤n≤10^5)。 第二行输入n个非负整数表示数组a (0≤a_i≤10^9)。

输出描述

输出满足条件的字典序最小的数组b。

样例输入

6

1 1 4 5 1 4

样例输出

0 0 5 4 0 5

参考题解

C++：

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    if (n == 0) {
        return 0;
    }
    
    int c = a[0];
    cout << (a[0] ^ c);
    
    for (int i = 1; i < n; i++) {
        cout << " " << (a[i] ^ c);
    }
    cout << endl;
    
    return 0;
}

Java：

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();
        }
        scanner.close();
        
        if (n == 0) {
            return;
        }
        
        int c = a[0];
        StringBuilder sb = new StringBuilder();
        sb.append(a[0] ^ c);
        
        for (int i = 1; i < n; i++) {
            sb.append(" ").append(a[i] ^ c);
        }
        
        System.out.println(sb.toString());
    }
}

Python：

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

if n == 0:
    exit()

c = a[0]
result = []
for i in range(n):
    result.append(a[i] ^ c)

print(result)

第二题：常大组合

给定一个长度为n的整数数组{a}。定义每个位置i的增益值b_i = a_i - i。请你统计所有满足i<j且b_i + b_j > 0的索引对(i,j)的数量。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T (1≤T≤10)代表数据组数。

保证单个测试文件的n之和不超过2×10^5。

每组测试数据：

第一行输入一个整数n (1≤n≤2×10^5)表示数组长度

第二行输入n个整数a_i (-10^9≤a_i≤10^9)表示数组元素

输出描述

对于每一组测试数据，新起一行。输出一个整数，表示满足条件的索引对数量。

样例输入

2

5

3 1 4 1 5

4

3 1 1 3

样例输出

4

2

参考题解

C++：

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

class BIT {
private:
    vector<int> tree;
    int n;
    
public:
    BIT(int size) : n(size), tree(size + 1, 0) {}
    
    void update(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) {
            tree[idx] += val;
        }
    }
    
    int query(int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }
};

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector<int> b(n);
        set<int> valueSet;
        
        for (int i = 0; i < n; i++) {
            int a_val;
            cin >> a_val;
            b[i] = a_val - (i + 1);
            valueSet.insert(b[i]);
        }
        
        vector<int> map(valueSet.begin(), valueSet.end());
        sort(map.begin(), map.end());
        int mapSize = map.size();
        BIT bit(mapSize);
        
        long long totalCount = 0;
        
        for (int j = 0; j < n; j++) {
            int target = -b[j];
            auto it = lower_bound(map.begin(), map.end(), target);
            int rankLE = it - map.begin();
            
            int countLE = 0;
            if (rankLE > 0) {
                countLE = bit.query(rankLE);
            }
            
            totalCount += (long long)j - countLE;
            
            auto it2 = lower_bound(map.begin(), map.end(), b[j]);
            int rankBJ = (it2 - map.begin()) + 1;
            bit.update(rankBJ, 1);
        }
        
        cout << totalCount << endl;
    }
    
    return 0;
}

Java：

import java.util.*;

public class Main {
    static int[] bit;
    static int mapSize;
    
    public static void update(int index, int val) {
        for (; index <= mapSize; index += index & -index) {
            bit[index] += val;
        }
    }
    
    public static int query(int index) {
        int sum = 0;
        for (; index > 0; index -= index &