华为 · 哈希 · 算法编程题
华为 哈希 N ≤ 1e5 时限 5 秒 / 512 MB

题目描述

生物学家小明正在研究一种特殊的细胞，这种细胞的增殖模式十分奇特。
他通过显微镜长期观察，记录下了 N 个不同时间点的细胞种群数量。
小明提出了一个理论模型：他认为这些细胞的增殖可能遵循一种规律，即种群数量会等于某个“增殖基数” B 的 t 次方与一个“稳定基数” S 的和，其中 t 代表增殖周期（一个正整数）。完整的公式为： C = B^t + S 。
现在，小明整理出了 M 组假说，每组假说包含一个增殖基数 B_j 和一个稳定基数 S_j 。
他希望您能帮他验证，对于每一组假说 (B_j, S_j) ，在他的 N 条观测记录中：
1. 总共有多少条记录符合 C_i = B_j^t + S_j 的模式（ t 可以取任意正整数）？
2. 在所有符合该模式的记录中，单个增殖周期（即固定的 t 值）所能对应的最高重复观测次数是多少？我们称之为“增殖峰值”。

输入输出

输入描述
输入第一行包含两个正整数 N 和 M ，分别代表观测记录的数量和假说的数量。
(1 ≤ N ≤ 100000, 1 ≤ M ≤ 200000)
第二行包含 N 个整数，表示 N 条细胞种群数量的观测记录 C_i 。数据保证按从小到大的顺序排列。
(1 ≤ C_i ≤ 10^9)
接下来 M 行，每行包含两个整数 B_j 和 S_j ，代表一组假说的增殖基数和稳定基数。
(0 ≤ B_j, S_j ≤ 10^7)
输出描述
输出共 M 行，每行对应一组假说的验证结果。
每行输出两个整数，以空格隔开，分别代表：
1. 符合该假说模式的总观测记录数。
2. 该假说模式下的增殖峰值。

样例共 2 组

样例 1
输入
4 2
45 78 90 429981774
12 78
9 42561285
输出
2 1
1 1
样例 2
输入
11 3
2 3 4 5 5 6 7 7 9 16 17
2 0
2 1
0 7
输出
3 1
5 2
2 2

算法解析依据充分

考点：哈希

数据规模 N ≤ 1e5 ｜ 限制 5 秒 / 512MB ｜ 标准输入输出

题目画像

  • 数据规模：M ≤ 200000，N ≤ 1e5
  • 元素值域：C_i ≤ 1e9，B_j ≤ 10000000，S_j ≤ 10000000（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：5 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：哈希

本题切入点

把 N 个观测值放进哈希表（已排序也可二分）；对每组 (B,S) 从 t=1 枚举 Bᵗ+S（B≥2 时增长极快，几十次即超 1e9），命中即累计并记录同一 t 的最大重复次数，B=0/1 需特判。

用哈希表把「查找/计数」的开销降到 O(1) 均摊。

思路框架（哈希 通法 · 非本题专属）

  1. 一次遍历，把元素作为 key、出现次数/首次位置作为 value 存进哈希表。
  2. 第二次遍历（或边扫边查）拿到需要的信息。
  3. 注意哈希无序：需要按原顺序输出时要额外记录顺序。

实现要点：Python 用 dict / collections.Counter / defaultdict；C++ 用 unordered_map。

复杂度：时间 O(n) 均摊 ｜ 空间 O(n)

该范式的通法易错点

  • 遍历哈希表时依赖了不存在的顺序。
  • 多次查询时每次都重新统计。

对照本题

  • 数据规模 N ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：4 2 / 45 78 90 429981774 / 12 78 / 9 42561285
  • 输出：2 1 / 1 1

样例 2

  • 输入：11 3 / 2 3 4 5 5 6 7 7 9 16 17 / 2 0 / 2 1 / 0 7
  • 输出：3 1 / 5 2 / 2 2

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-12月17号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解