笔试时间：2025年03月29日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：踩石头过河

有一条长度为n的河流，小O初始位于左岸边(即河流左侧的位置)，他想要跨越到河的对岸(即河流右侧的位置)。河上有一些石头可以供小O踩在上面。小O只能踩在石头或者岸边，他想知道他在能跨到河对岸的情况下，最长的一步最短是多少。

输入描述

第一行输入一个整数n(1 <= n <= 2*10^5)代表河流的长度。第二行输入n 个正整数 a1,a2,...,an(0 <= ai <= 1)代表是否是石头，如果ai=1，则说明当前位置是石头可以踩;否则是水流，不能踩。

输出描述

在一行上输出一个整数，表示最长的一步的最小值。

样例输入

5

0 1 1 0 1

样例输出

2

参考题解

模拟

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>

usingnamespacestd;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> pos;
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            pos.push_back(i + 1);
        }
    }
    pos.push_back(0);
    pos.push_back(n + 1);
    sort(pos.begin(), pos.end());
    int res = 0;
    for (int i = 1; i < pos.size(); ++i) {
        res = max(res, pos[i] - pos[i - 1]);
    }
    cout << res << endl;
    return0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        List<Integer> pos = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (a[i] != 0) {
                pos.add(i + 1); // 1-based position
            }
        }

        pos.add(0);       // add left boundary
        pos.add(n + 1);   // add right boundary
        Collections.sort(pos);

        int res = 0;
        for (int i = 1; i < pos.size(); i++) {
            res = Math.max(res, pos.get(i) - pos.get(i - 1));
        }

        System.out.println(res);
        scanner.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

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

pos = [i + 1 for i in range(n) if a[i] != 0]
pos.append(0)
pos.append(n + 1)
pos.sort()

res = 0
for i in range(1, len(pos)):
    res = max(res, pos[i] - pos[i - 1])

print(res)

第二题

题目：分割最少段数

小O有一个长度为 n 的数组 a，他在数组x上定义了一个函数f(x)，表示数组x中所有元素做按位|运算的结果。(例如x=[1,2,4,8]，则f(x)=1|2|4|8=15)小O现在希望将数组a分割成尽可能少的段，使得所有段的f函数值中的最大值不超过 k，请问他最少可以将a分为几段，请你帮帮他吧。

输入描述

输入包含两行。

第一行两个正整数n,k(1 ≤ n ≤ 200000),(1 ≤ k ≤ 10^9)，分别表示数组 a的长度，以及每段 f 函数值的上限。

第二行 n 个正整数 ai(1 < ai < 10^9)，表示数组 a 的元素。

输出描述

输出包含一行一个整数，如果可以做到，则输出最少分成的段数，否则输出-1。

样例输入

4 4

1 2 4 3

样例输出

3

参考题解

贪心，从前往后遍历数组，不断取或值，当或值大于指定的k时，需要新开一段，答案+1。在遍历时需要主要