笔试时间：2024年08月24日 秋招 阿里灵犀互娱

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

第一题

题目：减一

给出一组数，求出最长的子串。使得这个子串中的数最大值和最小值的差值最大为1。 如1 5 4 1 2 4 2 5 5。最长子串为5 4 4 5 5,长度为5。

输入描述

第一行为一整数n(1<=n<=100),表示整数的个数。 

下一行为n个整数，以空格分割，每个整数的值小于10^9。

输出描述

输出一个整数，为最长子串长度。

样例输入

6

4 6 5 3 3 1

样例输出

3

参考题解

模拟。

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

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

using namespace std;

int max_length_subarray(vector<int>& arr) {
    if (arr.empty()) {
        return 0;
    }

    sort(arr.begin(), arr.end());
    int start = 0;
    int max_length = 1;

    for (int end = 1; end < arr.size(); ++end) {
        if (arr[end] - arr[start] > 1) {
            ++start;
        }
        max_length = max(max_length, end - start + 1);
    }

    return max_length;
}

int main() {
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    cout << max_length_subarray(nums) << endl;

    return 0;
}

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

import java.util.*;

public class Main {
    public static int maxLengthSubarray(List<Integer> arr) {
        if (arr.isEmpty()) {
            return 0;
        }

        Collections.sort(arr);
        int start = 0;
        int maxLength = 1;

        for (int end = 1; end < arr.size(); ++end) {
            if (arr.get(end) - arr.get(start) > 1) {
                ++start;
            }
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> nums = new ArrayList<>(n);

        for (int i = 0; i < n; ++i) {
            nums.add(scanner.nextInt());
        }

        System.out.println(maxLengthSubarray(nums));
        scanner.close();
    }
}

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

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

def max_length_subarray(arr):
    if not arr:
        return 0
    
    arr.sort()  
    start = 0
    max_length = 1
    
    for end in range(1, len(arr)):
        if arr[end] - arr[start] > 1:
            start += 1
        max_length = max(max_length, end - start + 1)
    
    return max_length

print(max_length_subarray(nums))

第二题

题目：小杰的灵犀之旅

小杰在异世界探险时发现了一个有着奇妙法则的地方，灵犀帝国。这个法则让灵犀帝国的人不再为食物而烦恼。每逢每个月的最后一天，在灵犀帝国中的人会进入到其对应的奇妙领域，届时会有n轮食物大派送降临。奇妙领域存在着一条m个格子的路，在每轮的食物大派送中会在[l, r]的格子上放一颗灵果。此时小杰已经进入了奇妙领域，如果小杰将n轮食物大派送的所有灵果取走会拥有多少颗灵果呢？

输入描述

第一行包含一个正整数T (T < 10)，T代表数据组数。 

接下来T组数据，每组数据第一行两个正整数n，m。

第二行开始有n行，每行两个正整数l，r (1 <= l <= m, l <= r <= m)

输出描述

对于每组输入输出小杰拥有灵果的个数，由于答案可能过大所以答案%998244353。

说明

补充说明对于30%的数据 1 <= n <= 1000, 1 <= m <= 1000 对于50%的数据 1<= n <= 10000, 1 <= m <= 10000 对于100%的数据 1 <= n <= 100000, 1 <= m <= 100000

样例输入

2

1 2

1 2

3 6

1 2

1 2

4 5

样例输出

2

6

参考题解

将题目所给的所有区间累加即可，注意取模。

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

#include <iostream>

using namespace std;

int main() {
    int T;
    cin >> T;

    for (int i = 0; i < T; i++) {
        int n, m;
        cin >> n >> m;
        
        long long res = 0;
        for (int j = 0; j < n; j++) {
            int l, r;
            cin >> l >> r;
            res += r - l + 1;
            res %= 998244353;
        }
        
        cout << res << endl;
    }

    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        for (int i = 0; i < T; i++) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            
            long res = 0;
            for (int j = 0; j < n; j++) {
                int l = scanner.nextInt();
                int r = scanner.nextInt();
                res += r - l + 1;
                res %= 998244353;
            }
            
            System.out.println(res);
        }
        
        scanner.close();
    }
}

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

MOD = 998244353

def main():
    T = int(input())
    
    for _ in range(T):
        n, m = map(int, input().split())
        res = 0
        
        for _ in range(n):
            l, r = map(int, input().split())
            res += r - l + 1
            res %= MOD
        
        print(res)

if __name__ ==