【小红书笔试题汇总】[全网首发]2024-03-29-小红书春招笔试题-三语言题解(CPP/Python/Java)

🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新小红书近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

本次的三题全是今年小红书春招前两场的原题~

文章目录

• 本次的三题全是今年小红书春招前两场的原题~
• • 01.K小姐的魔法卡牌
  • • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 数据范围
    • 题解
    • 参考代码
  • 02.K小姐的新书推广计划
  • • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 数据范围
    • 题解
    • 参考代码
  • 03.K小姐的博客点赞奇观
  • • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 数据范围
    • 题解
    • 参考代码
  • 写在最后
  • 📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取～

01.K小姐的魔法卡牌

问题描述

K小姐是一位魔法卡牌游戏的高手。在这个游戏中，每位玩家都有若干张卡牌，每张卡牌上都有一个魔法效果。其中有一张名为”毁灭之光”的卡牌，可以消灭对手场上最左边和最右边的随从。另一张卡牌名为”狙击射击”，可以随机消灭对手场上的一个随从。

现在，K小姐想知道，如果她使用两张”狙击射击”卡牌，恰好消灭了对手场上最左边和最右边的随从（即达到了一张”毁灭之光”卡牌的效果），这种情况发生的概率是多少。注意，两张”狙击射击”卡牌是按顺序使用的，因此不会消灭同一个随从。

输入格式

输入仅一行，包含一个正整数 ，表示对手场上随从的数量。

输出格式

输出仅一行，包含一个实数，表示K小姐达成”毁灭之光”效果的概率，结果四舍五入保留 位小数。

样例输入

2

样例输出

1.0000000000

数据范围

题解

设对手场上有 个随从，我们可以将这 个随从从左到右编号为 。

如果 ，则无论如何都无法达成”毁灭之光”的效果，概率为 。

如果 ，则两张”狙击射击”卡牌必然能达成”毁灭之光”的效果，概率为 。

如果 ，则第一张”狙击射击”卡牌有 的概率消灭最左边或最右边的随从，第二张”狙击射击”卡牌有 的概率消灭剩下的最左边或最右边的随从，因此达成”毁灭之光”效果的概率为 。

综上所述，K小姐达成”毁灭之光”效果的概率为：

参考代码

• Python

n = int(input())
if n <= 1:
    print(f"{0:.10f}")
elif n == 2:
    print(f"{1:.10f}")
else:
    res = 2 / (n * (n - 1))
    print(f"{res:.10f}")

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <= 1) {
            System.out.printf("%.10f\n", 0.0);
        } else if (n == 2) {
            System.out.printf("%.10f\n", 1.0);
        } else {
            double res = 2.0 / (n * (n - 1));
            System.out.printf("%.10f\n", res);
        }
    }
}

• Cpp

#include <cstdio>

int main() {
    int n;
    scanf("%d", &n);
    if (n <= 1) {
        printf("%.10f\n", 0.0);
    } else if (n == 2) {
        printf("%.10f\n", 1.0);
    } else {
        double res = 2.0 / (n * (n - 1));
        printf("%.10f\n", res);
    }
    return 0;
}

02.K小姐的新书推广计划

问题描述

著名作家 K 小姐有 个社交媒体账号,每个账号的粉丝数分别为 。最近,她即将发布一本新书,为了给新书做宣传,她打算在自己的一些社交账号上发布推广信息。

她希望通过精心安排宣传计划,使得恰好有 个粉丝看到新书推广信息。为此,她可以选择若干个账号进行推广。对于每个选中的账号,她可以选择发布一次推广,也可以选择发布多次推广,但最多只能有一个账号发布多次推广。

如果在拥有 个粉丝的账号上发布一次推广,将有 个粉丝看到推广信息;如果在该账号上发布多次推广,将有 个粉丝看到推广信息。

现在,K 小姐想知道,为了使恰好 个粉丝看到新书推广信息,她最少需要在多少个账号上发布推广信息?

输入格式

第一行包含两个正整数 和 ,分别表示 K 小姐拥有的社交账号数量以及目标粉丝数量。

第二行包含 个正整数 ,表示每个社交账号的粉丝数量。

输出格式

输出一个整数,表示 K 小姐最少需要在多少个账号上发布推广信息。如果无法恰好使 个粉丝看到推广信息,则输出 。

样例输入

5 8
1 2 3 4 10

样例输出

2

数据范围

题解

本题可以使用动态规划求解。设 表示使恰好 个粉丝看到推广信息时,最少需要选择的账号数量。初始时 ,其余 。

我们先考虑在每个账号上至多发布一次推广的情况。对于每个账号 ,我们可以选择发布推广或不发布推广。如果发布推广,将使 个粉丝看到推广信息,因此可以通过 进行转移。

接下来考虑在某一个账号上发布多次推广的情况。我们可以枚举发布多次推广的账号 ,然后将该账号的粉丝数量修改为 ,再次进行上述动态规划过程。最终的答案即为所有情况中的最小值。

如果最终 ,则说明无法恰好使 个粉丝看到推广信息,输出 。

时间复杂度为 ,空间复杂度为 。

参考代码

• Python

n, x = map(int, input().split())
a = list(map(int, input().split()))

def cal():
    dp = [float('inf')] * (x + 1)
    dp[0] = 0
    for i in t:
        for j in range(x, i - 1, -1):
            dp[j] = min(dp[j], dp[j - i] + 1)
    return dp[x]

t = [i // 2 for i in a]
res = cal()

for i in range(n):
    t[i] = a[i]
    res = min(res, cal())
    t[i] //= 2

print(res if res != float('inf') else -1)

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, x;
    static int[] a;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        x = sc.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            t[i] = a[i] / 2;
        }
        int res = cal(t);
        for (int i = 0; i < n; i++) {
            t[i] = a[i];
            res = Math.min(res, cal(t));
            t[i] /= 2;
        }
        System.out.println(res == INF ? -1 : res);
    }

    static int cal(int[] t) {
        int[] dp = new int[x + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int i : t) {
            for (int j = x; j >= i; j--) {
                dp[j] = Math.min(dp[j], dp[j - i] + 1);
            }
        }
        return dp[x];
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

int cal(vector<int> &t, int x) {
    vector<int> dp(x + 1, INF);
    dp[0] = 0;
    for (int i : t) {
        for (int j = x; j >= i; j--) {
            dp[j] = min(dp[j], dp[j - i] + 1);
        }
    }
    return dp[x];
}

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int &i : a) {
        cin >> i;
    }
    vector<int> t(n);
    for (int i = 0; i < n; i++) {
        t[i] = a[i] / 2;
    }
    int res = cal(t, x);
    for (int i = 0; i < n; i++) {
        t[i] = a[i];
        res = min(res, cal(t, x));
        t[i] /= 2;
    }
    cout << (res == INF ? -1 : res) << endl;
    return 0;
}

03.K小姐的博客点赞奇观

问题描述

K小姐是一位热爱分享知识的博主,她在自己的博客上发布了 篇文章。初始时,每篇文章的点赞数分别为 。

每过一段时间,就会有一位读者随机给一篇文章点赞,每篇文章被点赞的概率相等。K小姐很好奇,当第一次出现所有文章点赞数均为偶数时,所有文章的总点赞数的期望是多少呢?

输入格式

第一行包含一个正整数 ,表示 K 小姐博客中的文章数量。

第二行包含 个非负整数 ,表示初始时每篇文章的点赞数。

输出格式

输出一个整数,表示所有文章总点赞数的期望对 取模后的结果。

样例输入

2
1 2

样例输出

6

数据范围

题解

我们可以用期望线性性来求解本题。设 表示从当前状态到达第一次所有文章点赞数均为偶数时,还需要点赞的次数的期望。

假设当前有 篇文章的点赞数为奇数,每次点赞后:

• 有 的概率使奇数点赞文章数减少 ;
• 有 的概率使奇数点赞文章数加 。

因此可以得到如下方程:

化简整理后有:

进一步消元得：

初始时 。从 开始递推计算即可得到 的值。那么答案就等于初始总点赞数加上 ,其中 为初始时奇数点赞文章的数量。

时间复杂度 ,空间复杂度 。

参考代码

• Python

MOD = 1000000007

def qmi(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        b >>= 1
        a = a * a % MOD
    return res

def solve():
    n = int(input())
    
    m = 0
    s = 0
    a = list(map(int, input().split()))
    for x in a:
        s += x
        s %= MOD
        if x % 2 == 0:
            m += 1
    
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        dp[i] = (n * qmi(n - i, MOD - 2) % MOD + i * qmi(n - i, MOD - 2) % MOD * dp[i - 1] % MOD) % MOD
    
    ans = 0
    for i in range(m, n):
        ans = (ans + dp[i]) % MOD
    ans = (ans + s) % MOD
    
    print(ans)

def main():
    T = 1
    while T > 0:
        solve()
        T -= 1

if __name__ == "__main__":
    main()

• Java

import java.util.Scanner;

public class Main {
    static final int N = 1000010;
    static final int MOD = 1000000007;
    static long[] dp = new long[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int evenCount = 0;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int num = scanner.nextInt();
            sum += num;
            sum %= MOD;
            if (num % 2 == 0)
                evenCount++;
        }

        for (int i = 1; i <= n; i++)
            dp[i] = 0;
        dp[0] = 1;

        long result = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = (n * power(n - i, MOD - 2) % MOD + i * power(n - i, MOD - 2) % MOD * dp[i - 1] % MOD) % MOD;
        }

        for (int i = evenCount; i < n; i++)
            result = (result + dp[i]) % MOD;
        result = (result + sum) % MOD;

        System.out.println(result);
    }

    static long power(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1)
                res = res * a % MOD;
            b >>= 1;
            a = a * a % MOD;
        }
        return res;
    }
}

• Cpp

#include <iostream>
#include <vector>

using namespace std;

const int N = 1000010;
const int MOD = 1000000007;
vector<long long> dp(N);

long long qmi(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return res;
}

void solve() {
    int n;
    cin >> n;

    int evenCount = 0;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int num;
        cin >> num;
        sum += num;
        sum %= MOD;
        if (num % 2 == 0)
            evenCount++;
    }

    for (int i = 1; i <= n; i++)
        dp[i] = 0;
    dp[0] = 1;

    long long result = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = (n * qmi(n - i, MOD - 2) % MOD + i * qmi(n - i, MOD - 2) % MOD * dp[i - 1] % MOD) % MOD;
    }

    for (int i = evenCount; i < n; i++)
        result = (result + dp[i]) % MOD;
    result = (result + sum) % MOD;

    cout << result << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取～