08-16 21:58 中国科学技术大学 C++ 发布于浙江
关注
0813小红书秋招笔试复盘三道题
#牛客AI配图神器##秋招笔面试记录#
------------------------------------
题目一：
题目大意：
给定 n (1 <= n <= 2e5) 张数字卡片，每张上有一个正整数 ai (1 <= ai <= 1e9, 不含0)。你需要将所有卡片上的数字拆分成独立的数位，然后将这些数位重新分配，组成 n 个新的数字，但每个新数字的位数必须与原来该位置的卡片上的数字位数相同。目标是让这 n 个新数字的总和最大。
解法思路：
这是一个贪心问题。要使总和最大，必须让越大的数位处在权重越高的位置上（例如，百位的权重大于十位）。因此，最优解法是：第一步，将所有数字拆分成单个的数位，放入一个列表。第二步，根据所有原始数字的位数，计算出所有位置的权重（如1, 10, 100等），放入另一个列表。第三步，将数位列表和权重列表都按降序排序。最后，将排序后的两个列表中的元素一一对应相乘再求和，即可得到最大的魔法能量值。
------------------------------------
题目二：
题目大意：
有一条含 n (1 <= n <= 1000) 颗珠宝的项链，每颗价值为 ai (1 <= ai <= 2e5)。对于每个数量 m (从1到n)，你需要从项链的某个前缀中（比如前 i 颗）选出 m 颗珠宝（保持原始相对顺序），并计算成本。成本 = (i - m) * k + (所选m颗珠宝的总价值)。你需要对每个 m，找出其最小的设计成本。(T 组数据, 1 <= T <= 50)
解法思路：
这是一个动态规划问题。可以定义 `dp[i][j]` 为“选择 i 颗珠宝，且最后一颗是原项链中的第 j 颗时，所选珠宝的最小价值总和”。状态转移方程为：`dp[i][j] = a[j] + min(dp[i-1][p])` 其中 `p < j`。这个转移可以通过维护前缀最小值来优化。得到DP表后，对于每个 m，最终成本是 `min(dp[m][i] + k * (i - m))` for `i >= m`。由于 `dp[i]` 只依赖于 `dp[i-1]`，可以使用滚动数组将空间复杂度优化到 O(n)。
------------------------------------
题目三：
题目大意：
给定一个长度为 n (1 <= n <= 2e5) 的非严格递增序列，其中部分数字缺失，用 0 表示 (0 <= ai <= 1e9)。已知序列的第一个和最后一个数不为0。你需要计算有多少种方法填补这些0，使得整个序列仍然保持非严格递增，结果对 1e9 + 7 取模。
解法思路：
这是组合数学问题。序列中已有的非零数字将整个序列分割成若干个独立的待填补区间。对于任意一个由非零数 L 和 R 包围的区间，假设中间有 c 个0，我们需要在这 c 个位置填上数，使得 L <= a_i <= ... <= a_j <= R。这等价于从 [L, R] 这个范围内的 `R - L + 1` 个数中，可重复地选出 c 个数，方案数符合多重组合（隔板法）模型。公式为 C((R-L)+c, c)。由于 R-L 的值可能很大，需要用 `(N*(N-1)*...*(N-c+1)) / c!` 的形式计算组合数，并使用费马小定理求乘法逆元来处理除法。最终答案是所有独立区间方案数的乘积。
具体的详细代码和题解可以戳我主页的文章查看
------------------------------------
题目一：
题目大意：
给定 n (1 <= n <= 2e5) 张数字卡片，每张上有一个正整数 ai (1 <= ai <= 1e9, 不含0)。你需要将所有卡片上的数字拆分成独立的数位，然后将这些数位重新分配，组成 n 个新的数字，但每个新数字的位数必须与原来该位置的卡片上的数字位数相同。目标是让这 n 个新数字的总和最大。
解法思路：
这是一个贪心问题。要使总和最大，必须让越大的数位处在权重越高的位置上（例如，百位的权重大于十位）。因此，最优解法是：第一步，将所有数字拆分成单个的数位，放入一个列表。第二步，根据所有原始数字的位数，计算出所有位置的权重（如1, 10, 100等），放入另一个列表。第三步，将数位列表和权重列表都按降序排序。最后，将排序后的两个列表中的元素一一对应相乘再求和，即可得到最大的魔法能量值。
------------------------------------
题目二：
题目大意：
有一条含 n (1 <= n <= 1000) 颗珠宝的项链，每颗价值为 ai (1 <= ai <= 2e5)。对于每个数量 m (从1到n)，你需要从项链的某个前缀中（比如前 i 颗）选出 m 颗珠宝（保持原始相对顺序），并计算成本。成本 = (i - m) * k + (所选m颗珠宝的总价值)。你需要对每个 m，找出其最小的设计成本。(T 组数据, 1 <= T <= 50)
解法思路：
这是一个动态规划问题。可以定义 `dp[i][j]` 为“选择 i 颗珠宝，且最后一颗是原项链中的第 j 颗时，所选珠宝的最小价值总和”。状态转移方程为：`dp[i][j] = a[j] + min(dp[i-1][p])` 其中 `p < j`。这个转移可以通过维护前缀最小值来优化。得到DP表后，对于每个 m，最终成本是 `min(dp[m][i] + k * (i - m))` for `i >= m`。由于 `dp[i]` 只依赖于 `dp[i-1]`，可以使用滚动数组将空间复杂度优化到 O(n)。
------------------------------------
题目三：
题目大意：
给定一个长度为 n (1 <= n <= 2e5) 的非严格递增序列，其中部分数字缺失，用 0 表示 (0 <= ai <= 1e9)。已知序列的第一个和最后一个数不为0。你需要计算有多少种方法填补这些0，使得整个序列仍然保持非严格递增，结果对 1e9 + 7 取模。
解法思路：
这是组合数学问题。序列中已有的非零数字将整个序列分割成若干个独立的待填补区间。对于任意一个由非零数 L 和 R 包围的区间，假设中间有 c 个0，我们需要在这 c 个位置填上数，使得 L <= a_i <= ... <= a_j <= R。这等价于从 [L, R] 这个范围内的 `R - L + 1` 个数中，可重复地选出 c 个数，方案数符合多重组合（隔板法）模型。公式为 C((R-L)+c, c)。由于 R-L 的值可能很大，需要用 `(N*(N-1)*...*(N-c+1)) / c!` 的形式计算组合数，并使用费马小定理求乘法逆元来处理除法。最终答案是所有独立区间方案数的乘积。
具体的详细代码和题解可以戳我主页的文章查看
全部评论
相关推荐
投递小红书等公司10个岗位 点赞 评论 收藏
分享
查看14道真题和解析