笔试时间：2025年8月17日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

小红书生态团队在评论审核中，需要对得分接近的评论判定观点相近，这一判断逻辑可以帮助团队灵活的调整评论区的观点统一性/观点多样性。 现在，将模型简化如下:给定长度为n的整数数组{a1,a2,…an}和一个整数 d。若|ai-aj|≤d，则称 ai与aj观点相近。一次操作可以选择一对元素，并将其同时从数组中删除(数组长度减少2)。 经过若干操作后，需要保证数组中不含任何观点相近的元素，且希望保留的元素数量尽可能多。请你计算，经过若干操作后，最终保留下来的最大元素数量。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤10^4)代表数据组数，每组测试数据描述如下: 第一行输入两个整数 n和 d(1≤n≤2*10^5;0≤d≤10^9),表示数组长度、观点相近的阈值。

第二行输入 n个整数 a1,a2,…an(0≤ai≤10^9)，表示数组元素。

除此之外，保证单个测试文件的n之和不超过2*10^5。

输出描述

对于每组测试数据，新起一行输出一个整数，表示最终保留下来的最大元素数量。

样例输入

2

5 2

1 2 4 7 9

4 0

1 1 2 5

样例输出

3

2

参考题解

我们需要从数组中移除偶数个元素（通过多次移除一对元素实现），使得剩余元素中没有任何两个元素的差值绝对值 ≤ d（即无“观点相近”元素）。 目标是最大化剩余元素的数量。 等价于：找到一个最大子集 S，其中 S 中任意两元素差 > d，且 n - |S| 为偶数（因为移除数量必须偶数）。该问题可建模为在一维数轴上的点集，禁止距离 ≤ d 的点共存。这是一个区间图（interval graph）的最大独立集问题。 由于数组排序后，冲突关系是连续的，可以用贪心高效求解最大独立集大小（无视奇偶约束下的最大剩余）。步骤如下：排序数组： 将数组 a 按升序排序，便于处理差值。计算无约束最大剩余（max_possible）：使用贪心：从左到右，尽可能多选元素，确保选中的元素间差 > d。初始化 last = -∞，计数 S = 0。遍历每个元素 x：如果 x > last + d，则选中它：S += 1，更新 last = x。这个 S 就是最大独立集大小（无奇偶约束下的最大剩余），因为在排序序列上，这种贪心能覆盖最优选择（类似于区间调度，避免了动态规划的 O(n) 空间/时间复杂，但这里时间 O(n log n) 因排序）。处理奇偶约束：移除数量 = n - S，必须为偶数。如果 (n - S) % 2 == 0，则直接返回 S（剩余与 n 同奇偶）。否则，返回 S - 1（多移除一个元素，使移除数量变为奇数 +1 = 偶数）。为什么 S - 1 可行？因为从最大独立集中移除一个元素，仍是合法独立集，且空集也合法（若 S=1 且需调整）。

C++：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        long long d;
        cin >> n >> d;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a.begin(), a.end());

        long long last = -(long long)1e10;
        int S = 0;
        for (long long x : a) {
            if (x > last + d) {
                S++;
                last = x;
            }
        }

        if ((n - S) % 2 == 0) cout << S << "\n";
        else cout << S - 1 << "\n";
    }
    return 0;
}

Java：

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            String[] parts = br.readLine().split(" ");
            int n = Integer.parseInt(parts[0]);
            long d = Long.parseLong(parts[1]);

            String[] arr = br.readLine().split(" ");
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(arr[i]);
            }
            Arrays.sort(a);

            long last = -(long)1e10;
            int S = 0;
            for (long x : a) {
                if (x > last + d) {
                    S++;
                    last = x;
                }
            }

            if ((n - S) % 2 == 0) {
                System.out.println(S);
            } else {
                System.out.println(S - 1);
            }
        }
    }
}

Python：

T = int(input())
for _ in range(T):
    n, d = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    S = 0
    last = - (10**10)
    for x in a:
        if x > last + d:
            S += 1
            last = x
    if (n - S) % 2 == 0:
        print(S)
    else:
        print(S - 1)

第二题

现在有n条 Plog 在首页上排成一列，队尾在下侧，队头在上侧。用长度为n的01串S=s1s2....sn,表示这条队列，其中:若 si=1，则第i条 Plog 属于美食;若 si=0，则第i条 Plog 属于旅行。一共会进行无限轮互评操作，每一轮:1.所有 Plog 的拥有者同时向队头(右侧)互评;2.互评只会影响每条 Plog 右侧的第一个异属性 Plog，如果右侧没有异属性 Plog，则不会产生互评操作;3.每轮所有互评动作并行计算，然后一次性将所有已经有评论的 Plog 移出，形成新队列再进入下一轮;同一条 Plog 在一轮可能收获多条评价。显然，无限进行下去，终究会出现不再有互评发生的情况。求整个过程中共有多少条 Plog 收获评价。

输入描述

第一行输入一个整数 n(1≤n≤10^5)，表示 Plog 数量。

第二行输入一个长度为 n 且只由字符'0'和'1'构成的字符串 s，表示 Plog 的属性分布。

其中其中si为从左向右第i条 Plog 的属性。

输出描述

输出一个整数，表示所有互评结束后共有多少条Plog 收获评价。

样例输入

10

1100010101

样例输出

8

参考题解

分块处理将连续的同种 Plog 视为一个“块”。 例如 1100010101 -> [2, 3, 1, 1, 1, 1, 1]。识别攻守方第一个块 a[0] 只攻击不被攻击，因此必定完全幸存。我们可将所有块分为两类：与 a[0] 同属性的A组（下标0, 2, 4...）和不同属性的B组（下标1, 3, 5...）。整个互评过程，可以看作是 A组 和 B组 的相互消耗。确定关键轮数 T