笔试时间：2025年8月9日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：答题闯关

某答题闯关节目设置了m道题目（编号1到m），规则要求将这些题目分为两轮闯关赛，每轮至少包含1道题，所有题目必须分配到两轮中。 共有n名选手参加比赛，每位选手能答对的题目范围是连续的一段（用L~R描述，表示该选手能答对第L到第R号题）。 选手只要能答对某一轮的所有题目（即该轮题目范围完全被选手的答题范围覆盖），就能晋级到复赛阶段。为了节目效果，导演想让尽可能多的选手晋级复赛。请在所有可能的题目分配方式中，计算最多有多少名选手可以晋级。

输入描述

第一行包含两个正整数n和m（1≤n≤50000，1≤m≤100000）；

接下来n行，每行有两个正整数L_i和R_i，表示第i名选手能答对的题目范围（1≤L_i≤R_i≤m）。

输出描述

输出一个整数，表示最多可以晋级的选手数量。

样例输入

4 8

4 7

1 4

5 8

2 5

样例输出

3

样例解释 有4个参赛选手，8道试题： 第一位选手可作答4~7题； 第二位选手可作答1~4题； 第三位选手可作答5~8题； 第四位选手可作答2~5题。 此时有多种情况，其中一种情况为：将两轮闯关的题目分为4和除4外的其他题，此时选手1，2，4可在第一轮得到满分，进入复赛。

参考题解

是用差分数组统计每个题目被多少玩家覆盖。具体做法是：对每位玩家的答题区间 [L,R]，在差分数组 diffArray 中对 diffArray[L] 加 1，对 diffArray[R+1] 减 1，最后通过前缀和计算每道题的覆盖人数，并取最大值作为答案。这样避免了逐题遍历每位玩家的区间

C++：

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

int main() {
    int playerCount, questionCount;
    cin >> playerCount >> questionCount;
    
    // 差分数组，大小为问题数量+3以避免越界
    vector<int> diffArray(questionCount + 3, 0);
    
    for (int i = 0; i < playerCount; ++i) {
        int L, R;
        cin >> L >> R;
        diffArray[L] += 1;
        diffArray[R + 1] -= 1;
    }
    
    int currentCover = 0;
    int maxAdvancing = 0;
    
    // 计算每个问题的覆盖人数并找到最大值
    for (int q = 1; q <= questionCount; ++q) {
        currentCover += diffArray[q];
        if (currentCover > maxAdvancing) {
            maxAdvancing = currentCover;
        }
    }
    
    cout << maxAdvancing << endl;
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int playerCount = scanner.nextInt();
        int questionCount = scanner.nextInt();
        int[] diffArray = new int[questionCount + 3];
        for (int i = 0; i < playerCount; ++i) {
            int L = scanner.nextInt();
            int R = scanner.nextInt();
            diffArray[L] += 1;
            diffArray[R + 1] -= 1;
        }
        int currentCover = 0;
        int maxAdvancing = 0;
        for (int q = 1; q <= questionCount; ++q) {
            currentCover += diffArray[q];
            if (currentCover > maxAdvancing) maxAdvancing = currentCover;
        }
        System.out.println(maxAdvancing);
        scanner.close();
    }
}

Python：

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    
    player_count = int(input[ptr])
    ptr += 1
    question_count = int(input[ptr])
    ptr += 1
    
    # 初始化差分数组，大小为问题数量+3以避免越界
    diff_array = [0] * (question_count + 3)
    
    for _ in range(player_count):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        diff_array[L] += 1
        diff_array[R + 1] -= 1
    
    current_cover = 0
    max_advancing = 0
    
    # 计算每个问题的覆盖人数并找到最大值
    for q in range(1, question_count + 1):
        current_cover += diff_array[q]
        if current_cover > max_advancing:
            max_advancing = current_cover
    
    print(max_advancing)

if __name__ == "__main__":
    main()

第二题

小钟在一张长为n、宽为m的网格图上摆放积木。图上有一些格子是特殊格子，小钟有无限个尺寸为1×3或3×1的积木。每次摆放积木需满足以下条件： 积木至少有一端与特殊格子重合； 只能在网格图内摆放，不能超出； 当前要摆放的积木不能与已摆放的积木重叠。 小钟会一直按上述要求摆放积木，直到无法再摆放为止。小爱想知道网格图最终有多少种可能的局面，两种局面不同，当且仅当网格图中存在某个格子，一种局面中该格子被积木覆盖，另一种局面中没有被覆盖。 1≤n, m≤8，特殊格子数量不超过13，数据随机生成。

输入描述

第一行有两个整数n（1≤n≤8）、m（1≤m≤8），分别表示网格图的长和宽。 接下来n行，每行输入m个字符： 若网格图第i行第j列位置是特殊格子，则字符为*； 否则为.。

输出描述

输出一个整数，表示网格图最终可能的局面个数。

样例输入

4 4

....

...*

.*..

....

样例输出

2

说明： 样例输入 2 3 3 样例输出 2 1 样例解释 对于第一个样例，两种可能的游戏结束局面如下: ... ..* .....*.... .*** .*** ....对于第二个样例，可以横着摆三行每行一个积木，也可以纵着摆三列每列一个积木，但是这两种方式所导致的最终的局面是相同的，因此可能的局面数是 1。

参考题解

把所有可能的积木摆放位置用位掩码表示，再通过最大团枚举寻找所有可能的覆盖组合，并记录每个组合能覆盖的格子集合。最终答案是这些覆盖集合的不同个数。位运算保证了摆放冲突检测的高效性，避免了重复搜索，从而在可行的时间内枚举所有组合情况。

C++：

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

static int rows, cols;
static vector<uint64_t> placementMasks;
static vector<uint64_t> compatibilityMask;
static unordered_set<uint64_t> finalCoverMasks;

static int cellIndex(int r, int c) { return r * cols + c; }

static void enumerateMaximalSets(uint64_t candidateSet, uint64_t excludedSet, uint64_t currentCover) {
    if (candidateSet == 0ULL && excludedSet == 0ULL) {
        finalCoverMasks.insert(currentCover);
        return;
    }
    uint64_t unionSet = candidateSet | excludedSet;
    int pivotIndex = __builtin_ctzll(unionSet);
    int bestCount = -1;
    uint64_t tmp = unionSet;
    while (tmp != 0ULL) {
        int u = __builtin_ctzll(tmp);
        int cnt = __builtin_popcountll(candidateSet & compatibilityMask[u]);
        if (cnt > bestCount) {
            bestCount = cnt;
            pivotIndex = u;
        }
        tmp &= tmp - 1ULL;
    }
    uint64_t candidates = candidateSet & ~compatibilityMask[pivotIndex];
    while (candidates != 0ULL) {
        int v = __builtin_ctzll(candidates);
        uint64_t bitV = 1ULL << v;
        uint64_t newCandidate = candidateSet & compatibilityMask[v];
        uint64_t newExcluded  = excludedSet & compatibilityMask[v];
        uint64_t newCover     = currentCover | placementMasks[v];
        enumerateMaximalSets(newCandidate, newExcluded, newCover);
        candidateSet &= ~bitV;
        excludedSet |= bitV;
        candidates &= candidates - 1ULL;
    }
}

int main() {
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (int r = 0; r < rows; ++r) {
        cin >> grid[r];
    }

    vector<pair<int, int>> specialCells;
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == '*') {
                specialCells.emplace_back(r, c);