题解 | #细胞增殖#

题目链接

题目描述

生物学家小明正在研究一种特殊的细胞，其增殖遵循规律：种群数量 $A = x^k + y$ ，其中 $x$ 是增殖基数， $y$ 是稳定基数， $k$ 是增殖周期（ $k \ge 1$ ）。
给定 $N$ 条观测记录 $C_i$ ，以及 $M$ 组假说 $(B_j, S_j)$ （对应 $x$ 和 $y$ ），请计算：

总共有多少条记录符合该模式？
单个固定的 $k$ 值所能对应的最高重复观测次数（增殖峰值）是多少？

数据范围：

$1 \le N \le 100,000, 1 \le M \le 200,000$
$1 \le C_i \le 10^9$ （数据保证已按从小到大排列）
$0 \le B_j, S_j \le 10^7$

解题思路

由于观测记录 $C_i$ 最大为 $10^9$ ，且增殖基数 $x$ 和稳定基数 $y$ 均为非负数，我们可以针对不同的 $x$ 值进行处理：

统计频次：
使用 map<int, int> 统计 $C_i$ 中每个数值出现的次数。
分类讨论 $x$ ：
- $x = 0$ ：由于 $k \ge 1$ ，则 $x^k = 0$ ，规律简化为 $A = y$ 。只需查看记录中 $y$ 的频次。
- $x = 1$ ：对于任何 $k \ge 1$ ， $x^k = 1$ ，规律简化为 $A = 1 + y$ 。只需查看记录中 $1 + y$ 的频次。
- $x > 1$ ： $x^k$ 随 $k$ 的增加呈指数级增长。因为 $x \ge 2$ 且 $A \le 10^9$ ，则 $k$ 的最大取值约为 $30$ （ $2^{30} > 10^9$ ）。
  - 枚举 $k = 1, 2, 3, \dots$ ，计算 $target = x^k + y$ 。
  - 如果 $target > 10^9$ ，则停止枚举。
  - 在频次表中查询 $target$ ，累加总记录数，并维护最大频次作为增殖峰值。
复杂度分析：
- $x = 0$ 或 $x = 1$ 时，查询时间为 $\mathcal{O}(\log N)$ 。
- $x > 1$ 时，枚举次数极少（最多 30 次），查询总时间为 $\mathcal{O}(\log N \cdot \log (\max C_i))$ 。
- 总时间复杂度完全可以承受。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    map<int, int> cnts;
    for (int i = 0; i < n; ++i) {
        int c;
        cin >> c;
        cnts[c]++;
    }

    while (m--) {
        long long x, y;
        cin >> x >> y;
        long long total = 0;
        int peak = 0;
        
        if (x == 0) {
            if (y >= 1 && y <= 1000000000 && cnts.count((int)y)) {
                total = cnts[(int)y];
                peak = cnts[(int)y];
            }
        } else if (x == 1) {
            long long val = 1 + y;
            if (val <= 1000000000 && cnts.count((int)val)) {
                total = cnts[(int)val];
                peak = cnts[(int)val];
            }
        } else {
            long long curr = x;
            while (curr + y <= 1000000000) {
                int val = (int)(curr + y);
                if (cnts.count(val)) {
                    total += cnts[val];
                    peak = max(peak, cnts[val]);
                }
                // 检查下一步是否会溢出 long long 或超过最大记录值
                if (1000000000 / x < curr) break; 
                curr *= x;
            }
        }
        cout << total << " " << peak << "\n";
    }
    
    return 0;
}

import java.util.Scanner;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        HashMap<Integer, Integer> cnts = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int c = sc.nextInt();
            cnts.put(c, cnts.getOrDefault(c, 0) + 1);
        }
        
        for (int i = 0; i < m; i++) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            long total = 0;
            int peak = 0;
            
            if (x == 0) {
                int c = cnts.getOrDefault((int) y, 0);
                total = c;
                peak = c;
            } else if (x == 1) {
                int val = (int) (1 + y);
                int c = cnts.getOrDefault(val, 0);
                total = c;
                peak = c;
            } else {
                long curr = x;
                while (curr + y <= 1000000000) {
                    int val = (int) (curr + y);
                    if (cnts.containsKey(val)) {
                        int c = cnts.get(val);
                        total += c;
                        peak = Math.max(peak, c);
                    }
                    if (1000000000 / x < curr) break;
                    curr *= x;
                }
            }
            System.out.println(total + " " + peak);
        }
    }
}

def solve():
    n, m = map(int, input().split())
    
    records = list(map(int, input().split()))
    cnts = {}
    for val in records:
        cnts[val] = cnts.get(val, 0) + 1
            
    for _ in range(m):
        x, y = map(int, input().split())
        
        total = 0
        peak = 0
        
        if x == 0:
            c = cnts.get(y, 0)
            total, peak = c, c
        elif x == 1:
            c = cnts.get(1 + y, 0)
            total, peak = c, c
        else:
            curr = x
            while curr + y <= 1000000000:
                val = curr + y
                if val in cnts:
                    c = cnts[val]
                    total += c
                    if c > peak:
                        peak = c
                curr *= x
                    
        print(total,peak)

if __name__ == "__main__":
    solve()

算法及复杂度

算法：哈希表/映射统计频次 + 分类讨论。利用 $x \ge 2$ 时指数爆炸的特性，极大地减少了搜索空间。
时间复杂度： $\mathcal{O}(N \log N + M \cdot \log_x (\max C_i))$ 。其中 $\mathcal{O}(N \log N)$ 用于 C++ 的 std::map 构建，Java 和 Python 使用哈希表可优化至 $\mathcal{O}(N)$ 。
空间复杂度： $\mathcal{O}(N)$ 。用于存储观测记录的频次映射。