小红背单词 思路 题意很直接：小红按顺序背单词，当她已经记住了 k 个单词时，一个新单词需要出现 k+1 次才能记住。问最终记住了多少个单词？ 那我们怎么模拟这个过程呢？ 关键观察：我们需要追踪两个东西——每个单词累计出现了几次，以及当前已经记住了几个单词（也就是"记忆门槛"）。 模拟过程：遍历输入序列，对每个单词：  如果已经记住了，跳过（不需要再背了） 否则把它的出现次数 +1 检查出现次数是否达到了门槛 total + 1（total 是当前已记住的单词数），达到了就记住它，total++  拿示例来走一遍：输入 you thank queue queue thank...

小红的回文串 思路 题目给了三种操作：拆分（w→vv，m→nn）、轴对称（b↔d，p↔q）、翻转（b↔q，d↔p，n↔u），问经过若干次操作后能不能变成回文串。 先别急着写代码，想想这些操作到底在干嘛？ 第一步：找等价类。 把所有能互相转换的字符归成一组：  b、d、p、q 通过轴对称和翻转可以互相转换，它们是一类 n、u 通过翻转可以互换，它们是一类 其他字母各自独立  所以判断回文的时候，b 和 q 算"相同"，n 和 u 也算"相同"。 第二步：处理拆分操作。 w 可以拆成两个 v，m 可以拆成两个 n。注意这里改变了字符串长度！也就是说，w 可以...

三角形取数(Hard Version) 思路 拿到题先理解这个"三角形"的结构：第  行有  个数，视觉上就是一个正三角形，每往下一行两边各多一个数。 从顶点出发，每一步可以往左下、正下、右下三个方向走。记左下走了  次、右下走了  次，要求最终 ，问路径上数字之和的最大值。 关键观察： 每一步的列变化量分别是 （左下不变列号，但因为下一行比当前行左边多了一个位置，相当于相对位移 ）、（正下）、（右下）。起始在第  行正中央，设"偏移量"为 ，那么到第  行时，列号 。 约束  就等价于最终列号满足 ，即 。 这个观察把问题彻底简化了——约束只作用在最后...

游游的排列构造 思路 这题要我们构造一个长度为 n 的排列，使得恰好有 k 个"好元素"（即前缀最大值），而且任意两个好元素不能相邻。 先想想好元素的性质：好元素就是从左往右扫的时候，每次遇到一个比之前所有值都大的位置。第一个位置一定是好元素（它自己就是前缀最大值）。 那怎么让好元素不相邻呢？最直觉的想法是把好元素放在偶数位置（第 1、3、5、... 个位置），这样相邻的两个好元素之间至少隔了一个非好元素。 具体构造方法：把 1 到 n 这些值分成 k 个块。  前 k-1 个块，每块 2 个数：第 i 个块（0-indexed）包含 ，我们先输出大的 （作为好元素），再输...

小红书推荐系统 思路 拿到这道题，先读题：给你一行搜索记录（由空格分隔的单词），要你找出所有出现次数不少于 3 次的单词，按频次从高到低输出，频次相同则按字典序升序。 那怎么统计每个单词出现了多少次呢？最自然的想法就是用一个哈希表（map），以单词为 key、出现次数为 value。 具体步骤是什么？  读入一整行字符串，按空格拆分出每个单词 用哈希表统计每个单词的出现次数 筛出频次  的单词 按频次降序排序，频次相同按字典序升序 逐行输出  整个流程就是：统计 -> 筛选 -> 排序 -> 输出，非常直白。 有什么需要注意的？ 排序的比较函数要写对——先比频次（大的在前），...

小红的矩阵染色 思路 题目在说什么？给你一个  的矩阵，里面有黑色格子（*）和白色格子（o），你最多可以把  个白色格子染成红色。得分规则：一个红色格子的正下方也是红色时，这个格子贡献 1 分。问最多能得几分？ 换句话说，我们要在矩阵里选一些白色格子染红，让红色格子在纵向上尽量连续。 那怎么想这道题呢？ 关键观察 首先，得分只和同一列中相邻的红色格子有关。横向相邻没有贡献，所以我们可以逐列独立分析。 对于每一列，黑色格子把白色格子分成了若干段连续的白色区间。比如一列是 o o * o o o，那就被分成长度为 2 和长度为 3 的两段。 如果我们在某段长度为  的连续白色区间中选了  个格子来...

游游的最小公倍数 思路 题目在说什么？给一个正整数 ，要把它拆成两个正整数 （），让  尽可能大。 怎么让 lcm 最大？回忆一下，。所以我们想要两件事：   尽量大 —— 这意味着  和  尽量接近   尽量小 —— 最理想的情况是 （互质）  如果能找到一对互质的  且尽量靠近 ，那  就是最大的。 分情况讨论  是奇数：取 ，。这两个数是相邻整数，一定互质，乘积最大。 ：取 ，。此时  是偶数，所以  和  都是奇数。它们的差为 2，且都是奇数，所以  但  必须是奇数，因此 。  且 ：取  行不行？不行，因为  是奇数， 和  都是偶数，。退一步，取 ，。此时  和  都是奇数（奇数...

小红的排列构造① 思路 这道题要求构造一个长度为  的排列，使得每个位置  都满足  不是质数。 先看小情况：  ：排列只有 ， 是质数，无解。 ： 给出 ， 给出 ，怎么放都有质数，无解。  那  呢？有一个非常巧妙的构造：把前三个位置放 ，后面的位置 （）直接放  本身。 为什么这样是对的？  位置 1 放 3：，合数 ✓ 位置 2 放 2：，合数 ✓ 位置 3 放 1：，合数 ✓ 位置 （）放 ：，是大于 2 的偶数，一定是合数 ✓  前三个位置的和全是 4，后面位置的和是 ，都是偶数且 ，不可能是质数。完美！ 这个构造的关键洞察是：恒等排列  几乎就是答案，唯一的问题在位置 1（ 是质...

分数线划定 思路 这题说白了就是个排序 + 模拟。先把题目拆解一下：  有 n 个人参加笔试，计划录取 m 人进面试 面试分数线怎么定？取排名第  名选手的成绩作为分数线 所有成绩 大于等于 分数线的选手都能进面试（所以实际人数可能超过计划数）  那关键问题来了——怎么排序？ 题目要求按成绩从高到低排，成绩相同则按报名号从小到大。排好之后，找到第  个人的成绩就是分数线。 但这里有个细节：可能有多个人和分数线同分。这些人全部要进面试，所以最终进面试的人数可能比  多。 实现上很直接：  读入数据，自定义排序 算出 ，取  的成绩作为分数线 遍历统计所有成绩  分数线的人数，输出即可  因为排好...

1=N 思路 题目在说什么？给你一个正整数 ，每次操作可以选择  的一个  的因子 ，将  变为 ，花费为 。问把  变成  的最小总花费。 关键观察 假设我们选了一个合数因子 （），一次操作花费 。但如果分两步：先除以 （花费 ），再除以 （花费 ），总花费 。 所以每次只除以质因数一定更优。 这意味着最小总花费就是  的所有质因数之和（含重复）。即对 ，答案为： $$ 以样例  为例：花费 。 实现 直接做质因数分解，枚举  到  的因子，累加每个质因子的贡献即可。时间复杂度 。 代码    C++   Java   Python3   JavaScript   #include <...

穷哈哈~ 思路 拿到这题先理解"笑声"的定义：笑声是由字母 h 和 a 交替组成的序列。比如 "a"、"ha"、"aha"、"hahaha" 这些都是合法的笑声，但 "hh"、"aa"、"abc" 就不是。 那问题就变成了：在字符串里找一个最长的连续子串，这个子串只包含 h 和 a，并且相邻字符不相同。 怎么做？直接一次遍历就够了。维护一个当前合法笑声的长度 cur：  如果当前字符不是 h 也不是 a，笑声中断，cur 归零； 如果当...

牛妹的位运算 思路 这题要求在  中找满足  且  的对数。 先搞清楚  到底意味着什么。两个数比大小，看的是最高位。AND 在某一位为 1，说明 a、b 在那一位都是 1；XOR 在某一位为 1，说明 a、b 在那一位不同。 所以条件成立的含义是：存在某个二进制位，a 和 b 在这一位上不同，并且在所有更高的位上，a 和 b 完全相同。换句话说，a 和 b 的最高不同位，要比它们的最高"都为1"的位更高。 再换个角度想：只要 ，考虑它们从高到低第一次出现不同的那一位。在这一位之上，a 和 b 完全相同，所以 AND 和 XOR 在那些更高位上的贡献一样。而在这个&quot...

【模板】排序 思路 拿到这题，题意很直白：给你一个整数数组，按从小到大排好序输出就行。 那问题来了——排序算法那么多，这里该用哪个？ 对于竞赛和实际工程来说，直接用标准库的排序就是最优选择。C++ 的 sort() 底层是 IntroSort（快排 + 堆排 + 插入排序的混合体），Java 的 Arrays.sort() 对基本类型用的是双轴快排。两者平均时间复杂度都是 ，而且经过了大量优化，手写很难比它们更快。 唯一要注意的就是 I/O 效率。数据量大的时候，C++ 用 scanf/printf 比 cin/cout 快不少；Java 用 BufferedReader + StringBu...

【模板】01背包 思路 经典的 01 背包模板题，但这道题要求输出两个答案：  不要求装满：背包容量为 ，在不超过容量的前提下，能装的最大价值是多少？ 恰好装满：背包容量恰好为  时，能装的最大价值是多少？如果装不满就输出 0。  01 背包基础 01 背包的核心：每个物品只有「选」或「不选」两种状态。 定义  表示容量为  时能获得的最大价值。对于每个物品 ，从大到小遍历容量（这样保证每个物品只选一次）： $$ 两问的区别在于初始化 这道题的精髓就在初始化： 第一问（不要求装满）： 全部初始化为 0。因为任何容量下，「什么都不装」也是一种合法方案，价值为 0。 第二问（恰好装满）：只有  是...