金山笔试 wps笔试 0918

笔试时间:2024年09月18日 秋招

历史笔试传送门:2023秋招笔试合集

第一题

题目

小强是一个的农场主,农场里有n头牛,每头牛有着独一无二的体重,每一头牛的颜色可能是m种颜色其中的一种,小强带了一些牛(可能为0个)出来吃草。你需要回答出小强带出来的牛的组合—共有多少种可能?注意:因为每—头牛有自己的体重(没有两头牛体重相等),所以如果四头牛体重分别是1,2,3,4,颜色分別是y1,y1,y4,y4和另外一种方案:四头牛体重分别是1,2,3,4,颜色分别是y1,y4,y4,y1即使两个方案的颜色的种类对应的数量是相同的,但是因为颜色对应的体重不同所以是两个不同的方案。由于方案数可能很大,请对 1e9 + 7 取模。

输入描述

两个正整数n和m。

1 <= n <= 10^9, 1 <= m <= 10^9

输出描述

一个整数代表答案。

样例输入

3 2

样例输出

27

说明:

小强可能带0头牛出来,只有1种方案。

小强可能带1头牛出来,有3*2种方案(带出的是3头牛中的任意一个,这头牛的颜色可能为2种颜色之一)。

小强可能带2头牛出来,有3*2^2种方案。

小强可能带3头牛出来,有1*2^3种方案。

一共有1+6+12+8=27种方案。

参考题解

模拟计算,((1 + m)^n \mod (10^9 + 7))

C++:[此代码未进行大量数据的测试,仅供参考]

#include <iostream>

using namespace std;

const long long MOD = 1000000007;

int main() {
    long long n, m;
    cin >> n >> m;

    long long result = 1;
    long long base = (m + 1) % MOD;

    // 计算 (1 + m)^n % MOD
    while (n > 0) {
        if (n & 1) {
            result = (result * base) % MOD; // 乘以基数
        }
        base = (base * base) % MOD; // 基数平方
        n >>= 1; // n 右移一位
    }

    cout << result << endl;
    return 0;
}

Java:[此代码未进行大量数据的测试,仅供参考]

import java.util.Scanner;

public class CowCombinations {
    private static final long MOD = 1000000007L;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong(); 
        long m = scanner.nextLong(); 
        scanner.close();

        long result = 1;
        long base = (m + 1) % MOD;

        // 计算 (1 + m)^n % MOD
        while (n > 0) {
            if ((n & 1) == 1) {
                result = (result * base) % MOD; // 乘以基数
            }
            base = (base * base) % MOD; // 基数平方
            n >>= 1; // n 右移一位
        }

        System.out.println(result);
    }
}

Python:[此代码未进行大量数据的测试,仅供参考]

MOD = 1000000007

def main():
    n = int(input())  # 读取n
    m = int(input())  # 读取m

    result = 1
    base = (m + 1) % MOD

    # 计算 (1 + m)^n % MOD
    while n > 0:
        if n & 1:
            result = (result * base) % MOD  # 乘以基数
        base = (base * base) % MOD  # 基数平方
        n >>= 1  # n 右移一位

    print(result)

if __name__ == "__main__":
    main()

第二题

题目

牛牛有n种糖果,每种糖果都有足够多,现在牛牛想用这些糖果组成一些糖果盒。每个糖果盒内放m个糖果。对于一个糖果盒,牛牛希望第i种糖果的数量不能少于l_i颗也不能多于r_i颗。满足条件的糖果盒组成方案可能会有很多,牛牛希望你帮他计算一共有多少种糖果盒的拼凑方案。对于两种方案,当有任意一种糖果个数不同,就视为两种不同方案。

输入描述

输入包括n+1行。

第一行包括两个正整数(1 <=n <= 20,1 <= m <= 100),表示糖果的种数和一盒糖果盒的糖果个数。

接下来的n行,每行两个整数l_i, r_i(0 <= l_i <= r_i<= 10),表示第i种糖果的数量限制上下限。

输出描述

输出一个整数,表示满足限定条件的方案数。保证答案在64位整数范围内。

样例输入

3 5

0 3

0 3

0 3

样例输出

12

参考题解

动态规划。定义状态:定义 dp[i][j] 表示前 i 种糖果中,可以凑成 j 个糖果盒的方案数。初始化:初始状态 dp[0][0] = 1,表示使用 0 种糖果凑成 0 个糖果盒只有 1 种方案,即不放糖果。其他 dp[0][j](j > 0)应初始化为 0,因为用 0 种糖果无法凑成正数量的糖果盒。状态转移:dp[i][j] += dp[i-1][j-k]:如果用当前糖果的数量为 k,那前 i-1 种糖果凑成 j-k 个糖果盒的方案数就需要被加到 dp[i][j] 中。表示如果用第 i 种糖果放 k 颗糖果,则剩下的 j-k 个糖果盒的拼凑方案数是由前 i-1 种糖果决定的。对于第 i 种糖果,有 l[i-1] 到 r[i-1] 的数量限制。如果当前糖果的数量限制为 k,可以尝试将其放入糖果盒中,更新 dp[i][j]:最终 dp[n][m] 就是答案。

C++:[此代码未进行大量数据的测试,仅供参考]

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
    }

    // 动态规划数组,dp[i][j] 表示前 i 种糖果凑成 j 个糖果盒的方案数
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));

    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {  // 遍历每一种糖果
        for (int j = 0; j <= m; j++) {  // 遍历糖果盒内的糖果数量
            for (int k = l[i - 1]; k <= r[i - 1]; k++) {  // 当前糖果的可选数量
                if (j >= k) {
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}

Java:[此代码未进行大量数据的测试,仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); 
        int m = sc.nextInt();

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2024 BAT笔试合集 文章被收录于专栏

持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。

全部评论
请问笔试要提前准备第二机位嘛
点赞 回复 分享
发布于 2024-09-29 18:27 陕西

相关推荐

一天面两场,太久没看八股了,真的一点状态都没了。问题大多记不住了,可能是昨晚焦虑地没睡好,说点感觉回答的不够好的吧。饿了么客户端系统中出现了比较多的异常应该怎么处理?日志定位的话,你会自己做日志吗?有什么要注意的点?异常用什么方式捕获?你说全局异常捕获的Handler,需要注意什么吗?虚拟内存段页式有什么区别?优缺点?你的项目中有实际发生过死锁吗?你是如何解决的?手撕:旋转数组,无法运行,plain&nbsp;text格式。阿里云(反问介绍是安全部门)Go语言:如何用Go实现类似python那种,可以不指定几个参数?比如说参数abc用户只传ab。明确告诉你,go不支持多态,还有哪些方法?Go中有指针,哪些东西要依赖指针传递?cmd.Flag为什么用指针?如果一个interface()作为参数处理过吗?你使用SDK时,如何向一个SDK的结构体注册一个函数?不能修改SDK。操作系统:协程线程的区别?协程线程的优缺点?为什么要用多线程不用多进程?(延伸了几个问题)除了切换开销,你认为还有哪些其他的原因吗?你说需要进入内核态,那系统调用的过程是怎样的?用户态切换内核态的第一件事是发送中断信号吗?你说线程可以共享内存,进程间的通信方式了解过吗?那如果进程也共享内存了,和线程的共享内存有什么区别?计算机网络:RPC用自定义协议替代HTTP协议只是为了节省开销吗?(开始深入)HTTP由哪些部分组成?用其他的传输协议你考虑过吗?为什么不用呢?随便回答了HTTP支持底层的TCP,你还知道哪些支持TCP的协议吗?HTTP和HTTPS的区别?你知道哪些加密算法?椭圆曲线你也知道?那你能介绍一下吗?CRC呢?快结束面试又追问了一个HTTP相关的问题,不记得了,管他呢。面试官在笑,问我确定吗,我也想笑,但还是憋住了。菜,就多练。
查看21道真题和解析
点赞 评论 收藏
分享
投递小天才等公司6个岗位
点赞 评论 收藏
分享
评论
1
6
分享

创作者周榜

更多
牛客网
牛客企业服务