笔试时间：2025年10月15日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：按位与

C/C++中的按位与运算符"&"是双目运算符，其功能是参与运算的两数各对应的二进制位相与，只有对应的两个二进制位都为1时，结果位才为1。参与运算的两个数均以补码出现。现在，给你n个数字，请你从中挑选2个数字，使他们的按位与运算结果在所有可能的挑选方式中是最大的。

输入描述

第一行包含一个正整数n（2≤n≤300000），表示给定数字的数量。 接下来n行，每行包含1个整数a（0≤a≤10^9），表示一个给定的数字。

输出描述

输出仅一行，包含一个数字，表示题目所求的最大按位与的结果。

样例输入

3

8

10

2

样例输出

8

样例说明

8&10=8，8&2=0，10&2=2，所以最大的一个结果是8。

参考题解

解题思路： 从高位开始贪心，因为高位为1对结果的影响更大。每次只保留在当前位为1的数字，因为只有这些数字可能产生更大的按位与结果。时间复杂度：O(30×n)。

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];
    }
    
    int res = 0;
    for (int bit = 30; bit >= 0; bit--) {
        vector<int> candidates;
        for (int x : a) {
            if ((x >> bit) & 1) {
                candidates.push_back(x);
            }
        }
        if (candidates.size() >= 2) {
            res |= (1 << bit);
            a = candidates;
        }
    }
    
    cout << res << endl;
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
        
        int res = 0;
        for (int bit = 30; bit >= 0; bit--) {
            List<Integer> candidates = new ArrayList<>();
            for (int x : a) {
                if (((x >> bit) & 1) == 1) {
                    candidates.add(x);
                }
            }
            if (candidates.size() >= 2) {
                res |= (1 << bit);
                a = candidates;
            }
        }
        
        System.out.println(res);
    }
}

Python：

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    res = 0
    for bit in range(30, -1, -1):
        candidates = [x for x in a if (x >> bit) & 1]
        if len(candidates) >= 2:
            res |= (1 << bit)
            a = candidates
    print(res)

if __name__ == "__main__":
    main()

第二题：游戏

小明和小红在玩一款与领地占领有关的对抗游戏。这个游戏的地图是一维的，从左到右有n个领地，分别编号为1，2，…，n。游戏初始时有一些可以选择的出生地，每个出生地由区间[l,r]描述，包含一段连续的领地，即编号l到r的领地。小明和小红这次游戏分配到了对抗的阵营，所以他们希望自己选的出生地包含的领地和对方不重合。

游戏周期性的更新它的出生地可选项，小明和小红想请你帮帮他们查看当前游戏出生地中是否有两个出生地不包含重复的领地。游戏在一开始没有任何出生地可选项，但是共有m次更新，每次更新要么添加一个出生地，要么销毁掉一个已有的出生地，请你在每次更新后告诉小明和小红是否有两个出生地不包含重复领地。

输入描述

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

对每组数据有4行数据：

- 第一行两个整数n和m，表示领地总数和更新总数。

- 第二行m个整数op_i（op_i∈{0,1}），表示第i次更新的类型，如果op_i=0则是删除出生地，op_i=1则是新增出生地。

- 第三行m个整数l_i（1≤l_i≤n）

- 第四行m个整数r_i（1≤r_i≤n）

其中[l_i,r_i]是第i次更新新增或删除的出生地的领地范围。注意可能增加了出生地[1,2]、[1,2]（均是1到2的领地范围，2个相同范围的出生地），后续一次删除出生地[1,2]只会删除一个。保证每次删除时都存在那样的出生地。

1≤T≤5，1≤n≤10^9，1≤m≤10^5，1≤l_i≤r_i≤n

输出描述

对于每组数据，输出一行共m个答案，分别表示对应每次更新后的答案：如果存在那样的出生地输出YES，否则输出NO。

样例输入

1

10 4

1 1 1 0

1 2 3 3

2 3 4 4

样例输出

NO NO YES NO

样例说明

• 第一次更新后仅有一个出生地[1,2]，不存在不相交领地的两个出生地。
• 第二次更新后有出生地[1,2]，[2,3]，它们领地重合了。
• 第三次更新后有出生地[1,2]，[2,3]，[3,4]，小明和小红分别选择[1,2]，[3,4]即可满足出生地领地不重合。
• 第四次更新后有出生地[1,2]，[2,3]，它们领地重合了。

参考题解

解题思路： 如果存在两个不相交的区间[l1,r1]和[l2,r2]，那么必然满足：r1 < l2 或 r2 < l1。换句话说，所有区间的最小右端点 < 所有区间的最大左端点。维护所有区间的最小右端点和最大左端点，如果最小右端点小于最大左端点，则说明存在两个不相交的区间（一个在左边，一个在右边），否则所有区间都有重叠。

C++：

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> ops(m), lefts(m), rights(m);
        
        for (int i = 0; i < m; i++) cin >> ops[i];
        for (int i = 0; i < m; i++) cin >> lefts[i];
        for (int i = 0; i < m; i++) cin >> rights[i];
        
        priority_queue<int, vector<int>, greater<int>> min_r_heap;
        priority_queue<int> max_l_heap;