笔试时间：2025年9月7日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

笨蛋同学拿到了一个随机数据生成器，它会在区间[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

参考题解

解题思路：

x位数的区间范围：x=1时为[1,9]；x≥2时为[10^(x-1), 10^x-1]。将给定区间[l,r]与x位数区间取交集，计算交集内整数个数。

C++：

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long l,r;
    cin>>l>>r;
    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), R = min(r, high);
        long long ans = (R>=L? R-L+1 : 0);
        cout<<ans<<"\n";
    }
    return 0;
}

Java：

import java.util.*;

public class Solution {
    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);
        }
    }
}

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名亲戚来叫的时间间隔

输出描述

对于每一组测试数据，输出一行。输出一个整数，表示对应天第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

参考题解

解题思路：

使用二分查找找到第k次事件发生的时间t，然后确定在时间t时哪个亲戚来叫。需要注意使用__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; 
    cin>>T;
    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.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int n = sc.nextInt();
            long k = sc.nextLong();
            long[] a = new long[n];
            long amin = Long.MAX_VALUE;