笔试时间：2025年10月19日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

在游戏中，主人公 Tk 有一个长度为 n 的数组 a[1], a[2], ..., a[n]；他将一个数组称为令人心动，当且仅当该数组的最大值不超过最小值的两倍，即 max(a[1], a[2], ..., a[n]) ≤ 2 × min(a[1], a[2], ..., a[n])；为了让自己的数组变为令人心动，他可以进行以下操作多次，直到满足条件：

选择一个元素 a[i]，并选取两个正整数 x, y 满足 x + y = a[i]，将 a[i] 删除，并将 x, y 插入数组中；请你计算使数组变为令人心动所需的最少操作次数。

输入描述

第一行输入一个整数 n（1 ≤ n ≤ 10^5），表示数组的长度； 第二行输入 n 个整数 a[1], a[2], ..., a[n]（1 ≤ a[i] ≤ 10^6），表示数组中的元素。

输出描述

输出一个整数，表示将数组变为令人心动的最少操作次数。

样例输入

3

3 6 13

样例输出

2

在此样例中，初始数组为 [3, 6, 13]，操作方案不唯一； 将 13 拆分为 5 和 8，数组变为 [3, 6, 5, 8]； 将 8 拆分为 4 和 4，数组变为 [3, 6, 5, 4, 4]，此时最大值 6 不超过最小值 3 的两倍，满足条件，共需 2 次操作。

参考题解

解题思路：

1. 确定最小值：由于拆分操作只能产生更小的数，最小值不会增大，所以保留原数组最小值作为最终的最小值是最优的
2. 确定最大值上限：根据心动数组条件，最大值 ≤ 2 × 最小值
3. 计算拆分次数：对于每个元素，如果大于 2 × 最小值，需要拆分成若干段，每段 ≤ 2 × 最小值
4. 公式化简：拆分次数 = (a[i] - 1) // (2 × min)

C++：

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

int f1(int x, int y) {
    return (x - 1) / y;
}

int f2(int x) {
    return 2 * x;
}

int main() {
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    int m = *min_element(b.begin(), b.end());
    int t = f2(m);
    int r = 0;
    
    for (int i = 0; i < n; i++) {
        r += f1(b[i], t);
    }
    
    cout << r << endl;
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static int f1(int x, int y) {
        return (x - 1) / y;
    }
    
    public static int f2(int x) {
        return 2 * x;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] b = new int[n];
        
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        
        int m = Arrays.stream(b).min().getAsInt();
        int t = f2(m);
        int r = 0;
        
        for (int i = 0; i < n; i++) {
            r += f1(b[i], t);
        }
        
        System.out.println(r);
    }
}

Python：

import sys

def f1(x, y):
    return (x - 1) // y

def f2(x):
    return 2 * x

n = int(sys.stdin.readline())
b = list(map(int, sys.stdin.readline().split()))
m = min(b)
t = f2(m)
r = 0
i = 0
while i < n:
    r += f1(b[i], t)
    i += 1
print(r)

第二题

给定一个长度为 n 的数组 a。你可以对数组执行以下操作任意次： 选择两个不同的下标 i, j，满足 i < j 且 ⌊n/i⌋ = ⌊n/j⌋； 将 a[i] 与 a[j] 同时替换为 gcd(a[i], a[j])。 请输出操作后（或者不执行任何操作）数组所有元素之和的最小值。 【名词解释】 - ⌊x⌋：代表对 x 进行下取整操作，得到不超过 x 的最大整数。 - 最大公约数（gcd）：指两个或多个整数共有约数中最大的一个。例如，12 和 30 的公约数有 1, 2, 3, 6，其中最大的约数是 6，因此记作 gcd(12, 30) = 6。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T（1 ≤ T ≤ 10^4）代表数据组数，每组测试数据描述如下： 第一行输入一个整数 n（1 ≤ n ≤ 10^5）代表数组长度； 第二行输入 n 个整数 a[1], a[2], ..., a[n]（1 ≤ a[i] ≤ 10^9）代表数组中的元素； 除此之外，保证单个测试文件的 n 之和不超过 2×10^5。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示操作后数组所有元素之和的最小值。

样例输入

1 6 1 2 3 7 8 9

样例输出

9

参考题解

解题思路：

1. 操作的本质：每次操作会将两个数替换为它们的gcd，由于gcd不会大于原来的数，这个操作只会让元素变小或保持不变
2. 分组的秘密：条件 ⌊n/i⌋ = ⌊n/j⌋ 实际上将下标 1 到 n 划分成了若干组，每组内的下标可以互相操作
3. 组内操作的影响：在同一个组内，通过多次操作让组内所有元素都变成它们的最小公因数（整个组的gcd）

C++：

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

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

bool solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    long long total_min_sum = 0;
    int l = 1;
    
    while (l <= n) {
        int k = n / l;
        int r = n / k;
        
        int group_gcd = a[l - 1];
        for (int i = l; i <= r && i < n; i++) {
            group_gcd = gcd(group_gcd, a[i]);
            if (group_gcd == 1) break;
        }
        
        int group_size = r - l + 1;
        total_min_sum += (long long)group_size * group_gcd;
        l = r + 1;
    }
    
    cout << total_min_sum << endl;
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t-