小红书

小红书

2个小时：20道选择 + 3道编程

第一题

题目描述

小红书的第 i 篇文章有一个点赞数 ai 。小红认为，如果两篇不同的文章满足：点赞数通过位异或运算恰好得到 k ，那么这两篇文章是相似文章，即ai xor aj=k 。

现在小红收集到了 n 篇文章的点赞数，请帮助她计算出有多少对 (i,j) 是相似文章。

输入描述 第一行输入两个整数 \(n，k(1≤n≤2*105,0≤k≤109)\) 代表文章总数与相似文章判断值。

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

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

样例输入 4 5 1 1 3 4

样例输出 2

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

第二题：

题目描述：

小红书总部有一间神秘的魔法阅读室，它四四方方的，三边长为 x,y 和 z ：在三维空间内，我们可以假定它占据了 (0,0,0) 到 (x,y,z) 的空间。有魔法的地方在于，这里面是不存在重力的！这样一来，阅读桌就可以漂浮在任何位置。

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

输入描述 每个测试文件均包含多个测试点。第一行输入一个整数 T(1≤T≤1000) 代表测试数据组数，每组测试数据描述如下： 第一行输入四个整数 x,y,z 和 k(1≤x,y,z≤1000,1≤k≤109) ，分别代表魔法阅读室的三边长和魔法阅读桌的体积。 除此之外，保证所有的 x 之和，y 之和以及所有的 z 之和均不超过 1000 。

输出描述 对于每一个测试点，在一行上输出一个整数，代表不同的摆放方式数量。如果无法将魔法阅读桌放入阅读室，那么输出 0 。 样例输入 1 3 1 2 2 样例输出 4 提示 对于第一个测试点，已经在题目中加以解释。 对于第二个测试点，无法将魔法桌放入阅读室。

样例输入 2 3 1 2 2 1 2 3 7

样例输出 4 0

提示 对于第一个测试点，已经在题目中加以解释。

对于第二个测试点，无法将魔法桌放入阅读室。

第三题

题目描述：

小红有一棵由 n 个节点、 n - 1 条无向边构成的树，每条边的权值为 wi。

定义树上两个点 (u,v) 的权值为，从 u 到 v 的简单路径上，全部边权的异或和，特别的，当 u 和 v 为同一个点时，权值为 0 。

小红会提出 q 次询问，每次询问要求计算有多少个点到节点 u 的权值恰好为 k 。

树是指这样的一张图，其上的任意两个点都连通，且不存在环。

简单路径是指两个节点之间的一条路径，其不包含任何重复的节点。也就是说，在简单路径上，每个节点只能出现一次。

输入描述 第一行输入两个整数 n,q( 1≤n , q≤105)，分别表示节点总数和询问次数。

此后 n-1 行，第 i 行输入三个整数 ui , vi 和 wi（ 1≤ui , vi≤n ; ui≠vi ; 0≤w≤260 ）表示树上第 i 条边连接节点 ui 和 vi 且边权为 wi 。保证树联通，没有重边。

此后 q 行，每行输入两个整数 u,k(1≤u≤n,0≤k≤260)代表被询问的节点和限定。

输出描述 对于每一个询问，在一行上输出一个整数，代表到节点 u 的权值恰好为 k 的节点数量。

样例输入 3 2 1 2 2 1 3 3 1 0 2 2

样例输出 1 1

提示 对于第一个询问，只有 1 号结点到 1 号结点的路径异或和为 0。

对于第二个询问，只有 1 号结点到 2 号结点的路径异或和为 2。

第二次笔试

2小时：20道选择，3道编程

这一次的编程题难度比上一次低一些

第一题：动态规划

题目描述

n个人，每个人的战力为 a_i, 将这n个人分为红蓝两队，计算两个队伍 战斗力差值的最小绝对值。

每个队伍的战力等于该队伍所有人战力之和。

输入描述：

第一行输入一个整数 n(1≤n≤1000) 代表人员数量。 第二行输入 n 个整数 \(a_1,a_2,...,a_n(0≤a_i≤2*10^6)\) 代表每个人的战斗力

输出描述：

在一行上输出一个整数，代表双方战斗力差值的最小绝对值。

示例： 输入： 4 7 4 5 3 输出： 1

提示：

第一个人和第四个人是红对，战斗力之和为 10 ；第二个人和第三个人是蓝队，战斗力之和为 9，答案为∣10−9∣=1 。可以发现，没有其它方案比 1 更小。

输入样例2

输入 3 1999 1 1

输出 1997

样例2解释： 红蓝双方的人数可以不一样。

思路

1. 总和计算：首先计算所有战力的总和 S。
2. 动态规划数组：使用一个布尔型数组 dp，其中 dp[j] 表示是否能用一些人组成战力和为 j。
3. 填充动态规划数组：遍历每个人的战力，并更新 dp 数组。
4. 寻找最小差值：最后通过遍历 dp 数组找到可能的战力和，计算出最小的绝对差值。

实现代码

import java.util.Scanner;

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

        int n = scanner.nextInt(); // 人员数量
        int[] a = new int[n]; // 每个人的战斗力

        int totalSum = 0; // 所有战斗力的总和

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            totalSum += a[i];
        }

        boolean[] dp = new boolean[totalSum + 1]; // 动态规划数组
        dp[0] = true; // 和为0是始终可以的

        // 填充动态规划数组
        for (int power : a) {
            for (int j = totalSum; j >= power; j--) {
                dp[j] = dp[j] || dp[j - power];
            }
        }

        // 寻找最小绝对差值
        int minDiff = Integer.MAX_VALUE;
        for (int j = 0; j <= totalSum; j++) {
            if (dp[j]) {
                int team1Sum = j;
                int team2Sum = totalSum - j;
                minDiff = Math.min(minDiff, Math.abs(team1Sum - team2Sum));
            }
        }

        System.out.println(minDiff); // 输出最小绝对差值
    }
}

第二题：集合

题目描述：

一个收藏夹中有多个用户，每个用户都有一个MCN机构编号，每个MCN机构的编号唯一。 现在需要从 n 个收藏夹中选出两个，使得这两个收藏夹里用户的不同MCN机构数量恰好为 x 。

输入描述

每个测试文件均包含多组测试数据。 第一行输入一个整数 T(1≤T≤5) 代表数据组数，
每组测试数据描述如下： 
第一行输入两个整数 n 和 x(2≤n≤100,1≤x≤800) ，分别代表收藏夹的数量和想要的不同MCN机构的数量。 
此后 n 行，第 i 行的第一个整数 mi (1≤mi≤400) 代表这个收藏夹中的用户数量，此后 mi 个长度不超过 10 ，且由大小写字母和数字混合构成的字符串 s1,s2,…,smi 代表每一个用户的MCN机构编号。 

输出描述：

对于每一组测试数据，如果存在这样两个不同的收藏夹，使得里面的用户不同MCN机构数量之和恰好为 x ，你需要在第一行上输出 YES ，随后在第二行上输出两个不同的整数，代表收藏夹的编号；否则，直接输出 NO 。 
如果存在多个合法答案，请输出编号最小的那一对。具体的说，如果 (a,b) 和 (c,d) 均满足答案，但 a<c 或 a=b,b<d ，则输出 (a,b) 。 

样例输入

2 
3 4 
3 17 20 30 
4 17 20 30 23 
4 18 18 18 17 
2 2 
1 33Abc 
3 32Def 45G 19h 

样例输出：

YES 
1 2
NO 

提示： 
在第一组测试数据中，有三种不同的选法： 
选择 1 和 2 收藏夹，此时不同的用户MCN有四个： {17,20,23,30} ，满足要求； 
选择 1 和 3 收藏夹：{17,18,20,30} ，也满足要求； 
选择 2 和 3 收藏夹：{17,18,20,23,30} ，不满足要求。 
综上，该组测试数据有两个不同的答案，即 (1,2)和(1,3), 但是前者编号更小，因此输出1 2

解题思路

1. 输入解析：读取测试数据，包括收藏夹的数量和目标不同MCN机构的数量。
2. 集合操作：使用集合存储每个收藏夹的MCN机构编号，以便计算不同机构的数量。
3. 组合检查：对每一对收藏夹，计算它们合并后的MCN机构数量，并与目标数量进行比较。
4. 结果输出：如果找到符合条件的收藏夹组合，输出它们的编号；如果没有，输出NO。

实现代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 数据组数
        StringBuilder result = new StringBuilder();

        while (T-- > 0) {
            int n = scanner.nextInt(); // 收藏夹数量
            int x = scanner.nextInt(); // 目标不同MCN机构数量
            List<Set<String>> mcnCollections = new ArrayList<>();

            // 读取每个收藏夹的MCN机构编号
            for (int i = 0; i < n; i++) {
                int mi = scanner.nextInt(); // 用户数量
                Set<String> mcnSet = new HashSet<>();
                for (int j = 0; j < mi; j++) {
                    mcnSet.add(scanner.next()); // 添加MCN机构编号
                }
                mcnCollections.add(mcnSet);
            }

            boolean found = false;

            // 检查所有两两组合
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    // 合并两个收藏夹的MCN机构
                    Set<String> combinedMCN = new HashSet<>(mcnCollections.get(i));
                    combinedMCN.addAll(mcnCollections.get(j));

                    // 检查不同MCN机构的数量
                    if (combinedMCN.size() == x) {
                        result.append("YES\n").append((i + 1)).append(" ").append((j + 1)).append("\n");
                        found = true;
                        break;
                    }
                }
                if (found) {
                    break;
                }
            }

            if (!found) {
                result.append("NO\n");
            }
        }

        // 输出结果
        System.out.print(result.toString());
        scanner.close();
    }
}

代码解析

1. 输入处理：使用 Scanner 类读取输入数据。首先读取测试组数 T，然后对每组数据处理。
2. 集合存储：每个收藏夹的MCN机构编号存储在 HashSet 中，以便于合并和去重。
3. 双重循环：遍历每对收藏夹，合并它们的MCN机构集合，并检查合并后的大小是否等于目标值 x。
4. 结果存储：如果找到满足条件的收藏夹对，将结果添加到 StringBuilder 中。
5. 输出结果：最后输出所有结果。

复杂度分析

• 时间复杂度：O(n^2 * m)，其中 n 是收藏夹的数量，m 是每个收藏夹中用户的最大数量。
• 空间复杂度：O(m)，用于存储每个收藏夹的MCN机构集合。

第三题

题目描述：

n 个座位围成了一个圈，编号为 \(\{1,2,...,n,1,2,...\}\) ，m 位同学挑选了各自喜欢的位置坐下，保证全部同学都有位置坐，一个座位上至多只坐了一个人。

体育老师来给大家送礼物了，他想要找到这样一个位置，使得全部人到礼物的距离之和最小。具体来说，假设第 \(i\) 个同学坐在第 \(a_i\) 个座位上，那么礼物需要放在这样一个座位 \(j\) ，使得 \(\sum_{i=1}^m min \{|j-a_i|, |a_i+n-j|\}\) 最小，注意，礼物可以放在有人的座位上。

请直接输出这个座位的编号！

输入描述

第一行输入两个整数 \(n,m(1≤n≤10^9;1≤m≤2*10^5)\) 代表座位的数量和同学的数量。 第二行输入 m 个不同的整数 \(a_1,a_2,...,a_m (1≤a_i≤n)\) 代表每个同学所坐的座位编号。

输出描述

在一行上输出一个整数，代表礼物放置的座位编号。如果存在多个位置使得 \(\sum_{i=1}^m min \{|j-a_i|, |a_i+n-j|\}\) 最小，输出最小的位置编号即可。

样例1输入 4 3 1 4 3 样例1输出 4

提示：

样例1解释 如果放在第四个座位上，全部人到礼物的距离和为 1+0+1=2 。

样例2输入 8 3 1 4 5 输出 4

样例2解释： 礼物放在第四个座位上时，全部人到礼物的距离和为 3+0+1=4 ，可以证明这是最小的。

问题描述：

给定一个圆形座位环，有 nnn 个座位，编号为 111 到 nnn（编号循环，如 n+1n+1n+1 又回到 111）。有 mmm 个同学坐在他们喜欢的座位上，座位编号为 a1,a2,…,ama_1, a_2, \dots, a_ma1​,a2​,…,am​。体育老师想要选择一个座位放置礼物，使得所有同学到礼物的距离之和最小。距离定义为：

distance(ai,j)=min⁡(∣j−ai∣,n−∣j−ai∣)\text{distance}(a_i, j) = \min(|j - a_i|, n - |j - a_i|)distance(ai​,j)=min(∣j−ai​∣,n−∣j−ai​∣)

需要找到这样一个座位编号 jjj 使得总距离最小，如果有多个位置满足，输出编号最小的那个。

解题思路：

• 单峰函数特性：总距离函数关于位置 jjj 是单峰的（先下降后上升），因此可以使用 三分查找 来找到最小值。

• 实现步骤：

  1. 输入读取：读取 nnn、mmm 和同学的座位编号数组 aaa。
  2. 三分查找：在区间 [1,n] 上进行三分查找，找到使总距离最小的座位编号 j。
  3. 距离计算：对于给定的 j，计算所有同学到 j 的总距离。
  4. 结果输出：输出使总距离最小的最小座位编号。

  5. 注意事项：

  6. 整数处理：由于座位编号是整数，因此在三分查找时需要注意取整。

  7. 效率：由于 nnn 可达 10910^9109，需要保证算法的时间复杂度为 O(log⁡n)O(\log n)O(logn)。

Java代码实现：

import java.util.Scanner;

public class Main {
    static long n;
    static int m;
    static int[] a;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextLong();
        m = scanner.nextInt();
        a = new int[m];
        for (int i = 0; i < m; i++) {
            a[i] = scanner.nextInt();
        }

        long left = 1;
        long right = n;
        while (right - left > 3) {
            long mid1 = left + (right - left) / 3;
            long mid2 = right - (right - left) / 3;

            long s1 = totalDistance(mid1);
            long s2 = totalDistance(mid2);

            if (s1 < s2) {
                right = mid2 - 1;
            } else {
                left = mid1 + 1;
            }
        }

        long minTotal = Long.MAX_VALUE;
        long minPos = -1;
        for (long j = left; j <= right; j++) {
            long s = totalDistance(j);
            if (s < minTotal || (s == minTotal && j < minPos)) {
                minTotal = s;
                minPos = j;
            }
        }

        System.out.println(minPos);
    }

    // 计算所有同学到座位j的总距离
    static long totalDistance(long j) {
        long sum = 0;
        for (int a_i : a) {
            long d = Math.abs(a_i - j);
            sum += Math.min(d, n - d);
        }
        return sum;
    }
}

通过60%

方案二

优化思路：

在圆上，求解最小化所有点到某一点的距离之和的问题，可以通过以下方法解决：

• 展开圆：将圆展开为一条长度为 2n 的线段，这样我们可以将圆上的点映射到线性空间中。

• 滑动窗口：在展开的线性空间中，使用大小为 m 的滑动窗口来遍历所有可能的位置，并计算每个位置的总距离。

• 中位数优化：在一维线性空间中，最小化绝对距离之和的点是中位数。在我们的场景中，可以利用这一性质来优化计算。

具体步骤：

1. 输入读取和数据准备：

   • 读取 n、m 和同学的座位编号数组 a。
   • 将所有座位编号复制一份并加上 n，形成一个长度为 2m 的数组，用于模拟圆的展开。

   • 排序和前缀和计算：

   • 对展开后的数组进行排序。

   • 计算展开数组的前缀和，用于快速计算指定区间的距离之和。

   • 滑动窗口计算最小总距离：

   • 使用大小为 m 的滑动窗口在展开数组上滑动。

   • 对于每个窗口，计算窗口中所有点到窗口中位数位置的距离之和。
   • 记录最小的总距离和对应的座位编号。

   • 结果输出：

   • 输出使总距离最小的最小座位编号（取模 n 以回到原始座位编号范围）。

优化后的Java代码：

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

public class Main {
    static long n;
    static int m;
    static long[] positions;
    static long[] prefixSum;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextLong();
        m = scanner.nextInt();
        long[] a = new long[m];
        for (int i = 0; i < m; i++) {
            a[i] = scanner.nextLong();
        }

        // 展开圆并准备数据
        positions = new long[2 * m];
        for (int i = 0; i < m; i++) {
            positions[i] = a[i];
            positions[i + m] = a[i] + n;
        }

        Arrays.sort(positions);

        // 计算前缀和
        prefixSum = new long[2 * m];
        prefixSum[0] = positions[0];
        for (int i = 1; i < 2 * m; i++) {
            prefixSum[i] = prefixSum[i - 1] + positions[i];
        }

        long minTotalDistance = Long.MAX_VALUE;
        long bestPosition = -1;

        for (int i = 0; i <= m; i++) {
            int left = i;
            int right = i + m - 1;
            int medianIndex = (left + right) / 2;
            long medianPos = positions[medianIndex];

            // 左侧距离计算
            long leftCount = medianIndex - left;
            long leftSum = (medianIndex > 0 ? prefixSum[medianIndex - 1] : 0) - (left > 0 ? prefixSum[left - 1] : 0);
            long leftDistance = leftCount * medianPos - leftSum;

            // 右侧距离计算
            long rightCount = right - medianIndex;
            long rightSum = prefixSum[right] - prefixSum[medianIndex];
            long rightDistance = rightSum - rightCount * medianPos;

            long totalDistance = leftDistance + rightDistance;

            if (totalDistance < minTotalDistance || (totalDistance == minTotalDistance && (medianPos % n) < (bestPosition % n))) {
                minTotalDistance = totalDistance;
                bestPosition = medianPos % n;
                if (bestPosition == 0) {
                    bestPosition = n;
                }
            }
        }

        System.out.println(bestPosition);
    }
}