✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：图书馆编号查询

1️⃣：理解偶数序列拼接规律，找到第n个字符所属的偶数

2️⃣：模拟累加字符长度，直到找到目标位置

难度：简单

这道题目的关键在于理解字符串的构成规律，通过模拟偶数递增过程来定位目标字符。采用逐步累加字符长度的方法，避免构造完整字符串，实现 O(√n) 的高效解法。

题目二：音乐团体组建

1️⃣：理解最大公约数大于1等价于有共同质因子

2️⃣：使用质数筛统计每个质数对应的乐器编号数量

3️⃣：通过双哈希去重，统计不同的组建方案

难度：中等

这道题目结合了数论和哈希技巧，需要理解最大公约数的本质是共同质因子。通过线性筛生成质数，然后统计每个质数能覆盖的乐器数量，最后用双哈希避免重复计数。

题目三：科研项目时间规划

1️⃣：使用离线算法将查询和项目按左端点排序

2️⃣：坐标压缩处理大范围的右端点值

3️⃣：树状数组维护满足条件的项目并快速查询

难度：中等偏难

这道题目需要理解二维范围查询的优化方法，通过离线处理和树状数组实现高效的区间包含统计。关键在于将二维问题转化为一维前缀和查询，实现 O((n+m) log(n+m)) 的时间复杂度。

01. 图书馆编号查询

问题描述

小兰在图书馆工作，负责管理图书编号系统。图书馆采用特殊的编号规则：从第一本书开始，编号依次为 （即所有非负偶数）。

为了方便管理，小兰将所有编号按顺序拼接成一个长字符串：。现在她需要快速查找这个字符串中第 个字符是什么。

输入格式

第一行包含一个正整数 （），表示要查询的字符位置。

输出格式

输出一个字符，表示拼接字符串中第 个字符。

样例输入

6

1

样例输出

1

0

数据范围

题解

这道题的核心是理解字符串的构成规律。图书编号按照偶数递增：0, 2, 4, 6, 8, 10, 12...，拼接后形成"0246810121416..."。

关键观察：我们不需要真的构造出完整的字符串，只需要找到第 个字符属于哪个偶数，以及在该偶数中的位置。

解题思路：

1. 从偶数0开始，依次计算每个偶数转为字符串后的长度
2. 累加这些长度，直到总长度首次
3. 此时最后加入的偶数就包含了第 个字符
4. 计算该字符在这个偶数字符串中的具体位置

例如查询第6个字符：

• 偶数0：长度1，累计长度1
• 偶数2：长度1，累计长度2
• 偶数4：长度1，累计长度3
• 偶数6：长度1，累计长度4
• 偶数8：长度1，累计长度5
• 偶数10：长度2，累计长度7 ≥ 6

所以第6个字符在偶数10的字符串"10"中，位置为 6-5-1=0，即字符'1'。

时间复杂度 ，因为前 个偶数的总字符长度约为 ，所以需要检查的偶数个数为 。

参考代码

• Python

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

n = int(input())
pos = 0  # 当前累计字符数
num = 0  # 当前偶数

while True:
    s = str(num)  # 将偶数转为字符串
    if pos + len(s) >= n:
        # 第n个字符在当前偶数的字符串中
        print(s[n - pos - 1])
        break
    pos += len(s)  # 累加字符数
    num += 2      # 下一个偶数

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    int pos = 0;  // 累计字符数
    int num = 0;  // 当前偶数
    
    while (true) {
        string s = to_string(num);  // 偶数转字符串
        if (pos + s.length() >= n) {
            // 找到目标字符
            cout << s[n - pos - 1] << endl;
            break;
        }
        pos += s.length();  // 累加长度
        num += 2;          // 下一个偶数
    }
    
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int pos = 0;  // 累计字符数
        int num = 0;  // 当前偶数
        
        while (true) {
            String s = String.valueOf(num);  // 偶数转字符串
            if (pos + s.length() >= n) {
                // 找到目标字符所在偶数
                System.out.println(s.charAt(n - pos - 1));
                break;
            }
            pos += s.length();  // 累加字符长度
            num += 2;          // 移动到下一个偶数
        }
        
        sc.close();
    }
}

02. 音乐团体组建

问题描述

小基 音乐学院正在组建各种音乐团体。学院有 位音乐家，每位音乐家都擅长演奏特定的乐器，用一个正整数 表示。

为了组建和谐的音乐团体，学院要求团体中所有成员必须有共同的音乐风格。具体来说，如果选择一些音乐家组成团体，他们擅长的乐器编号的最大公约数必须大于 。

小基 希望组建一个人数尽可能多的音乐团体，并想知道满足条件的最大团体规模，以及有多少种不同的组建方案。

如果两个团体包含的乐器编号的多重集合相同，则认为是同一种组建方案（即不区分成员的具体身份，只看乐器编号及其出现次数）。

输入格式

第一行包含一个正整数 （），表示音乐家的数量。

第二行包含 个正整数 （），表示每位音乐家擅长的乐器编号。

题目保证至少有一位音乐家的乐器编号不是 。

输出格式

输出两个整数，第一个表示最大团体规模，第二个表示满足最大规模的不同组建方案数。

样例输入

6
2 4 3 9 7 35

样例输出

2 3

数据范围

• 
• 
• 保证序列中的元素不全为

题解

这道题的核心是理解音乐团体的组建规则：团体中所有成员的乐器编号必须有大于1的最大公约数，也就是说他们必须共享某个质因子。

关键观察：如果要让团体规模最大，应该选择所有包含某个特定质因子的音乐家。因此问题转化为：对每个质数，统计有多少个乐器编号包含这个质因子。

解题思路：

1. 统计每个乐器编号的出现次数
2. 对每个质数 ，计算所有能被 整除的乐器编号的总出现次数
3. 找到出现次数最多的质数对应的团体规模
4. 统计有多少个不同的质数能达到这个最大规模

方案去重的关键：两个质数如果对应完全相同的乐器编号多重集合，就算作同一种方案。我们使用双哈希来区分不同的多重集合。

例如样例：乐器编号 [2,4,3,9,7,35]

• 质数2：包含2,4，团体规模2
• 质数3：包含3,9，团体规模2
• 质数7：包含7,35，团体规模2

三个质数都能组建规模为2的团体，且对应不同的乐器组合，所以答案是 2 3。

时间复杂度 ，其中 是乐器编号的上界，主要消耗在质数筛选和倍数枚举上。

参考代码

• Python

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

def sieve(maxn):
    # 线性筛生成质数
    is_prime = [True] * (maxn + 1)
    is_prime[0] = is_prime[1] = False
    primes = []
    
    for i in range(2, maxn + 1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if p * i > maxn:
                break
            is_prime[p * i] = False
            if i % p == 0:
                break
    return primes

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

# 统计每个乐器编号出现次数
freq = {}
for x in a:
    freq[x] = freq.get(x, 0) + 1

maxval = max(a)
primes = sieve(maxval)

MOD1, MOD2 = 1000000007, 1000000009
cnt, h1, h2 = {}, {}, {}

# 对每个质数计算团体规模和哈希值
for p in primes:
    cnt[p] = h1[p] = h2[p] = 0
    for mult in range(p, maxval + 1, p):
        if mult in freq:
            cnt[p] += freq[mult]
            h1[p] = (h1[p] + freq[mult] * mult) % MOD1
            h2[p] = (h2[p] + freq[mult] * mult) % MOD2

max_size = max(cnt[p] for p in primes)

# 统计不同的哈希值
seen = set()
for p in primes:
    if cnt[p] == max_size:
        seen.add((h1[p], h2[p]))

print(max_size, len(seen))

• Cpp

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

const int MAXV = 2000000;
const int MOD1 = 1000000007;
const int MOD2 = 1000000009;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    static int freq[MAXV + 1] = {};
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;
    }
    
    // 线性筛生成质数
    vector<int> primes;
    static int lp[MAXV + 1] = {};  // 最小质因子
    
    for (int i = 2; i <= MAXV; i++) {
        if (!lp[i]) {
            lp[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > lp[i] || 1LL * p * i > MAXV) break;
            lp[p * i] = p;
        }
    }
    
    static int cnt[MAXV + 1] = {};
    static long long h1[MAXV + 1] = {};
    static long long h2[MAXV + 1] = {};
    
    // 计算每个质数的团体规模和哈希
    for (int p : primes) {
        for (int mult = p; mult <= MAXV; mult += p) {
            if (freq[mult] == 0) continue;
            cnt[p] += freq[mult];
            h1[p] = (h1[p] + 1LL * freq[mult] * mult) % MOD1;
            h2[p] = (h2[p] + 1LL * freq[mult] * mult) % MOD2;
        }
    }
    
    int maxSize = 0;
    for (int p : primes) {
        maxSize = max(maxSize, cnt[p]);
    }
    
    set<pair<long long, long long>> hashSet;
    for (int p : primes) {
        if (cnt[p] == maxSize) {
            hashSet.insert({h1[p], h2[p]});
        }
    }
    
    cout << maxSize << " " << hashSet.size() << "\n";
    return 0;
}

• Java

import java.util.*;

public class Main {