小红书-2026.03.08

#刷题链接🔗: bishipass.com

题目一：完美数字

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

难度：Mid

题目二：强迫症

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

难度：Mid

题目三：每日一题 Plus

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

难度：High

01. 完美数字

问题描述

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

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

• >

  可以将  写作一个公差为  且所有元素都是正整数的等差数列的乘积，例如， 可以写作 ；

• >

  上述等差数列的长度至少为 。

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

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数。

接下来每组测试数据输入一行，一个整数 ，表示一次点赞数查询。

输出格式

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

样例输入

36224

样例输出

YESNOYES

数据范围

• >
• >

题解

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

设一个完美数字写成：

其中 ，。

先看长度上界。若 ，最小乘积都已经是：

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

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

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

复杂度方面：

• >

  预处理总规模很小，可以认为是常数级。

• >

  每次查询时间复杂度是 。

参考代码

• >
  Python

import sysinput = lambda: sys.stdin.readline().strip()LIM = 10 ** 9good = set()for ln in range(3, 13):    st = 1whileTrue:        prod = 1        overflow = Falsefor i in range(ln):            value = st + i# 先判断这一步乘上去会不会越界。if prod > LIM // value:                overflow = Truebreak            prod *= value# 一旦当前起点已经越界，后面的起点只会更大。if overflow:break        good.add(prod)        st += 1t = int(input())for _ in range(t):    x = int(input())# 预处理后，每次询问只要查集合。    print("YES"if x in good else"NO")

• >
  Cpp

#include<bits/stdc++.h>usingnamespacestd;intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);constlonglong lim = 1000000000LL;unordered_set<longlong> good;for (int len = 3; len <= 12; ++len) {for (longlong st = 1; ; ++st) {longlong prod = 1;bool overflow = false;for (int i = 0; i < len; ++i) {longlong value = st + i;// 这一位乘上去会越界，就可以直接停。if (prod > lim / value) {                    overflow = true;break;                }                prod *= value;            }// 当前起点已经越界，后面的起点也不用再试。if (overflow) {break;            }            good.insert(prod);        }    }int t;cin >> t;while (t--) {longlong x;cin >> x;// 预处理后，单次查询就是 O(1) 查表。cout << (good.count(x) ? "YES" : "NO") << '\n';    }return0;}

• >
  Java

import java.io.*;import java.util.*;publicclassMain{publicstaticvoidmain(String[] args)throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));finallong 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);    }}

02. 强迫症

问题描述

本题是小红书 2025.08.20 第 2 题的原题。

在小红书首页的两列中，小红薯独爱第一列。她将第一列每条的点赞状态从上到下用一个二进制字符串表示，其中：

• >
  字符表示用户已点赞第条；
• >
  字符表示用户未点赞第条。

小红薯定义一轮点赞行为如下：

• >
  选择索引对；
• >
  从第条开始，到第条结束，进行一次重复点赞行为。这会使得原本未点赞的变为已点赞，原本已点赞的变为未点赞。

小红薯希望使得这一列的点赞状态调整为一个回文串，即第一条和最后一条的点赞状态相同，第二条和倒数第二条的点赞状态相同，以此类推。

请计算她最少需要进行的点赞行为轮数。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数代表数据组数，每组测试数据描述如下：

第一行输入一个整数，表示数量；

第二行输入一个长度为、由字符0和1构成的字符串，表示点赞状态。

除此之外，保证单个测试文件的之和不超过。

输出格式

对于每一组测试数据，新起一行，输出一个整数，代表使字符串成为回文串所需的最少点赞行为轮数。

样例输入

22013010

样例输出

10

数据范围

• >
• >
• >
  单个测试文件中所有  之和不超过 

题解

这题看起来像是在一个二进制串上做区间翻转，但真正要盯住的不是整段字符串，而是每一对对称位置。

对于位置  和位置 ：

• >

  如果二者本来就相同，那这一对不用管。

• >

  如果二者不同，那这一对迟早要被修好。

于是可以把所有不相等的对称位置单独拎出来。设这些位置对在左半边的下标分别是：

如果翻转一个区间 ，那么某一对对称位置只有在“恰好翻到其中一个端点”时，是否相等的状态才会改变。进一步观察会发现：一次操作所影响到的这些对称下标，在左半边一定对应一段连续区间。

反过来，如果左半边有一段连续的不相等下标，比如从  到 ，那么直接翻转左半边这个区间 ，就能一次性把这整段对应的对称关系全部翻转，而不会影响其他位置对。

所以答案就非常直接了：

把所有不相等的对称位置找出来，统计它们在左半边形成了多少段连续块，答案就是多少。

这也是为什么它不需要区间 DP。真正有效的信息只有“哪些对称位置不相等”，而不是具体翻了哪个区间。

算法实现时，只要扫一遍前半部分：

• >

  若 s[i] != s[n - 1 - i]，说明当前位置属于不相等集合。

• >

  统计这样的下标一共分成多少段连续块即可。

复杂度分析：

• >

  每组数据线性扫描一次。

• >

  时间复杂度是 。

• >

  额外空间复杂度是 。

参考代码

• >
  Python

import sysinput = lambda: sys.stdin.readline().strip()t = int(input())for _ in range(t):    n = int(input())    s = input()    ans = 0    last = -2for i in range(n // 2):if s[i] == s[n - 1 - i]:continue# 新的不匹配连续块，需要新开一次操作。if i != last + 1:            ans += 1# 记录当前块在左半边延伸到哪里。        last = i    print(ans)

• >
  Cpp

#include<bits/stdc++.h>usingnamespacestd;intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) {int n;string s;cin >> n >> s;int ans = 0;int last = -2;for (int i = 0; i < n / 2; ++i) {if (s[i] == s[n - 1 - i]) {continue;            }// 新的不匹配连续块，需要新开一次操作。if (i != last + 1) {                ++ans;            }// 记录当前块在左半边延伸到哪里。            last = i;        }cout << ans << '\n';    }return0;}

• >
  Java

import java.io.*;publicclassMain{publicstaticvoidmain(String[] args)throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int t = Integer.parseInt(br.readLine());        StringBuilder out = new StringBuilder();while (t-- > 0) {int n = Integer.parseInt(br.readLine());            String s = br.readLine();int ans = 0;int last = -2;for (int i = 0; i < n / 2; i++) {if (s.charAt(i) == s.charAt(n - 1 - i)) {continue;                }// 新的不匹配连续块，需要新开一次操作。if (i != last + 1) {                    ans++;                }// 记录当前块在左半边延伸到哪里。                last = i;            }            out.append(ans).append('\n');        }        System.out.print(out);    }}

03. 每日一题 Plus

问题描述

本题是小红书 2025.08.24-第一套 第 3 题的原题。

这天，有人在小红书上发布了一道每日一题之编程题，如下：

给定一个长度为  的字符串 ，该字符串仅由小写字母构成。你需要删除尽可能少的字符，使得所得的字符串中，字符  至  的出现次数满足： 的次数  的次数  的次数。

显然，这个问题的答案非常多，因为可能有不同的删除方案。评论区已经有很多人给出了自己的解答。

为了展现你强大的编程实力，你决定写一个程序，在解决这个问题的同时，找到的字符串是全部答案中字典序最小的。直接输出这个字符串即可。

名词解释

不同长度字符串的字典序比较：从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的字母表顺序，字母序更小的字符串字典序也更小；如果比较到其中一个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。

输入格式

第一行输入一个整数 ，表示字符串长度。

第二行输入一个长度为 、仅由小写字母构成的字符串 。除此之外，保证字符串至少包含一个 。

输出格式

输出一个字符串，表示满足上述条件且字典序最小的结果字符串。

样例输入

4xyxz

3azz

样例输出

xyz

zz

数据范围

• >
• >
  字符串仅由小写字母构成
• >
  字符串至少包含一个 

题解

这题最容易错在“只做对一半”。第一步确实要先决定每个字母最后保留多少个，但如果做到这里就直接把答案按 a..z 拼出来，就会忽略一个关键事实：

删除字符之后，剩下的结果必须仍然是原串的一个子序列，字符相对顺序不能打乱。

所以这题要分成两步做。

#第一步：先算每个字母最多能保留多少个

设原串中 26 个字母的出现次数为 cnt[0..25]，目标是确定一个新数组 keep[0..25]，满足：

并且：

因为删得越少越好，所以等价于让  尽量大。

如果已经知道右边字母最多能保留多少个，那么当前字母能保留的上限也就确定了。

从 z 往前做贪心：

• >

  z 没有右侧约束，所以直接全部保留，令 keep[25] = cnt[25]。

• >

  对于其余字母 i，为了满足单调不降，必须有 keep[i] <= keep[i+1]。

• >

  同时又不能超过自己原本的数量，所以最优选择就是：

这样做既保证了合法，又让保留总量尽可能大。

#第二步：在固定配额下，取字典序最小的子序列

保留次数确定之后，问题就变成了：

从原串里恰好选出 keep[i] 个字母 i，构成一个子序列，并让这个子序列字典序最小。

这是一个很经典的“单调栈 + 剩余数量”模型。

扫描原串时，维护：

• >
  remain[i]：当前位置之后还剩多少个字母 i；
• >
  used[i]：当前栈里已经放了多少个字母 i。

遇到当前字符 ch 时：

• >
  如果这个字符的配额已经用满了，那它只能跳过；
• >
  否则就尝试把它放进答案；
• >
  放进去之前，如果栈顶字符比它大，而且把栈顶弹掉以后，后面仍然来得及补足栈顶字符的配额，那么就应该先弹栈，这样答案会更小。

这一步的本质是：在不破坏最终可行性的前提下，尽量把更小的字符往前放。

复杂度分析：

• >

  统计次数需要 。

• >

  反推 keep 只需要扫 26 个字母，时间是常数级。

• >

  单调栈部分每个字符最多进栈、出栈各一次，总时间复杂度还是 。

• >

  额外空间复杂度是 。

参考代码

• >
  Python

import sysinput = lambda: sys.stdin.readline().strip()defsolve():    n = int(input())    s = input()    cnt = [0] * 26for ch in s:        cnt[ord(ch) - ord('a')] += 1    keep = [0] * 26    keep[25] = cnt[25]for i in range(24, -1, -1):        keep[i] = min(cnt[i], keep[i + 1])    remain = cnt[:]    used = [0] * 26    stack = []for ch in s:        idx = ord(ch) - ord('a')        remain[idx] -= 1# 当前字符的配额已经够了，直接跳过。if used[idx] == keep[idx]:continuewhile stack:            top = ord(stack[-1]) - ord('a')# 栈顶不比当前字符大，就没有必要再弹。if top <= idx:break# 弹掉栈顶后，如果后面补不回它的配额，就不能弹。if used[top] - 1 + remain[top] < keep[top]:break            used[top] -= 1            stack.pop()        stack.append(ch)        used[idx] += 1    print(''.join(stack))if __name__ == "__main__":    solve()

• >
  Cpp

#include<bits/stdc++.h>usingnamespacestd;intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;string s;cin >> s;vector<int> cnt(26, 0);for (char ch : s) {        ++cnt[ch - 'a'];    }vector<int> keep(26, 0);    keep[25] = cnt[25];for (int i = 24; i >= 0; --i) {        keep[i] = min(cnt[i], keep[i + 1]);    }vector<int> remain = cnt;vector<int> used(26, 0);string ans;    ans.reserve(n);for (char ch : s) {int idx = ch - 'a';        --remain[idx];// 当前字符的配额已经够了，直接跳过。if (used[idx] == keep[idx]) {continue;        }while (!ans.empty()) {int top = ans.back() - 'a';// 栈顶不比当前字符大，就没有必要再弹。if (top <= idx) {break;            }// 弹掉栈顶后，如果后面补不回它的配额，就不能弹。if (used[top] - 1 + remain[top] < keep[top]) {break;            }            --used[top];            ans.pop_back();        }        ans.push_back(ch);        ++used[idx];    }cout << ans << '\n';return0;}

• >
  Java

import java.io.*;publicclassMain{publicstaticvoidmain(String[] args)throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());        String s = br.readLine();int[] cnt = newint[26];for (int i = 0; i < s.length(); i++) {            cnt[s.charAt(i) - 'a']++;        }int[] keep = newint[26];        keep[25] = cnt[25];for (int i = 24; i >= 0; i--) {            keep[i] = Math.min(cnt[i], keep[i + 1]);        }int[] remain = cnt.clone();int[] used = newint[26];char[] stack = newchar[n];int top = 0;for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);int idx = ch - 'a';            remain[idx]--;// 当前字符的配额已经够了，直接跳过。if (used[idx] == keep[idx]) {continue;            }while (top > 0) {int last = stack[top - 1] - 'a';// 栈顶不比当前字符大，就没有必要再弹。if (last <= idx) {break;                }// 弹掉栈顶后，如果后面补不回它的配额，就不能弹。if (used[last] - 1 + remain[last] < keep[last]) {break;                }                used[last]--;                top--;            }            stack[top++] = ch;            used[idx]++;        }        System.out.println(new String(stack, 0, top));    }}