笔试时间：2023年7月23日 提前批

第一题

题目：小红的数组构造

小红的数组构造小红希望你构造一个数组满足以下条件：1. 数组共有n个元素，且所有元素两两不相等。2. 所有元素的最大公约数等于k。3. 所有元素之和尽可能小。请你输出数组元素之和的最小值。

输入描述

两个正整数n和k

1≤ n,k ≤ 10^5

输出描述

一个正整数，代表数组元素之和的最小值。

样例输入

示例1:

3 1

示例2:

2 2

样例输出

示例1:

6

示例2:

6

参考题解

C++：

#include <iostream>

int main() {
    long long n, k;
    std::cin >> n >> k;
    std::cout << ((1 + n) * n / 2) * k << std::endl;
    return 0;
}

Java：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long k = sc.nextLong();
        System.out.println(((1+n)*n / 2 ) * k);
    }

}

Python：

n = int(input())
k = int(input())
print(((1 + n) * n // 2) * k)

第二题

题目：精华帖子

小红书的推荐帖子列表为[0,n]，其中所有的帖子初始状态为”普通“，现在运营同学把其中的一些帖子区间标记为了”精华“。

输入描述

第一行输入两个正整数n,m,k，代表初始帖子列表长度，精华区间的数量，以及运营同学准备截取的长度。

接下来的m行，每行输入两个正整数li,ri，代表第i个区间。

1 ≤ k ≤ n ≤ 1000000000

1 ≤ m ≤ 100000

0 ≤ li < ri ≤ n

保证任意两个区间是不重叠的。

输出描述

一个正整数，代表最多的精华帖子数量。

样例输入

5 2 3

1 2

3 5

样例输出

2

参考题解

二分+前缀和。

C++：

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

int main() {
    int n, m, k;
    std::cin >> n >> m >> k;

    std::vector<std::pair<int, int>> itv(m);

    for (int i = 0; i < m; i++) {
        std::cin >> itv[i].first >> itv[i].second;
    }

    std::sort(itv.begin(), itv.end());

    // 前缀和
    std::vector<int> pres(m + 1, 0);

    for (int i = 1; i <= m; i++) {
        pres[i] = pres[i - 1] + (itv[i - 1].second - itv[i - 1].first);
    }

    int res = 0;

    for (int i = 0; i < m; i++) {
        int l = i, r = m;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (itv[mid].second >= itv[i].first + k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        // r是大于等于当前区间起点的最大值
        if (r < m && itv[r].first <= itv[i].first + k) {
            // 包含在r区间中
            res = std::max(res, pres[r + 1] - pres[i] - (itv[r].second - itv[i].first - k));
        } else {
            res = std::max(res, pres[r] - pres[i]);
        }
    }

    std::cout << res << std::endl;
    return 0;
}

Java：

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();

        int[][] itv = new int[m][2];

        for (int i = 0; i < m; i++) {
            itv[i][0] = sc.nextInt();
            itv[i][1] = sc.nextInt();
        }

        Arrays.sort(itv, (a,b)->a[0] - b[0]);

        // 前缀和
        int[] pres = new int[m+1];

        for (int i = 1; i <= m; i++) pres[i] = pres[i-1] + (itv[i-1][1] - itv[i - 1][0]);