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

阅读本书更多章节>>>>

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

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

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

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

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

文章目录

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

01.K小姐的魔法卡牌

问题描述

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

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

输入格式

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

输出格式

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

样例输入

2

样例输出

1.0000000000

数据范围

1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105

题解

设对手场上有 n n n 个随从，我们可以将这 n n n 个随从从左到右编号为 1 , 2 , … , n 1, 2, \dots, n 1,2,…,n。

如果 n = 1 n = 1 n=1，则无论如何都无法达成"毁灭之光"的效果，概率为 0 0 0。

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

如果 n ≥ 3 n \geq 3 n≥3，则第一张"狙击射击"卡牌有 2 n \frac{2}{n} n2​ 的概率消灭最左边或最右边的随从，第二张"狙击射击"卡牌有 1 n − 1 \frac{1}{n-1} n−11​ 的概率消灭剩下的最左边或最右边的随从，因此达成"毁灭之光"效果的概率为 2 n ⋅ 1 n − 1 \frac{2}{n} \cdot \frac{1}{n-1} n2​⋅n−11​。

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

P = { 0 , n = 1 1 , n = 2 2 n ( n − 1 ) , n ≥ 3 P = \begin{cases} 0, & n = 1 \\ 1, & n = 2 \\ \frac{2}{n(n-1)}, & n \geq 3 \end{cases} P=⎩ ⎨ ⎧​0,1,n(n−1)2​,​n=1n=2n≥3​

参考代码

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 小姐有 n n n 个社交媒体账号,每个账号的粉丝数分别为 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​。最近,她即将发布一本新书,为了给新书做宣传,她打算在自己的一些社交账号上发布推广信息。

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

如果在拥有 a i a_i ai​ 个粉丝的账号上发布一次推广,将有 ⌊ a i 2 ⌋ \lfloor \frac{a_i}{2} \rfloor ⌊2ai​​⌋ 个粉丝看到推广信息;如果在该账号上发布多次推广,将有 a i a_i ai​ 个粉丝看到推广信息。

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

输入格式

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

第二行包含 n n n 个正整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​,表示每个社交账号的粉丝数量。

输出格式

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

样例输入

5 81 2 3 4 10

样例输出

2

数据范围

1 ≤ n , x ≤ 100 1 \leq n, x \leq 100 1≤n,x≤100 1 ≤ a i ≤ 100 1 \leq a_i \leq 100 1≤ai​≤100

题解

本题可以使用动态规划求解。设 d p [ i ] dp[i] dp[i] 表示使恰好 i i i 个粉丝看到推广信息时,最少需要选择的账号数量。初始时 d p [ 0 ] = 0 dp[0] = 0 dp[0]=0,其余 d p [ i ] = + ∞ dp[i] = +\infty dp[i]=+∞。

我们先考虑在每个账号上至多发布一次推广的情况。对于每个账号 i i i,我们可以选择发布推广或不发布推广。如果发布推广,将使 ⌊ a i 2 ⌋ \lfloor \frac{a_i}{2} \rfloor ⌊2ai​​⌋ 个粉丝看到推广信息,因此可以通过 d p [ j ] = min ⁡ ( d p [ j ] , d p [ j − ⌊ a i 2 ⌋ ] + 1 ) dp[j] = \min(dp[j], dp[j - \lfloor \frac{a_i}{2} \rfloor] + 1) dp[j]=min(dp[j],dp[j−⌊2ai​​⌋]+1) 进行转移。

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

如果最终 d p [ x ] = + ∞ dp[x] = +\infty dp[x]=+∞,则说明无法恰好使 x x x 个粉丝看到推广信息,输出 − 1 -1 −1。

时间复杂度为 O ( n 2 x ) O(n^2x) O(n2x),空间复杂度为 O ( x ) O(x) O(x)。

参考代码

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] //= 2print(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小姐是一位热爱分享知识的博主,她在自己的博客上发布了 n n n 篇文章。初始时,每篇文章的点赞数分别为 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​。

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

输入格式

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

第二行包含 n n n 个非负整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​,表示初始时每篇文章的点赞数。

输出格式

输出一个整数,表示所有文章总点赞数的期望对 1 0 9 + 7 10^9+7 109+7 取模后的结果。

样例输入

21 2

样例输出

6

数据范围

1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105 0 ≤ a i ≤ 1 0 9 0 \leq a_i \leq 10^9 0≤ai​≤109

题解

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

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

有 i n \frac{i}{n} ni​ 的概率使奇数点赞文章数减少 1 1 1;有 n − i n \frac{n - i}{n} nn−i​ 的概率使奇数点赞文章数加 1 1 1。

因此可以得到如下方程:

f [ i ] = 1 + i n ⋅ f [ i − 1 ] + n − i n ⋅ f [ i + 1 ] f[i] = 1 + \frac{i}{n} \cdot f[i-1] + \frac{n - i}{n} \cdot f[i + 1] f[i]=1+ni​⋅f[i−1]+nn−i​⋅f[i+1]

化简整理后有:

f [ i ] = n − i n + i n ⋅ ( f [ i − 1 ] + 1 + f [ i ] ) f[i] = \frac{n - i}{n} + \frac{i}{n} \cdot (f[i-1] + 1 + f[i]) f[i]=nn−i​+ni​⋅(f[i−1]+1+f[i])

进一步消元得：

f [ i ] = n n − i + i n − i ⋅ f [ i − 1 ] f[i] = \frac{n}{n - i} + \frac{i}{n - i} \cdot f[i - 1] f[i]=n−in​+n−ii​⋅f[i−1]

初始时 f [ 0 ] = 0 f[0]=0 f[0]=0。从 f [ 1 ] f[1] f[1] 开始递推计算即可得到 f [ i ] f[i] f[i] 的值。那么答案就等于初始总点赞数加上 f [ c n t ] f[cnt] f[cnt],其中 c n t cnt cnt 为初始时奇数点赞文章的数量。

时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( n ) O(n) O(n)。

参考代码

Python

MOD = 1000000007def qmi(a, b):    res = 1    while b > 0:        if b & 1:            res = res * a % MOD        b >>= 1        a = a * a % MOD    return resdef 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 -= 1if __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领取～

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/fengyun/2024-04-12/157349.html，文章来源：网络cs，作者：欧阳逸，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！