笔试时间：2025年9月26日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

笨蛋同学拿到了一个随机数据生成器，它会在区间 [l,r] 上以等概率生成一个整数。她想知道：区间内恰好为 x 位数的整数有多少个。

请你输出在 [l,r] 中，恰好是 x 位数的整数个数。

在本题中，x 位数定义为：当 x = 1 时，为区间 [1,9] 内的整数；当 x ≥ 2 时，为区间 [10^(x-1), 10^x - 1] 内的整数。

输入描述

第一行输入两个整数 l,r (1 ≤ l ≤ r ≤ 2 × 10^9)，表示生成器的取值范围。 第二行输入一个整数 q (1 ≤ q ≤ 9)，表示询问的次数。 此后 q 行，第 i 行输入一个整数 x_i (1 ≤ x_i ≤ 9)，表示第 i 次询问的位数。

输出描述

输出 q 行。对于每次询问，输出一个整数，表示在区间 [l,r] 中恰好为 x 位数的整数个数。

样例输入

1 20

4

1

2

3

9

样例输出

9

11

0

0

样例说明： 区间 [1,20] 中，1 位数共有 9 个 (1 ~ 9)，2 位数共有 11 个 (10 ~ 20)，更高位不存在。

参考题解

解题思路：

• x 位数的区间定义：1位数是[1,9]，x≥2时是[10^(x-1), 10^x-1]
• 对每个查询，计算x位数区间与[l,r]的交集
• 预先计算10的幂次，避免重复计算
• 使用64位整数避免溢出

C++：

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long l, r;
    if(!(cin >> l >> r)) return 0;
    
    int q; 
    cin >> q;
    
    long long p[11]; 
    p[0] = 1;
    for(int i = 1; i <= 10; i++) 
        p[i] = p[i-1] * 10LL;
    
    for(int i = 0; i < q; i++){
        int x; 
        cin >> x;
        
        long long low = (x == 1 ? 1 : p[x-1]);
        long long high = p[x] - 1;
        long long L = max(l, low);
        long long R = min(r, high);
        long long ans = (R >= L ? R - L + 1 : 0);
        
        cout << ans << "\n";
    }
    
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long l = sc.nextLong();
        long r = sc.nextLong();
        
        int q = sc.nextInt();
        
        long[] p = new long[11];
        p[0] = 1;
        for(int i = 1; i <= 10; i++) {
            p[i] = p[i-1] * 10L;
        }
        
        for(int i = 0; i < q; i++) {
            int x = sc.nextInt();
            
            long low = (x == 1 ? 1 : p[x-1]);
            long high = p[x] - 1;
            long L = Math.max(l, low);
            long R = Math.min(r, high);
            long ans = (R >= L ? R - L + 1 : 0);
            
            System.out.println(ans);
        }
        
        sc.close();
    }
}

Python：

l, r = map(int, input().split())
q = int(input())

p = [1]
for i in range(1, 11):
    p.append(p[-1] * 10)

for _ in range(q):
    x = int(input())
    
    low = 1 if x == 1 else p[x-1]
    high = p[x] - 1
    L = max(l, low)
    R = min(r, high)
    ans = R - L + 1 if R >= L else 0
    
    print(ans)

第二题

题目描述：阿宅的寒假共有 T 天；每天有 n 名亲戚来他家做客；每到饭点时，所有亲戚会来叫在房间里编程的阿宅吃饭；第 i 名亲戚每隔 a_i 秒会来一次，首次来叫的时间为 a_i 秒（即，第 i 名亲戚的到访时间为 a_i, 2a_i, 3a_i, …）。

阿宅想知道，每一天第 k 次来叫他的亲戚编号；若同一秒内有多名亲戚同时来叫，则编号较小者优先。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 T (1 ≤ T ≤ 30)，表示寒假天数；此后对每天数据，描述如下： 在一行上输入两个整数 n 和 k (1 ≤ n ≤ 10^5; 1 ≤ k ≤ 10^9)，分别表示亲戚人数和要查询的第 k 次。 在一行输入 n 个整数 a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9)，表示第 i 名亲戚来叫的时间间隔。 除此之外，保证单个测试文件的 n 之和不超过 2 × 10^5。

输出描述

对于每一组测试数据，输出一行。输出一个整数，表示对应天第 k 次来叫吃饭的亲戚编号。

样例输入

6

3 1

1 2 3

3 2

1 2 3

3 3

1 2 3

3 4

1 2 3

3 5

1 2 3

3 6

5 7 11

样例输出

1

1

2

1

3

1

样例说明：对于第一、二、三、四、五组测试数据，每一秒的到访序列依次为：

• 第一秒，仅有亲戚 1 来叫；
• 第二秒，亲戚 1 和 2 来叫；
• 第三秒，亲戚 1 和 3 来叫。

参考题解

解题思路：

• 二分查找第k次访问发生的时间t
• 对于时间m，计算到m为止总共有多少次访问
• 找到恰好第k次访问的时间后，确定是哪个亲戚
• 使用__int128避免溢出

C++：

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T; 
    if(!(cin >> T)) return 0;
    
    while(T--){
        int n; 
        ll k; 
        cin >> n >> k;
        
        vector<ll> a(n);
        ll amin = LLONG_MAX;
        for(int i = 0; i < n; i++){ 
            cin >> a[i]; 
            amin = min(amin, a[i]); 
        }
        
        ll l = 1, r = amin * k;
        while(l < r){
            ll m = l + (r - l) / 2;
            __int128 cnt = 0;
            for(int i = 0; i < n; i++){
                cnt += m / a[i];
                if(cnt >= k) break;
            }
            if(cnt >= k) r = m; 
            else l = m + 1;
        }
        
        ll t = l;
        __int128 before = 0;
        if(t > 0){
            ll tm = t - 1;
            for(int i = 0; i < n; i++){
                before += tm / a[i];
                if(before >= k) break;
            }
        }
        
        ll rem = k - (long long)before;
        int ans = -1;
        for(int i = 0; i < n; i++){
            if(t % a[i] == 0){
                rem--;
                if(rem == 0){ 
                    ans = i + 1; 
                    break; 
                }
            }
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

Java：

import java.util.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while(T-- > 0) {