程序员基德

昨天 19:39 中国科学技术大学 C++ 发布于浙江

关注

【笔试刷题】小红书-2026.03.08-改编真题

✅ 春招备战指南 ✅

💡 学习建议：

先尝试独立解题
对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

小红书-2026.03.08

整体难度更贴近 Mid / Mid / High。第二题容易误入区间 DP，第三题最容易错在“只顾计数，不顾删除后的相对顺序”。

题目一：完美数字

这题先别急着对每个询问现算。因为上界只有 $10^9$ ，长度至少为 $3$ 的连续乘积其实没多少个，直接一次性预处理出来反而最稳。

难度：Mid

题目二：强迫症

这题看起来是在字符串上做区间翻转，真正决定答案的却不是区间本身，而是哪几对对称位置不一样。把这些位置压成左半边的若干连续块，答案就直接出来了。

难度：Mid

题目三：每日一题 Plus

这题表面是在删字符，第一步确实要先求“每个字母最多保留多少个”；但只做到这一步还不够，因为删除后的答案必须保持原串相对顺序。最终还要再做一遍按配额取子序列的字典序最小化。

难度：High

01. 完美数字

问题描述

本题是小红书 2025.08.27 第 1 题的原题。

用户的每一次点赞都代表着对内容的喜爱。小红定义一个正整数 $x$ 为完美数字，当且仅当同时满足以下两个条件：

可以将 $x$ 写作一个公差为 $1$ 且所有元素都是正整数的等差数列的乘积，例如， $6$ 可以写作 $1 \times 2 \times 3$ ；
上述等差数列的长度至少为 $3$ 。

现在小红薯接收到多次 $Plog$ 点赞数查询，每次给出一个正整数 $x$ ，请帮助小红薯判断该点赞数是否为完美数字。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1\le T\le 10^4)$ 代表数据组数。

接下来每组测试数据输入一行，一个整数 $x(1\le x\le 10^9)$ ，表示一次点赞数查询。

输出格式

对于每组测试数据，新起一行，如果点赞数是完美数字，输出 YES；否则，输出 NO。

样例输入

样例输出

YES
NO
YES

数据范围

$1 \le T \le 10^4$
$1 \le x \le 10^9$

题解

这题如果对每个询问都临时去试所有长度和起点，思路当然也能写，但完全没有必要。真正该抓住的是上界： $x \le 10^9$ ，满足条件的连续乘积总数其实非常少，完全可以一次性预处理出来。

设一个完美数字写成：

$x = k \times (k+1) \times (k+2) \times \cdots \times (k+\ell-1)$

其中 $k \ge 1$ ， $\ell \ge 3$ 。

先看长度上界。若 $\ell \ge 13$ ，最小乘积都已经是：

$1 \times 2 \times \cdots \times 13 = 6227020800 > 10^9$

所以合法长度只可能在 $3 \sim 12$ 之间，长度范围一下子就被压得很小了。

接着枚举每个长度 $\ell$ 的起点 $k$ 。因为乘积会随着 $k$ 的增大快速变大，所以一旦某个起点已经越界，后面的起点也不用再试。这样预处理下来，所有可能的完美数字只有很少一批，直接塞进哈希表即可。

之后每次询问只需要判断这个数在不在集合里，单次复杂度就是 $O(1)$ 。

复杂度方面：

预处理总规模很小，可以认为是常数级。
每次查询时间复杂度是 $O(1)$ 。

参考代码

Python

import sys

input = lambda: sys.stdin.readline().strip()

LIM = 10 ** 9
good = set()

for ln in range(3, 13):
    st = 1
    while True:
        prod = 1
        overflow = False
        for i in range(ln):
            value = st + i
            # 先判断这一步乘上去会不会越界。
            if prod > LIM // value:
                overflow = True
                break
            prod *= value
        # 一旦当前起点已经越界，后面的起点只会更大。
        if overflow:
            break
        good.add(prod)
        st += 1

t = int(input())
for _ in range(t):
    x = int(input())
    # 预处理后，每次询问只要查集合。
    print("YES" if x in good else "NO")

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

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

    const long long lim = 1000000000LL;
    unordered_set<long long> good;

    for (int len = 3; len <= 12; ++len) {
        for (long long st = 1; ; ++st) {
            long long prod = 1;
            bool overflow = false;

            for (int i = 0; i < len; ++i) {
                long long value = st + i;
                // 这一位乘上去会越界，就可以直接停。
                if (prod > lim / value) {
                    overflow = true;
                    break;
                }
                prod *= value;
            }

            // 当前起点已经越界，后面的起点也不用再试。
            if (overflow) {
                break;
            }
            good.insert(prod);
        }
    }

    int t;
    cin >> t;
    while (t--) {
        long long x;
        cin >> x;
        // 预处理后，单次查询就是 O(1) 查表。
        cout << (good.count(x) ? "YES" : "NO") << '\n';
    }
    return 0;
}

Java

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        final long lim = 1000000000L;
        Set<Long> good = new HashSet<>();

        for (int len = 3; len <= 12; len++) {
            for (long st = 1; ; st++) {
                long prod = 1;
                boolean overflow = false;

                for (int i = 0; i < len; i++) {
                    long value = st + i;
                    // 这一位乘上去会越界，就可以直接停。
                    if (prod > lim / value) {
                        overflow = true;
                        break;
                    }
                    prod *= value;
                }

                // 当前起点已经越界，后面的起点也不用再试。
                if (overflow) {
                    break;
                }
                good.add(prod);
            }
        }

        int t = Integer.parseInt(br.readLine());
        StringBuilder ans = new StringBuilder();
        while (t-- > 0) {
            long x = Long.parseLong(br.readLine());
            // 预处理后，单次查询就是查集合。
            ans.append(good.contains(x) ? "YES" : "NO").append('\n');
        }
        System.out.print(ans);
    }
}