大厂真题 / 得物

得物 4.26 笔试真题

本场考试概述

考试时间：2026年4月26日 考试岗位：暑期实习 难度评级：中等

考点分析：

第一题：模拟 / 枚举（难度简单）
第二题：多重背包 DP（难度中等）
第三题：枚举 + 哈希（难度中等）

建议策略：

第一题是签到题，枚举底数即可，注意范围分析
第二题是经典多重背包，掌握二进制拆分模板即可
第三题需要将直线规范化表示，考察计算几何基础

第一题：特殊立方数

题目描述

如果一个正整数 $M$ 满足：$M$ 是 $d$ 位数，且 $M^3$ 的最后 $d$ 位恰好等于 $M$，则称 $M$ 为特殊立方数。

例如 $25^3 = 15625$，最后 2 位是 25，因此 25 是特殊立方数。

给定区间 $[a, b]$（$b \leq 10^9$），统计其中有多少个特殊立方数。

样例

输入

1 200

输出

思路分析

第一步：枚举底数而非枚举立方数

直接枚举 $[a, b]$ 内的每个数判断是否为特殊立方数？范围太大（$10^9$），不可行。

换个思路：既然特殊立方数 $K = M^3$，那我们枚举 $M$。由于 $K \leq 10^9$，所以 $M \leq 1000$。只需要枚举 1 到 1000，共 1000 个数。

第二步：逐个判断

对每个 $M$：计算 $K = M^3$，检查 $K$ 是否在 $[a, b]$ 范围内，再取 $K$ 的最后 $d$ 位（$d$ 是 $M$ 的位数）判断是否等于 $M$。

题解代码

import sys
input = sys.stdin.readline

a, b = map(int, input().split())

cnt = 0
for M in range(1, 1001):
    K = M ** 3
    if K > b:
        break
    if K < a:
        continue
    mod = 10 ** len(str(M))
    if K % mod == M:
        cnt += 1

print(cnt)

复杂度分析

时间复杂度：$O(\sqrt[3]{b})$，最多枚举 1000 个底数。 空间复杂度：$O(1)$。

第二题：挖掘宝石

题目描述

$N$ 种宝石，第 $i$ 种有 $x_i$ 颗，每颗价值 $y_i$、挖掘耗时 $z_i$ 分钟。总游戏时间 $T$ 分钟，求在时间内能获得的最大价值。

$N \leq 100$，$T \leq 1000$，$x_i \leq 100$。

样例

输入

输出

思路分析

第一步：识别多重背包

每种宝石数量有限（最多 $x_i$ 颗），这是经典的多重背包问题。$N \leq 100$，$T \leq 1000$，直接对每种宝石枚举取几颗再做 DP，复杂度 $O(N \times T \times \max(x_i))$ 可行但偏大。

第二步：二进制拆分优化

将第 $i$ 种宝石的 $x_i$ 颗拆成 $1, 2, 4, \dots$ 和余数这几组，每组视为一个独立物品。例如 7 颗拆为 $1 + 2 + 4$，三组可以组合出 $0 \sim 7$ 的任意取法。拆分后转化为 01 背包，复杂度降到 $O(N \times T \times \log(\max(x_i)))$。

第三步：逆序遍历

01 背包的关键：从大到小更新容量，保证每个虚拟物品在一轮中至多被选一次。

题解代码

import sys
input = sys.stdin.readline

N, T = map(int, input().split())
gems = []
for _ in range(N):
    x, y, z = map(int, input().split())
    gems.append((x, y, z))

f = [0] * (T + 1)
for cnt, val, cost in gems:
    k = 1
    remain = cnt
    while remain > 0:
        take = min(k, remain)
        w = take * cost
        v = take * val
        for j in range(T, w - 1, -1):
            f[j] = max(f[j], f[j - w] + v)
        remain -= take
        k *= 2

print(f[T])

复杂度分析

时间复杂度：$O(N \times T \times \log(\max(x_i)))$，每种宝石拆出 $O(\log x_i)$ 个虚拟物品，每个遍历 $T$ 个容量。 空间复杂度：$O(T)$，一维滚动 DP 数组。

第三题：计算好直线的数量

题目描述

二维平面上有 $n$ 个坐标两两不同的点，如果一条直线经过至少 $k$ 个点，则称为”好直线”。求平面中好直线的条数。

$n \leq 500$，$k \geq 2$。

样例

输入

输出

思路分析

第一步：枚举点对

$n \leq 500$，枚举所有 $\binom{n}{2}$ 个点对的复杂度为 $O(n^2) \approx 1.25 \times 10^5$，完全可行。

第二步：直线规范化

两个不同点对可能确定同一条直线。将每条直线用规范化的整数三元组 $(a, b, c)$ 唯一表示：

两点 $(x_1, y_1), (x_2, y_2)$ 确定直线 $ax + by + c = 0$，其中 $a = y_2 - y_1$，$b = x_1 - x_2$，$c = x_2 y_1 - x_1 y_2$。

除以三者绝对值的 GCD 消除倍数差异，再规定首个非零系数为正，得到唯一标识。

第三步：收集点集并统计

用哈希表将规范化三元组映射到点下标集合。枚举所有点对后，统计集合大小 $\geq k$ 的直线条数。

题解代码

import sys
from math import gcd
input = sys.stdin.readline

n, k = map(int, input().split())
points = []
for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y))

def canonical(x1, y1, x2, y2):
    a = y2 - y1
    b = x1 - x2
    c = x2 * y1 - x1 * y2
    g = gcd(gcd(abs(a), abs(b)), abs(c))
    if g != 0:
        a //= g
        b //= g
        c //= g
    if a < 0 or (a == 0 and b < 0):
        a, b, c = -a, -b, -c
    return (a, b, c)

line_points = {}
for i in range(n):
    for j in range(i + 1, n):
        key = canonical(points[i][0], points[i][1], points[j][0], points[j][1])
        if key not in line_points:
            line_points[key] = set()
        line_points[key].add(i)
        line_points[key].add(j)

ans = sum(1 for pts in line_points.values() if len(pts) >= k)
print(ans)

复杂度分析

时间复杂度：$O(n^2)$，枚举所有点对，每对的规范化和集合插入均为 $O(1)$（均摊）。 空间复杂度：$O(n^2)$，最多 $O(n^2)$ 条不同直线。

小结

第一题看似范围大（$b \leq 10^9$），但枚举底数 $M$ 而非立方数，范围缩小到 1000，是典型的”换方向枚举”技巧
第二题是多重背包模板题，二进制拆分将每种物品的 $x_i$ 颗拆成 $O(\log x_i)$ 组后转化为 01 背包
第三题的难点在于直线的规范化表示——除以 GCD 并规定符号，使同一条直线始终映射到相同的三元组

这篇文章有帮助吗？

| GitHub 留言