首页 > 试题广场 >

细胞增殖

[编程题]细胞增殖
  • 热度指数：872 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
生物学家小明正在研究一种特殊的细胞，这种细胞的增殖模式十分奇特。
他通过显微镜长期观察，记录下了 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 \le N \le 100000, 1 \le M \le 200000)

第二行包含 N 个整数，表示 N 条细胞种群数量的观测记录 C_i。数据保证按从小到大的顺序排列。
(1 \le C_i \le 10^9)

接下来 M 行，每行包含两个整数 B_j 和 S_j，代表一组假说的增殖基数和稳定基数。
(0 \le B_j, S_j \le 10^7)


输出描述:
输出共 M 行，每行对应一组假说的验证结果。

每行输出两个整数，以空格隔开，分别代表：
1.  符合该假说模式的总观测记录数。
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

备注:
本题由牛友@Charles 整理上传
算法知识视频讲解
添加回答
种好一棵树头像 种好一棵树
 利用数组存储 测量值为索引，值为测量值的重复值 最大的测量值即为数组的长度 - 1 
await readline();
    const records = (await readline()).split(" ").reduce((a, b) => {
        a[+b] = (a[+b] || 0) + 1;
        return a;
    }, []);

    const guesses = [];
    while ((line = await readline())) {
        const guess = line.split(" ").map(Number);
        guesses.push(guess);
    }
    const maxC = records.length - 1;
    const res = [];

    for (const [b, s] of guesses) {
        let count = 0;
        let max = 0;

        if (b === 0) {
            count = max = records[s] || 0;
        } else if (b === 1) {
            count = max = records[s + 1] || 0;
        } else {
            for (let i = 1; b ** i + s <= maxC; i++) {
                const current = records[b ** i + s] || 0;
                count += current;
                max = Math.max(max, current);
            }
        }

        res.push([count, max]);
    }

    for (const result of res) {
        console.log(result.join(" "));
    }


发表于 2026-01-05 03:25:25 回复(0)
C
久辰天头像 久辰天
能解出来，但是复杂度降不下去，所以只能过的一个例子

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

//符合判断函数,判断输入的c与b,s是否存在对应t值
int pd(int c,int b,int s){
    for(int t=1;;t++){       //t为正整数
        if(c == pow(b,t)+s){
            return t;     //返回当期t值（i就是t值）
        }else if(c < pow(b,t)+s){
            return 0;
        }
    }
}


int main() {
    int n,m;

    scanf("%d %d",&n,&m);  //输入 n,m，均为整数

    int* c=(int *)malloc(n * sizeof(int));  //定义观测记录c[i]-一维动态数组
    for(int i=0; i<n ;i++){
        scanf("%d",&c[i]);   //输入n个观测记录
    }

    int* b=(int *)malloc(m * sizeof(int));  //定义增殖基数b[i]-一维动态数组
    int* s=(int *)malloc(m * sizeof(int));  //定义稳定基数s[i]-一维动态数组
   
    for(int i=0; i<m ;i++){
        scanf("%d %d",&b[i],&s[i]);   //输入m组基数
    }    
   
    //循环遍历 每一组b,s 与 每一个c
    int* t=(int *)malloc(n*sizeof(int));  //用于确认每个t出现的次数
    for(int i=0;i<m;i++){
        //每个循环都初始化计数和值
        int count=0;   //记录每一个C有多少对应的t
        int max=0;     //记录最大t值是多少
        memset(t,0,n*sizeof(int));
        for(int j=0;j<n;j++){      //判断每一组b,s与c[j]是否存在t值
            int zqt=pd(c[j],b[i],s[i]);  //确认周期t的值
            if(zqt>0){        //存在t
                count++;                     //计数+1
                t[zqt]++;
                if(t[zqt]>max){        
                max=t[zqt];
                }
            }
        }
        printf("%d %d\n",count,max);
        free(t);

    }
    return 0;
}
发表于 2025-12-31 11:22:38 回复(0)
提交观点

问题信息

来自：2025年秋招-华为-...
难度：
2条回答 125浏览

热门推荐

相关试题

细胞增殖

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号