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

小红走网格 思路 小红从原点 (0,0) 出发，每次可以向上走 a 步、向下走 b 步、向左走 c 步、向右走 d 步，问能否到达 (x, y)。 把 x 和 y 两个方向拆开独立考虑：  x 方向：向右走 r 次、向左走 s 次，最终 x 坐标 = rd - sc，其中 r, s >= 0。 y 方向：向上走 p 次、向下走 q 次，最终 y 坐标 = pa - qb，其中 p, q >= 0。  关键数学结论：对于非负整数 r, s，rd - sc 能表示的整数集合恰好是 gcd(c, d) 的所有倍数。 为什么？由裴蜀定理，存在整数 r', s' 使得 r'd + s'c =...

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

小红喜欢1 思路 拿到这题第一反应是什么？一个数组里只有一个 1，其余全是 0，找到那个 1 的下标就行了。 那怎么找？直接从头到尾扫一遍，碰到 1 就输出当前位置，结束。没有比这更直接的做法了。 注意一个细节：题目要求的下标是 从 1 开始 的，不是从 0 开始，所以计数器从 1 开始累加就好。 另外，题目输入没有先给数组长度 n，而是直接给了一行数字，所以我们边读边判断就行，读到 1 立刻输出并退出，甚至不需要把整个数组存下来。 代码    C++   Java   Python3   JavaScript   #include <iostream> using namespa...

小红的字符串 思路 拿到这道题，先想想回文串的性质：一个回文串满足 s[i] == s[n-1-i]，也就是首尾对称的字符必须相同。 那操作是什么呢？每次可以把一个字符循环右移到字母表的下一个字母（'a'->'b'->'c'->...->'z'->'a'）。问最少操作多少次能把字符串变成回文串。 怎么拆解这个问题？ 既然回文串要求对称位置的字符相等，我们只需要关注每一对 (s[i], s[n-1-i]) 就行了。每一对是独立的——把这对变成相同字符的最小代价加起来，就是总答案。 那对于一对字符 (a, b)，怎么用最少的右移操作让它们相等？ 我们可以只移 a，也可...

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

BGN31: 清楚姐姐买竹鼠 题目分析 清楚姐姐要买至少 n 只竹鼠，有两种购买方式：单买一只花 a 元，或者买一捆（3只）花 b 元。问最少花多少钱？ 拿到这道题，你会怎么想？ 思路引导 首先问自己一个问题：我们是不是只要比较"单买3只"和"买一捆"哪个更划算就行了？ 没那么简单。虽然如果 b < 3a，买捆更划算，但问题在于 n 不一定是 3 的倍数。比如要买 10 只，买 3 捆是 9 只，还差 1 只得单买。而买 4 捆就是 12 只，多买了 2 只但也许反而更便宜。 所以关键在于：最后那个"零头"怎么处理？ 我们可以枚...

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

茉茉的密码 思路 题意很直接：给你  个由小写字母组成的字符串，找出一个在所有字符串中都出现过的公共子串，输出任意一个即可。 既然"任意一个"都行，那最简单的想法是——找一个所有字符串里都有的单个字符不就行了？确实可以，但这题其实是在考最长公共子串的思路，我们不妨把它做完整。 二分 + 滚动哈希 核心思路是二分答案：二分公共子串的长度 ，然后验证是否存在长度为  的子串同时出现在所有字符串中。 验证的方法是滚动哈希（Rabin-Karp）：  取最短的那个字符串  作为基准（公共子串长度不可能超过最短串）。 把  所有长度为  的子串的哈希值丢进一个集合 common。 对...

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

乒乓球 思路 拿到这道题，先理解一下规则：给你一串由 'W' 和 'L' 组成的比赛记录，要你分别用 11 分制和 21 分制来模拟，输出每一局的比分。 那什么时候一局结束呢？两个条件同时满足：  某一方的分数 不小于 目标分数（11 或 21） 双方比分差 至少为 2  想到这里，是不是觉得其实就是一个简单的模拟？没错，遍历字符串，维护双方得分，每次检查是否满足结局条件就行了。 需要注意什么？ 有个小坑：如果字符串读完了但当前这局还没打完（比分差不够 2，或者还没到目标分），也要输出当前比分。这个容易漏掉。 还有输出格式——11 分制输出完之后要有一个空行，再输出 21 分制的结果。 实现步...

小红和小紫的取素因子游戏 思路 经典博弈论问题。小红和小紫轮流对正整数 x 操作：每次选一个 x 的素因子 k（k > 1），把 x 变成 x/k。谁先没法操作谁就输，小红先手。 关键观察：不管怎么选素因子，总操作次数是固定的，等于 x 的素因子个数（含重复）。 为什么？每次操作都是把 x 除以它的某个素因子，也就是从 x 的质因数分解里去掉一个素因子。不管你每次选哪个素因子去掉，最终都要把所有素因子去完才会变成 1。所以总步数 = x 的质因数分解中素因子的总个数（计重数）。 比如 x = 12 = 2^2 * 3，一共 3 个素因子（两个 2 和一个 3），不管怎么操作都是 3 步。...

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

最大子段和 思路 经典中的经典——最大子段和，也叫最大子数组和。给你一个整数数组，找一段连续的子数组，使得它的元素之和最大。 最暴力的做法当然是枚举所有子数组，算出每个的和取最大值，但那是  的，数据大了就扛不住。 这里用的是 Kadane 算法，核心思想特别简单：我们维护一个变量 cur 表示"以当前元素结尾的最大子段和"。每读入一个新元素，就把它加到 cur 上，然后用 cur 去更新全局答案。如果 cur 变成负数了呢？那说明前面这一段已经是累赘了，不如从下一个元素重新开始，所以把 cur 归零。 为什么这样是对的？因为一个负数的前缀只会拖累后面的元素，丢掉它一定不亏...