笔试时间：2023年9月20日 秋招

第一题

题目：丢失报文的位置

某通信系统持续向外发送报文，使用数组nums保存n个最近发送的报文，用于在报文未达到对端的情况下重发。报文使用序号sn表示，序号sn按照报文发送顺序从小到大排序，相邻报文sn不完全连续且有可能相同。报文使用循环覆盖的方式保存，即nums数组填满后，从头开始保存新的报文。假设需要重发序号为sn的报文。请找出序号为sn的报文在数组中的开始位置和结束位置。

解答要求：时间限制:C/C++1000ms,其他语言: 2000ms内存限制: C/C++256MB其他语言:512MB

输入描述

第一行输入:数组nums的大小n，取值范围[0,10000]

第二行输入:数组中的所有报文的序号sn，sn取值范围[0,100000]。

第三行输入:需要重发的报文序号sn，取值范围[0,100000]

输出描述

start end

说明：start和end代表需要重发的报文序号sn在数组中的起始下标和结束下标

样例输入

7

0 0 1 2 2 5 6

1

样例输出

2 2

解释

nums数组大小为7。保存了7个报文，sn分别是0 0 1 2 2 5 6

sn为1的报文在数组中仅有1个，下标是2，因此输出2 2

参考题解

模拟。找到最小值，实际上是从从小开始，从最小值开始的第一个是起点，然后是终点。

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

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

int main() {
    int n, search_number;
    cin >> n;
    
    vector<int> numbers(n, -1);
    for (int i = 0; i < n; i++) 
        cin >> numbers[i];
    
    cin >> search_number;
    
    int min_index = 0;
    int max_value = numbers[0];
    
    for (int i = 0; i < n; i++) {
        if (numbers[i] < max_value) {
            max_value = numbers[i];
            min_index = i;
        }
    }

    int start_index = -1;
    int end_index = -1;
    
    for (int i = 0; i < n; i++) {
        int current_index = (min_index + i) % n;
        if (numbers[current_index] == search_number) {
            if (start_index == -1) {
                start_index = current_index;
                end_index = current_index;
            }
            else {
                end_index = current_index;
            }
        }
    }
    
    cout << start_index << " " << end_index << endl;
}

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

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        ArrayList<Integer> numbers = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            numbers.add(input.nextInt());
        }
        int searchNumber = input.nextInt();
        int minIndex = 0;
        int maxValue = numbers.get(0);

        for (int i = 0; i < n; i++) {
            if (numbers.get(i) < maxValue) {
                maxValue = numbers.get(i);
                minIndex = i;
            }
        }

        int startIndex = -1;
        int endIndex = -1;

        for (int i = 0; i < n; i++) {
            int currentIndex = (minIndex + i) % n;
            if (numbers.get(currentIndex) == searchNumber) {
                if (startIndex == -1) {
                    startIndex = currentIndex;
                    endIndex = currentIndex;
                } else {
                    endIndex = currentIndex;
                }
            }
        }

        System.out.println(startIndex + " " + endIndex);
    }
}

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

n = int(input())
numbers = list(map(int, input().split()))
search_number = int(input())

min_index = 0
max_value = numbers[0]

for i in range(n):
    if numbers[i] < max_value:
        max_value = numbers[i]
        min_index = i

start_index = -1
end_index = -1

for i in range(n):
    current_index = (min_index + i) % n
    if numbers[current_index] == search_number:
        if start_index == -1:
            start_index = current_index
            end_index = current_index
        else:
            end_index = current_index

print(start_index, end_index)

第二题

题目：快速传球

班级组织传球活动，男女同学随机排成m行n列队伍，第一列中的任意一个男同学都可以作为传球的起点，要求最终将球传到最后一列的任意一个男同学手里，求所有能够完成任务的传球路线中的最优路线(传球次数最少的路线)的传球次数。传球规则：1、男同学只能将球传给男同学，不能传给女同学。2、球只能传给身边前后左右相邻的同学。3、如果游戏不能完成，返回-1。

说明：1、传球次数最少的路线为最优路线。2、最优路线可能不唯一，不同最优路线都为最少传球次数。

解答要求：时间限制:C/C++100ms其他语言: 200ms内存限制: C/C++256MB,其他语言: 512MB。

输入描述

班级同学随机排成的m行n列队伍，1代表男同学，0代表女同学；

输入第一行包含两个用空格分开的整数m[1,30]和n [1,30]，表示m行n列的队伍；

接下来是m行每行包含n个用空格分开的整数1或0。

输出描述

最优路线的传球次数（最少传球次数）。

样例输入

4 4

1 1 1 0

1 1 1 0

0 0 1 0

0 1 1 1

样例输出

5

参考题解

最短路BFS。

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

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

class ShortestPathFinder {
public:
    int numRows, numCols;
    vector<vector<int>> grid;

    void solve() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        cin >> numRows >> numCols;
        grid.resize(numRows, vector<int>(numCols));

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                cin >> grid[i][j];
            }
        }

        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int result = INT_MAX;

        for (int i = 0; i < numRows; i++) {
            if (grid[i][0] == 1) {
                queue<vector<int>> q;
                q.push({0, i, 0});
                vector<vector<bool>> used(numRows, vector<bool>(numCols, false));
                used[i][0] = true;

                while (!q.empty()) {
                    vector<int> current = q.front();
                    q.pop();
                    int distance = current[0];
                    int x = current[1];
                    int y = current[2];

                    if (y == numCols - 1) {
                        result = min(result, distance);
                    }

                    for (vector<int> dir : directions) {
                        int nx = x + dir[0];
                        int ny = y + dir[1];

                        if (isValid(nx, ny) && !used[nx][ny] && grid[nx][ny] == 1) {
                            used[nx][ny] = true;
                            q.push({distance + 1, nx, ny});
                        }
                    }
                }
            }
        }