笔试时间：2025年10月12日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

Tk有一个长度为n的数组a，数组的权值为所有元素之和。为了使数组权值最大，Tk提出超级重排流程：

1. 将所有元素的十进制表示按顺序拼接成一个字符串；
2. 对该字符串中的所有字符进行重新排列；
3. 按照原元素的位数切分字符，恢复为n个新数字。

或者说，首先收集所有数字的每一个单独的数位；其次，对于每一个原始数字a[i]，记录下它的位数，必须用收集到的所有数位来构造n个新数字，其中第i个新数字的位数必须与原始数组中第i个数字a[i]的位数相同。目标是找到一种分配这些数位的方式，使得这n个新数字的总和达到最大。

输入描述

第一行输入一个整数n（1≤n≤10^5），表示数组长度。 第二行输入n个整数a[i]（1≤a[i]≤10^9），题目保证每个元素的十进制表示中不含字符'0'。

输出描述

输出一个整数，表示经过超级重排后数组的最大权值。

样例输入

2

36 15

样例输出

114

参考题解

解题思路：题目要求通过重排所有数字的数位，构造n个新数字（每个新数字的位数与原始数字相同），使得新数字的总和最大。关键在于将高权重（高位）分配给大的数字。

1. 统计每个原始数字的位数和所有数位中每个数字（0-9）的出现次数。
2. 确定每个数位权重的槽位数量：对于第e位，其权重为10^e，该位能被分配的条件是原始数字的位数≥e+1。
3. 贪心分配：从最高权重位开始，用最大的数字（9→0）填充槽位。

C++：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> tokens(n);
    int maxL = 0;
    vector<int> len_cnt(11, 0);
    vector<int> digit_cnt(10, 0);
    
    for (int i = 0; i < n; i++) {
        cin >> tokens[i];
        int L = tokens[i].length();
        len_cnt[L]++;
        maxL = max(maxL, L);
        for (char ch : tokens[i]) {
            int d = ch - '0';
            digit_cnt[d]++;
        }
    }
    
    vector<int> suff_ge(maxL + 2, 0);
    int s = 0;
    for (int L = maxL; L >= 1; L--) {
        s += len_cnt[L];
        suff_ge[L] = s;
    }
    
    vector<long long> pow10(maxL);
    pow10[0] = 1;
    for (int e = 1; e < maxL; e++) {
        pow10[e] = pow10[e - 1] * 10;
    }
    
    long long ans = 0;
    int d = 9;
    for (int e = maxL - 1; e >= 0; e--) {
        int slots = suff_ge[e + 1];
        while (slots > 0) {
            if (digit_cnt[d] == 0) {
                d--;
                continue;
            }
            int take = min(digit_cnt[d], slots);
            ans += (long long)take * d * pow10[e];
            digit_cnt[d] -= take;
            slots -= take;
        }
    }
    
    cout << ans << 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();
        String[] tokens = new String[n];
        int maxL = 0;
        int[] lenCnt = new int[11];
        int[] digitCnt = new int[10];
        
        for (int i = 0; i < n; i++) {
            tokens[i] = sc.next();
            int L = tokens[i].length();
            lenCnt[L]++;
            maxL = Math.max(maxL, L);
            for (char ch : tokens[i].toCharArray()) {
                int d = ch - '0';
                digitCnt[d]++;
            }
        }
        
        int[] suffGe = new int[maxL + 2];
        int s = 0;
        for (int L = maxL; L >= 1; L--) {
            s += lenCnt[L];
            suffGe[L] = s;
        }
        
        long[] pow10 = new long[maxL];
        pow10[0] = 1;
        for (int e = 1; e < maxL; e++) {
            pow10[e] = pow10[e - 1] * 10;
        }
        
        long ans = 0;
        int d = 9;
        for (int e = maxL - 1; e >= 0; e--) {
            int slots = suffGe[e + 1];
            while (slots > 0) {
                if (digitCnt[d] == 0) {
                    d--;
                    continue;
                }
                int take = Math.min(digitCnt[d], slots);
                ans += (long)take * d * pow10[e];
                digitCnt[d] -= take;
                slots -= take;
            }
        }
        
        System.out.println(ans);
    }
}

Python：

def main():
    n = int(input())
    tokens = input().split()
    maxL = 0
    len_cnt = [0] * 11
    digit_cnt = [0] * 10
    
    for tok in tokens:
        L = len(tok)
        len_cnt[L] += 1
        if L > maxL:
            maxL = L
        for ch in tok:
            d = int(ch)
            digit_cnt[d] += 1
    
    suff_ge = [0] * (maxL + 2)
    s = 0
    for L in range(maxL, 0, -1):
        s += len_cnt[L]
        suff_ge[L] = s
    
    pow10 = [1] * maxL
    for e in range(1, maxL):
        pow10[e] = pow10[e - 1] * 10
    
    ans = 0
    d = 9
    for e in range(maxL - 1, -1, -1):
        slots = suff_ge[e + 1]
        while slots > 0:
            if digit_cnt[d] == 0:
                d -= 1
                continue
            take = min(digit_cnt[d], slots)
            ans += take * d * pow10[e]
            digit_cnt[d] -= take
            slots -= take
    
    print(ans)

main()

第二题

小红书后端基础设施包含n个服务器节点，编号1到n。第i个节点与相邻节点（即编号i-1和i+1的节点，如果存在）通过链路相连。每一个节点都有它的传输信号限制，第i个节点发送的数据至多只能经过d[i]条链路。现在需在若干节点部署服务点，确保每个节点均可在不超过其链路限制的范围内访问到至少一个服务点。求最少需要部署的服务点数。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数T（1≤T≤10）代表数据组数，每组测试数据描述如下： 第一行输入一个整数n（1≤n≤2×10^5），表示节点数。 第二行输入n个整数d[i]（0≤d[i]≤n），表示第i个节点的传输信号限制。 除此之外，保证单个测试文件的n之和不超过2×10^5。

输出描述

对于每组测试数据，输出一个整数，表示最少需要部署的服务点数。

样例输入

3

7

4 0 0 1 3 1 3

5

0 1 1 1 0

4

0 0 0 0

样例输出

3

3

4

样例说明： 对于第一组测试数据，节点覆盖区间分别为[1,5]，[2,2]，[3,3]，[3,5]，[2,8]，[5,7]，[4,10]，可选服务点位置为2，5，7，共3个。 对于第三组测试数据，d[i]=0时，所有区间为自身，需在每个节点设服务点，共4个。

参考题解

解题思路： 本题转换为经典的区间选点问题：给定一组区间，求最少需要多少个点，使得每个区间内都至少包含一个点。贪心策略：按区间右端点排序，每次选择当前区间右端点作为服务点（因为右端点能尽可能覆盖后续区间），然后跳过所有包含该点的区间。

C++：

#include <bits/stdc++.h>
using namespace std;

void solve