小红书笔试 20250824
笔试时间：2025年8月24日
往年笔试合集：
第一题：行为权重
小红是小红书的用户行为分析师。平台将每次用户行为映射为一个正整数权重序列 [a₁, a₂, …, aₙ]，以便后续关联推荐时关键 “红色” 行为。
为了保证标记的行为具有足够的共性，必须选出的所有 “红色” 行为权重的最大公约数大于 1；同时，为了避免相邻生冗余，所选下标不得相邻。
现给定用户的一次行为序列，求最多可以染成红色的行为数量。
【名词解释】
最大公约数：指一组整数共有约数中最大的一个。例如，12、18 和 30 的公约数有 1,2,3,6，其中最大的约数是 6，因此 gcd (12,18,30)=6。
输入描述
在一行上输入一个整数 n（1 ≤ n ≤ 10⁵），表示行为序列长度。
在第二行输入 n 个整数 a₁, a₂, …, aₙ（1 ≤ aᵢ ≤ 100），表示每次行为的权重值。
输出描述
在一行上输出一个整数，表示最多可染红的行为数量。
样例输入
5 1 2 3 2 6
样例输出
2
在这个样例中，可将下标 2 与 4 对应的权重染红，它们的最大公约数为 2，且不相邻，故答案为 2。
参考题解
直接找出满足所有条件的最佳组合很复杂。我们可以反过来想：既然所有选中的数必须有一个大于1的最大公约数（GCD），那么它们必然都是某个整数 d (d>1) 的倍数。由于题目给的数字最大不超过100，这个公约数 d 也肯定在2到100之间。因此，我们可以把复杂问题分解成近百个简单问题：第一步：锁定公约数 d我们假设最终选出的所有“红色”行为，它们的公约数就是 d。我们依次让 d 等于 2、3、4、...、100，分别计算每种情况下的最优解。第二步：解决简化后的问题 当公约数 d 固定后，问题就变成了：在原数组中，最多能选出多少个“不相邻”的、且是 d 的倍数的数？第三步：动态规划（“打家劫舍”模型）这个简化后的问题是一个非常经典的动态规划模型，可以类比为“打家劫舍”（不能偷相邻的屋子）。 我们从头到尾遍历数组，对每个位置 i 的数 a[i]，我们做决策：不选 a[i]：最大数量等于到位置 i-1 的最大数量。选 a[i]：因为不能和相邻的 a[i-1] 一起选，所以最大数量是 1 (代表 a[i] 自己) + 到位置 i-2 的最大数量。我们在这两个选择中取一个更大的结果。如果 a[i] 不是 d 的倍数：我们肯定不能选它，所以到位置 i 为止的最大数量，就等于到位置 i-1 的最大数量。如果 a[i] 是 d 的倍数：我们有两个选择：第四步：取全局最优解我们对每一个 d（从2到100）都执行一次第三步的动态规划，会得到近百个结果。在所有这些结果中，取那个最大的数，就是题目的最终答案。
C++：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0;
for (int d = 2; d <= 100; ++d) {
int prev1 = 0, prev2 = 0;
for (int i = 0; i < n; ++i) {
int temp1 = prev2;
int temp2 = 0;
if (a[i] % d == 0) {
temp2 = 1 + prev1;
}
int current = max(temp1, temp2);
prev1 = prev2;
prev2 = current;
}
if (prev2 > ans) {
ans = prev2;
}
}
cout << ans << endl;
return 0;
}
Java：
import java.util.Scanner;
public class MaxDivisibleSubsequence {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = scanner.nextInt();
}
int ans = 0;
for (int d = 2; d <= 100; ++d) {
int prev1 = 0, prev2 = 0;
for (int i = 0; i < n; ++i) {
int temp1 = prev2;
int temp2 = 0;
if (a[i] % d == 0) {
temp2 = 1 + prev1;
}
int current = Math.max(temp1, temp2);
prev1 = prev2;
prev2 = current;
}
if (prev2 > ans) {
ans = prev2;
}
}
System.out.println(ans);
scanner.close();
}
}
Python：
import sys def main(): n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) ans = 0 for d in range(2, 101): prev1, prev2 = 0, 0 for i in range(n): temp1 = prev2 temp2 = 0 if a[i] % d == 0: temp2 = 1 + prev1 current = max(temp1, temp2) prev1, prev2 = prev2, current if prev2 > ans: ans = prev2 print(ans) if __name__ == "__main__": main()
第二题：潜在同好
在小红书平台的社交推荐项目中，产品团队希望基于用户的日常行为习惯分数，挖掘潜在的 “同好” 关系。系统简化如下，数据库中有 n 个用户的日常行为习惯分数，第 i 个用户的分数使用 aᵢ表示。记第 i 个用户和第 j 个用户构成 “同好” 关系，当且仅当 aᵢ能被 aⱼ整除，或者 aⱼ能被 aᵢ整除。接下来将进行 m 次查询，每次给定一个额外的用户行为分数 x，请统计在数据库中，有多少不同的人能与这个人构成 “同好” 关系。
输入描述
第一行输入两个整数 n,m（1 ≤ n,m ≤ 5×10⁵），表示数据库中用户数量、查询次数。
第二行输入 n 个整数 a₁,a₂,…,aₙ（1 ≤ aᵢ ≤ 5×10⁵），表示数据库中的用户日常行为习惯分数。
接下来 m 行，每行输入一个整数 x（1 ≤ x ≤ 5×10⁵），表示一个额外的用户行为习惯分数。
输出描述
对于每次查询，新起一行，输出一个整数，表示数据库中能与 x 构成 “同好” 关系的用户数量。
样例输入
5 3
1 2 2 5 6
4
2
1
样例输出
3
4
5
参考题解
预处理 + 容斥原理。核心公式对于每次查询 x，与其构成“同好”关系的人数等于： (数据库中 x 的倍数个数) + (数据库中 x 的因数个数) - (数据库中 x 自身的个数) 减去 x 自身的个数是因为它在“倍数”和“因数”中被计算了两次。优化方法直接对每次查询计算上述数量会超时。由于查询次数多而数值范围固定，我们采用“空间换时间”的策略，进行预处理。预处理步骤我们使用三个数组，提前算好所有可能用到的信息：这两个关键数组 (multiples_count 和 divisors_sum) 都可以通过类似筛法的循环在 O(MAXlogMAX) 的高效时间内计算完成。counts[k]: 统计分数 k 的出现次数。multiples_count[k]: 预计算数据库中 k 的倍数总共有多少个。divisors_sum[k]: 预计算数据库中 k 的因数总共有多少个。快速查询 预处理完成后，对于任何查询 x，我们只需从预处理好的数组中直接取值，代入第一步的核心公式，即可在 O(1) 时间内得出答案。
C++：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int M = 500001;
vector<int> f1(int n, vector<int>& arr, int sz) {
vector<int> cnt(sz + 1, 0);
for (int v : arr) {
if (v <= sz) {
cnt[v]++;
}
}
return cnt;
}
vector<int> f2(vector<int>& cnt, int sz) {
vector<int> mc(sz + 1, 0);
for (int i = 1; i <= sz; ++i) {
int t = i;
while (t <= sz) {
mc[i] += cnt[t];
t += i;
}
}
return mc;
}
vector<int> f3(vector<int>& cnt, int sz) {
vector<int> ds(sz + 1, 0);
for (int i = 1; i <= sz; ++i) {
if (cnt[i] > 0) {
int j = i;
while (j <= sz) {
ds[j] += cnt[i];
j += i;
}
}
}
return ds;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n_val, m_val;
cin >> n_val >> m_val;
vector<int> nums(n_val);
for (int i = 0; i < n_val; ++i) {
cin >> nums[i];
}
vector<int> cnt_arr = f1(n_val, nums, M);
vector<int> mc_arr = f2(cnt_arr, M);
vector<int> ds_arr = f3(cnt_arr, M);
vector<string> output;
for (int i = 0; i < m_val; ++i) {
int q;
cin >> q;
if (q >= M) {
output.push_back("0\n");
} else {
int result = mc_arr[q] + ds_arr[q] - cnt_arr[q];
output.push_back(to_string(result) + "\n");
}
}
for (const string& line : output) {
cout << line;
}
return 0;
}
Java：
import java.io.*;
import java.util.*;
public class ArrayAnalyzer {
private static final int M = 500001;
public static int[] f1(int n, int[] arr, int sz) {
int[] cnt = new int[sz + 1];
for (int v : arr) {
if (v <= sz) {
cnt[v]++;
}
}
return cnt;
}
public static int[] f2(int[] cnt, int sz) {
int[] mc = new int[sz + 1];
for (int i = 1; i <= sz; i++) {
int t = i;
while (t <= sz) {
mc[i] += cnt[t];
t += i;
}
}
return mc;
}
public static int[] f3(i
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
查看15道真题和解析