笔试时间：2024年08月10日

历史笔试传送门：2023秋招笔试合集

第一题

题目

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

输入描述

第一行输入一个整数n代表河流的长度。

第二行输入n个正整数a1,a2...an 代表是否是石头，如果ai= 1，则说明当前位置是石头，可以踩；否则是水流，不能踩。

输出描述

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

样例输入一

5

0 1 0 1 1

样例输出一

2

样例输入二

8

0 1 1 0 0 0 1 1

样例输出二

4

参考题解

求数组中任意两个1之间最大间隔了多少个0，然后加一即可。所以只需要顺序遍历一遍数组，用一个变量cur记录数组中前一个1的位置，如果当前的数是1，就计算两个1之间的间隔，更新答案即可。这里需要注意的是，河的右端也是可以站立的，所以如果数组的后缀全是0，还需要更新一次答案。

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

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200010;
int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    int cur = 0;
    int res = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            res = max(res, i - cur);
            cur = i;
        }
    }
    // 如果最后一个元素不是1，还需要更新一次
    if (cur != n) res = max(res, n - cur + 1);
    cout << res;

    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[] a = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        
        int cur = 0;
        int res = 1;
        for (int i = 1; i <= n; i++) {
            if (a[i] == 1) {
                res = Math.max(res, i - cur);
                cur = i;
            }
        }
        
        if (cur != n) {
            res = Math.max(res, n - cur + 1);
        }
        
        System.out.println(res);
        
        sc.close();
    }
}

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

def main():
    import sys
    input = sys.stdin.read
    data = list(map(int, input().split()))
    
    n = data[0]
    a = data[1:]
    
    cur = 0
    res = 1
    for i in range(n):
        if a[i] == 1:
            res = max(res, i - cur + 1)
            cur = i + 1  # 1-based index to 0-based
    
    if cur <= n:
        res = max(res, n - cur + 1)
    
    print(res)

if __name__ == "__main__":
    main()

第二题

题目

小O有一个长度为n的数组a，他在数组x上定义了一个函数f(x)，表示数组x中所有元素做按位|（或）运算的结果。

小O现在希望将数组a分割成尽可能少的段，使得所有段的f函数值中的最大值不超过k，请问他最少可以将a分为几段，请你帮帮他吧。

输入描述

输入包含两行。

第一行两个整数，分别表示数组的长度，以及每段f函数值的上限。

第二行n个正整数ai，表示数组a的元素。

输出描述

在一行上输出一个整数，表示最少能分成多少段。如果无法分段，输出-1。

样例输入一

4 8

1 2 4 8

样例输出一

2

说明：

可以分成两段：[[1,2,4], [8]]

样例输入二

4 3

1 2 4 8

样例输出二

-1

参考题解

贪心。

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

#include <iostream>
using namespace std;

const int N = 200010;
int a[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    
    int cur = 0;
    int res = 0;
    for (int i = 0; i < n; i++) {
        int t = cur | a[i];
        if (t > k) {
            res++;
            cur = a[i];
            if (cur > k) {
                res = -1;
                break;
            }
        } else {
            cur = t;