✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线110+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

题目一：图书馆资源配置优化

1️⃣：使用差分数组统计每个位置被多少个区间覆盖

2️⃣：计算前缀和得到覆盖次数，取最大值作为答案

难度：中等

这道题目的关键在于理解资源分配的策略。通过将其中一个阅览室设置为只包含单一资料的方式，问题转化为寻找被最多研究生需求区间覆盖的资料编号。差分数组的应用使得我们能够在 O(n+m) 的时间复杂度内解决问题。

题目二：古城遗迹探索路径

1️⃣：枚举每个标记位置作为石柱端点的所有可能放置方式

2️⃣：使用位运算表示覆盖状态，DFS搜索所有合法组合

3️⃣：用集合去重，统计不同的最终布局状态数量

难度：中等偏难

这道题目结合了状态枚举和位运算优化。由于标记位置数量有限（≤13），可以通过深度优先搜索枚举所有可能的石柱放置组合。关键技巧是使用位运算快速判断覆盖冲突，并用集合记录所有不同的最终状态。

01. 图书馆资源配置优化

问题描述

小毛是某大学图书馆的管理员，最近图书馆购入了 套珍贵的学术资料（编号从 到 ）。为了提高资源利用率，图书馆决定将这些资料分配到两个不同的阅览室中，每个阅览室至少要放置 套资料，且所有资料都必须分配完毕。

图书馆有 名研究生申请使用这些资料，每名研究生都有自己的研究方向，只对连续编号的一段资料感兴趣（用区间 表示第 名研究生需要的资料范围）。

如果某个阅览室中的所有资料都在某名研究生需要的范围内（即该阅览室的资料集合完全被研究生的需求区间覆盖），那么这名研究生就可以在该阅览室完成研究工作，从而获得图书馆的研究资格认证。

小毛希望通过合理的资料分配方案，让尽可能多的研究生能够获得研究资格认证。请帮助他计算在所有可能的分配方案中，最多有多少名研究生可以获得认证？

输入格式

第一行包含两个正整数 和 （，）。

接下来 行，每行包含两个正整数 和 ，表示第 名研究生需要的资料范围（）。

输出格式

输出一个整数，表示最多可以获得研究资格认证的研究生数量。

样例输入

4 8
4 7
1 4
5 8
2 5

样例输出

3

数据范围

• 
• 
• 

样例	解释说明
样例1	有4名研究生，8套资料。第1名研究生需要资料47，第2名需要14，第3名需要58，第4名需要25。可以将资料4单独放在一个阅览室，其余资料放在另一个阅览室。这样研究生1、2、4都可以在第一个阅览室完成研究（他们的需求区间都包含资料4），共3人获得认证。

题解

这道题的关键在于理解资料分配的本质。既然要将 套资料分为两个阅览室，而研究生的需求区间都是连续的，我们需要找到一个最优的分配策略。

仔细分析可以发现，如果我们将资料分为两部分，其中一部分不是连续区间，那么能够完全覆盖这部分的研究生需求区间会很少。因此，最优策略是让其中一个阅览室只包含一套资料，另一个阅览室包含剩余的所有资料。

具体来说，问题转化为：选择某个资料编号 （），将资料 单独放在一个阅览室，其余资料放在另一个阅览室。一个研究生能获得认证当且仅当：

1. 他的需求区间包含资料 ，或者
2. 他的需求区间包含除资料 外的所有其他资料

由于第二种情况基本不可能（需求区间要覆盖几乎所有资料），所以问题进一步简化为：选择哪个资料编号 ，使得需求区间包含 的研究生数量最多。

算法步骤：

1. 使用差分数组统计每个资料编号被多少个研究生需要
2. 对每个研究生的需求区间 ，在差分数组中标记：diff[L_i]++, diff[R_i+1]--
3. 计算差分数组的前缀和，得到每个资料编号被覆盖的次数
4. 返回最大的覆盖次数

时间复杂度：，空间复杂度：。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    n, m = map(int, input().split())
    
    # 差分数组统计每个位置被多少区间覆盖
    diff = [0] * (m + 2)
    
    for _ in range(n):
        l, r = map(int, input().split())
        diff[l] += 1
        diff[r + 1] -= 1
    
    # 计算前缀和得到每个位置的覆盖次数
    ans = 0
    cur_cnt = 0
    for i in range(1, m + 1):
        cur_cnt += diff[i]
        ans = max(ans, cur_cnt)
    
    print(ans)

solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    // 差分数组，用于统计每个位置的覆盖次数
    vector<int> diff(m + 2, 0);
    
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        // 区间[l,r]对差分数组的影响
        diff[l]++;
        diff[r + 1]--;
    }
    
    // 计算前缀和，得到每个位置被覆盖的次数
    int ans = 0, cnt = 0;
    for (int i = 1; i <= m; i++) {
        cnt += diff[i];
        ans = max(ans, cnt);
    }
    
    cout << ans << "\n";
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // 差分数组用于统计覆盖次数
        int[] diff = new int[m + 2];
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            
            // 在差分数组中标记区间影响
            diff[l]++;
            diff[r + 1]--;
        }
        
        // 通过前缀和计算每个位置的实际覆盖次数
        int maxCnt = 0, curCnt = 0;
        for (int i = 1; i <= m; i++) {
            curCnt += diff[i];
            maxCnt = Math.max(maxCnt, curCnt);
        }
        
        System.out.println(maxCnt);
    }
}

02. 古城遗迹探索路径

问题描述

小基是一名考古学家，她在一处古城遗迹中发现了一个 的方形区域。在这个区域中，有一些位置标记着古代文字符号（用"*"表示），其余位置都是普通的石板（用"."表示）。

小基手中有许多古代石柱，每根石柱的尺寸都是 或 （可以横着或竖着放置）。考古规则要求，每放置一根石柱时必须满足以下条件：

1. 石柱的至少一端必须与标记有古代文字的位置重合
2. 石柱必须完全放置在遗迹区域内，不能越界
3. 新放置的石柱不能与已经放置的石柱发生重叠

小基会按照上述规则持续放置石柱，直到无法再放置任何石柱为止。

小柯作为小基的助手，对最终的遗迹布局很好奇。她想知道遗迹区域最终可能有多少种不同的布局状态。两种布局状态被认为是不同的，当且仅当存在某个位置，在一种布局中该位置被石柱覆盖，而在另一种布局中没有被覆盖。注意，布局的不同与放置顺序无关，仅与位置是否被覆盖有关！

已知 ，标记有古代文字的位置数量不超过 。

输入格式

第一行包含两个整数 （）和 （），分别表示遗迹区域的长和宽。

接下来 行，每行包含 个字符。如果第 行第 列位置标记有古代文字，则对应字符为"*"，否则为"."。

输出格式

输出一个整数，表示遗迹区域最终可能的不同布局状态数量。

样例输入

4 4
....
...*
.*..
....

3 3
***
***
***

样例输出

2

1

数据范围

• 
• 标记古代文字的位置数量不超过

样例	解释说明
样例1	有两种可能的最终布局：一种是在第2行第4列和第3行第2列各放置一根竖直石柱，另一种是在第2行放置一根水平石柱。虽然放置方式不同，但最终覆盖的位置模式确实不同