小红书笔试小红书笔试题 0914

笔试时间：2024年09月14日秋招

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

第一题

题目：小红的文章匹配

小红书的第 i 篇文章有一个点赞数 ai 。小红认为，如果两篇不同的文章满足：点赞数通过位异或运算恰好得到 k ，那么这两篇文章是相似文章，即ai xor aj=k 。现在小红收集到了 n 篇文章的点赞数，请帮助她计算出有多少对 (i,j) 是相似文章。

输入描述

第一行输入两个整数n，k代表文章总数与相似文章判断值。

第二行输入 n 个整数 a1,a2,...,an(0≤ai≤) 代表每篇文章的点赞数。

输出描述

在一行上输出一个整数，代表相似文章的对数。

样例输入

4 5

1 1 3 4

样例输出

2

提示：可以发现，1 xor 4 = 5 ，那么文章一和四、文章二和四为两对相似文章。

参考题解

a xor b = c，则a xor c =b，对每篇文章i，找多少其他文章=a[i] xor k即可。

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

#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
map<int,int>c;
int a[200005];
long long ans=0;
int main()
{
    int n,k;
    cin>>n>>k;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i];
        c[a[i]]++;
    }
    for (int i=1; i<=n; i++)
        if (c[a[i]^k])
            ans+=c[a[i]^k]-(a[i]==(a[i]^k));
    cout<<ans/2<<endl;
    return 0;
}

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

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Map<Integer, Integer> c = new HashMap<>();
        long ans = 0;
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            c.put(a[i], c.getOrDefault(a[i], 0) + 1);
        }
        
        for (int i = 1; i <= n; i++) {
            int target = a[i] ^ k;
            if (c.containsKey(target)) {
                ans += c.get(target) - (a[i] == target ? 1 : 0);
            }
        }
        
        System.out.println(ans / 2);
        sc.close();
    }
}

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

def main():
    c = {}
    ans = 0

    n, k = map(int, input().split())
    a = [0] * (n + 1)

    for i in range(1, n + 1):
        a[i] = int(input())
        if a[i] in c:
            c[a[i]] += 1
        else:
            c[a[i]] = 1

    for i in range(1, n + 1):
        target = a[i] ^ k
        if target in c:
            ans += c[target] - (1 if a[i] == target else 0)

    print(ans // 2)

if __name__ == "__main__":
    main()

第二题

题目：魔法阅读室

小红书总部有一间神秘的魔法阅读室，它四四方方的，三边长为 x,y 和 z ：在三维空间内，我们可以假定它占据了 (0,0,0) 到 (x,y,z) 的空间。有魔法的地方在于，这里面是不存在重力的！这样一来，阅读桌就可以漂浮在任何位置。小红书的大家都非常的热爱阅读，特别是在魔法阅读室里！所以，为了搭配魔法阅读室，大家购买了一张魔法阅读桌：这个桌子的体积为 k ，边长可以为任何的正整数。你需要将魔法阅读桌放入魔法阅读室，使得阅读桌的各边平行于对应轴，并且每个角都位于整数坐标上。在所有可能的边长选取情况下，旋转桌子被视为一种方向，找到全部三种方向里摆放方式数量最多的那种情况的数量之和。例如下图中，在 312 的空间里有一张边长为 (2,1,1) 的阅读桌，左右方向有 4 种摆放方式，而竖直方向只有 3 种摆放方式，故我们选取左右方向计入答案。

输入描述

每个测试文件均包含多个测试点。

第一行输入一个整数 T(1≤T≤1000) 代表测试数据组数，每组测试数据描述如下：

第一行输入四个整数 x,y,z 和 k，分别代表魔法阅读室的三边长和魔法阅读桌的体积。

除此之外，保证所有的 x 之和，y 之和以及所有的 z 之和均不超过 1000 。

输出描述

对于每一个测试点，在一行上输出一个整数，代表不同的摆放方式数量。如果无法将魔法阅读桌放入阅读室，那么输出 0。

样例输入

2

3 1 2 2

1 2 3 7

样例输出

4

0

提示：

对于第一个测试点，已经在题目中加以解释。对于第二个测试点，无法将魔法桌放入阅读室。

参考题解

枚举边长i,j,t，保证i<j<t避免重复。不同方向就是把三条边顺序排列组合。边长(a,b,c)在(x,y,z)空间能放的方案数是(x-a+1) * (b-y+1) * (c-z+1)

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

#include<cstdio>
#include<iostream>
using namespace std;
int x,y,z,k;
int w(int a,int b,int c)
{
    if (a>x || b>y || c>z) return 0;
    return (x-a+1)*(y-b+1)*(z-c+1);
}
int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        cin>>x>>y>>z>>k;
        if (x>y) swap(x,y);
        if (y>z) swap(y,z);
        if (x>y) swap(x,y);
        long long ans=0;
        for (int i=1; i<=x; i++)
            for (int j=i; j<=y; j++)
            {
                int t=k/i/j;
                if (t<j) break;
                if (i*j*t!=k) continue;
                int s=max(w(t,i,j),w(t,j,i));
                int ss=max(w(i,t,j),w(j,t,i));
                int sss=max(w(i,j,t),w(j,i,t));
                ans+=max(s,max(ss,sss));
            }
        cout<<ans<<endl;
    }
    return 0;
}

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