2016年的美团校招笔试放到今天再看依然是一套非常值得拿出来反复刷的题。我这几天重新把“美团2016研发工程师编程题(二)”完整做了一遍发现这套题没有那种偏难怪的题但每一道都精准戳中了面试官真正想考察的点单调栈、字典序计数、带边界的矩阵模拟。三个考点覆盖了笔试中最常见的数据结构、数学建模和代码实现能力。如果你正在准备研发工程师岗位的笔试或面试这套题很适合用来做一次完整的自测尤其是在牛客网上模拟真实笔试环境能把心态问题也一起暴露出来。1. 这套题的整体设计与考点拆解1.1 三道题分别考什么先给一个整体的表格方便你做题型定位题目核心考点推荐解法难度同类题出现频率直方图内最大矩形单调栈、贪心、边界处理单调栈 O(n)中等极高LeetCode 84 原题字符串计数字典序、组合计数、分类讨论按位统计中等偏难高变体非常多棋子翻转模拟、方向数组、越界处理直接模拟简单中笔试常客如果你只看难度会觉得这套题没有特别难的题。但真正做起来会发现三道题里有两道不是一次就能写对的。直方图最大矩形即使你知道要用单调栈边界条件处理不好也会卡很久字符串计数更是把“分类讨论”考到了极致长度不同的字符串和固定长度目标串之间的字典序关系特别容易绕晕。1.2 为什么美团这样出题2016年的美团还在高速扩张期研发工程师需要应对大量真实业务场景比如订单调度、商家数据检索、用户行为统计这些场景说白了就是数据结构和算法的基础应用。所以笔试题目不会故意刁难你它们考察的是三件事第一常用数据结构是否真的理解到位而不是背模板第二面对一个需要分类讨论的问题能不能把逻辑理清楚再动手第三在有限时间内能不能写出无 bug 的代码。这套题的区分度也做得很好。模拟题人人会写但写快写对的人不多单调栈那道题知道单调栈和不知道单调栈的人代码量和思考路径会差很多字符串计数那道题很多人会在“s1 本身长度等于 targetLen 时是否减一”这种细节上翻车。三道题综合起来基本能把候选人的代码能力分成几个梯队。现在很多公司的笔试喜欢堆题量动辄十几道选择题加三道编程题反而很难像这样用三道题精准定位水平这也是我建议大家回头做老题的原因。2. 直方图内最大矩形单调栈是标准解2.1 题目理解与暴力思路题目描述大意是给定 n 个非负整数表示直方图中各个柱子的高度每个柱子的宽度为 1求这个直方图中能够形成的最大矩形面积。这道题最直觉的做法是枚举矩形的左右边界然后在左右边界之间找最小高度面积等于最小高度乘以宽度。这个做法的时间复杂度是 O(n^2)代码写起来也很简单def max_area_bruteforce(heights): n len(heights) ans 0 for left in range(n): min_h heights[left] for right in range(left, n): min_h min(min_h, heights[right]) ans max(ans, min_h * (right - left 1)) return ans当 n 超过 10^4 时O(n^2) 就会超时。笔试里看到数组长度范围基本就要意识到必须优化到 O(n) 或者 O(n log n)。而这道题的最优解就是利用“最大矩形的高一定等于某个柱子的高度”这个关键观察。为什么最大矩形的高一定等于某个柱子的高度因为如果你的矩形高度不贴着任何柱子的顶边那它一定可以继续向上扩展一段距离直到碰到某个柱子的顶边这时候面积会更大。所以考虑每一个柱子让它作为矩形的高度然后向左右扩展直到遇到第一个高度小于它的柱子。这样以该柱子为高的最大矩形就确定了。朴素地做这件事也是 O(n^2)因为每个柱子都要向左右扫描。单调栈的用处就是把“向左右找第一个更矮柱子”这个过程优化到均摊 O(1)。2.2 单调栈解法推导单调栈的思路是维护一个高度单调递增的栈栈里存的是柱子的下标。从左到右遍历每个柱子当当前柱子的高度小于栈顶柱子的高度时说明栈顶柱子的右边界已经出现因为右边已经有一个柱子比它矮了。此时把栈顶柱子出栈它的高就是它自己的高度它的左边界是出栈后新的栈顶位置右边界就是当前遍历到的位置。用一个例子走一遍heights [2,1,5,6,2,3]遍历到下标 0高度 2栈空入栈栈为 [0]。遍历到下标 1高度 1栈顶高度 2 1出栈下标 0。此时高度 2 的柱子左边界是 -1栈空右边界是 1面积 2 * (1 - (-1) - 1) 2。然后当前高度 1 入栈栈为 [1]。遍历到下标 2高度 5栈顶高度 1 5入栈栈为 [1,2]。遍历到下标 3高度 6入栈栈为 [1,2,3]。遍历到下标 4高度 2栈顶高度 6 2出栈下标 3高度 6左边界是 2右边界是 4面积 6 * (4 - 2 - 1) 6。继续栈顶下标 2 高度 5 2出栈下标 2高度 5左边界是 1右边界是 4面积 5 * (4 - 1 - 1) 10。然后当前高度 2 入栈栈为 [1,4]。遍历到下标 5高度 3入栈栈为 [1,4,5]。遍历结束在数组末尾补一个高度为 0 的哨兵柱子强制把栈里剩余元素全部弹出来计算。这里最后一个哨兵非常重要。如果不在末尾补 0栈里会剩下高度 3、2、1 这三根柱子没有计算结果就漏了。代码实现def largest_rectangle_area(heights): stack [] max_area 0 # 末尾补0作为哨兵保证所有柱子最后都能出栈 for i, h in enumerate(heights [0]): while stack and heights[stack[-1]] h: height heights[stack.pop()] left stack[-1] if stack else -1 width i - left - 1 max_area max(max_area, height * width) stack.append(i) return max_area这段代码运行完后max_area 就是最大矩形面积。整体时间复杂度 O(n)因为每个下标最多入栈一次、出栈一次。2.3 代码实现的细节与易错点先说出栈时宽度计算的原理。当栈顶柱子出栈时当前遍历到的位置 i 是它右边第一个比它矮的柱子所以右边界是 i - 1。出栈后新的栈顶如果是 left那么 left 位置的柱子是它左边第一个比它矮的柱子所以左边界是 left 1。宽度就是 (i - 1) - (left 1) 1 i - left - 1。这个公式是单调栈解法的核心建议亲手推导一次不要死记。关于相等高度的处理while 条件用的是而不是。也就是说当遇到和栈顶高度相等的柱子时左边那根相同高度的柱子先不出栈它会等到右边出现一个更矮的柱子时才出栈。这样计算的宽度会把相等高度的柱子都包含进去最终面积不会变小。比如 heights [2,2]如果用第一个 2 会在遇到末尾哨兵 0 时出栈宽度是 2面积为 4正确。如果用第一个 2 在遍历到第二个 2 时就会出栈当时宽度是 1面积是 2虽然第二个 2 后面还会算一次但逻辑会多一层考虑不如干净。还有一个细节是栈里存下标而不是存高度。原因是下标能同时拿到柱子的高度和位置出栈后可以计算宽度。如果只存高度宽度没法算如果只存下标高度可以通过 heights[下标] 拿到。边界情况也要考虑空数组直接返回 0全 0 的数组任何柱子的高度都是 0面积也是 0数组长度为 1那就返回这一个柱子的高度。这些用例在笔试时建议自己先想一遍能有效减少低级失误。3. 字符串计数字典序计数的通用解法3.1 题目描述与思路转换题目描述大意是给定两个仅由小写字母组成的字符串 s1 和 s2以及一个整数 len求长度恰好为 len、只含小写字母、且字典序大于 s1 小于 s2 的字符串个数。结果对 1000007 取模。s1 和 s2 的长度都小于等于 50len 在 1 到 50 之间。第一眼看过去可能会想枚举所有长度为 len 的字符串那有 26^len 种直接爆炸。正确的思路是把问题拆成两个函数写一个count_less(t, length)统计长度恰好为 length 的字符串中字典序严格小于字符串 t 的个数。那么答案就等于count_less(s2, len) - count_less(s1, len)另外如果 s1 本身就是长度恰好为 len 的字符串那还要再减 1因为 s1 本身是合法候选字符串但它不小于自己而我们的目标是“大于 s1”。这里最需要小心的是s1 和 s2 的长度不一定等于 len。字典序比较时如果某个字符串是另一个字符串的前缀短的字符串字典序更小比如 ab abc。所以长度为 len 的候选字符串和长度不足 len 的 s1 比较时情况会比较微妙这也是多数人卡住的点。3.2 小于某个串的数量怎么算核心实现是count_less函数。先明确一点我们要统计的是长度固定为 length 的候选字符串而 t 的长度可能大于、等于或小于 length所以必须先统一处理。如果 t 的长度大于 length那么只需看 t 的前 length 个字符。所有长度 length 且字典序小于这个前缀的字符串显然都小于 t另外恰好等于这个前缀的那个长度为 length 的字符串也比 t 小因为 t 比它长所以要额外加 1。如果 t 的长度等于 length直接统计小于 t 的字符串个数即可。如果 t 的长度小于 length把 t 后面用空字符补齐到 length。这个空字符小于任何小写字母所以所有长度为 length 的候选字符串在 t 耗尽的位置上都会比 t 大这正好对应了字典序中“短前缀更小”的规则。统一之后就得到了一个长度恰为 length 的字符串 TT 里可能包含空字符现在只需要统计字典序严格小于 T 的候选字符串个数。方法是逐位统计对于第 i 位如果 T[i] 是普通小写字母 c那么候选字符串第 i 位可以选择 a 到 c-1 之间任意一个字母共ord(c) - ord(a)种选择后面 length - i - 1 位可以任意填有 26^(length-i-1) 种所以这一位的贡献就是这两个数相乘。然后让第 i 位等于 c继续看下一位。如果 T[i] 是空字符说明 T 已经结束任何候选字符串在这一位都有字符都比 T 大所以直接停止统计。代码实现MOD 1000007 def count_less(t, length): # 统计长度恰好为length的字符串中字典序严格小于t的个数 if len(t) length: # 截断并加上等于截断串的那一个 return count_less_prefix(t[:length]) 1 # 长度不足时用 \0 补齐\0 小于 a padded t \0 * (length - len(t)) return count_less_prefix(padded) def count_less_prefix(T): # T 的长度已经是 length可能包含 \0 total 0 L len(T) for i in range(L): c T[i] if c \0: break cnt ord(c) - ord(a) if cnt: total (total cnt * pow(26, L - i - 1, MOD)) % MOD return total % MOD主流程def solve(): # 牛客常见输入一行包含 s1、s2、len line input().strip().split() s1, s2 line[0], line[1] length int(line[2]) ans count_less(s2, length) - count_less(s1, length) if len(s1) length: ans - 1 print(ans % MOD)这里减法之后必须取模因为count_less(s2) - count_less(s1)可能为负Python 的%会正确处理负数其他语言可能需要(ans MOD) % MOD。3.3 取模、边界与验证示例先验证一个例子s1 as2 clength 2。count_less(c, 2)补齐为 c\0第 0 位 c 的贡献是(c-a) * 26^1 52遇到空字符停止结果 52也就是所有 a? 和 b? 开头的字符串。count_less(a, 2)第 0 位 a 的贡献是 0结果 0。len(s1) 1不等于 2不减 1。答案 52。手动验证长度 2 的字符串大于 a 小于 c 的包含 aa... az 和 ba... bz正好 52 个正确。再看一个容易出错的例子s1 abs2 aclength 3。count_less(ac, 3)补齐为 ac\0第 0 位贡献 0第 1 位 c 贡献(c-a) * 26^1 52结果 52。count_less(ab, 3)第 1 位 b 贡献(b-a) * 26^1 26结果 26。len(s1) 2不等于 3不减 1。答案 26。手动验证大于 ab 小于 ac 的长度 3 字符串第一位必须是 a因为 b?? 已经大于 ac 了第二位必须是 b因为 ab? 都大于 ab 且都小于 ac第三位任意因为第二位 b 已经小于 c所以是 aba 到 abz共 26 个正确。取模的坑主要出现在减法。如果答案是负数直接 print(ans % MOD) 在 Python 里没问题但在 C 或 Java 里要写成(ans % MOD MOD) % MOD否则会输出负数。另外pow(26, 0, MOD)结果是 1这个在代码里要保证不写错指数当 i 走到最后一位时remaining 为 0贡献就是cnt * 1。这道题还有一个容易忽略的点s1 和 s2 的输入可能包含空格或换行读取时要确定输入格式。牛客网上这道题的输入格式是同一行三个值用空格分隔所以input().split()就够了。如果做题平台不同格式可能变成三行写代码前先确认。4. 棋子翻转模拟题也要细心4.1 题目规则与思路我印象里这道题是这样的给定一个棋盘每个格子上有棋子用 0 和 1 表示两种状态。接下来给出一系列翻转操作的坐标每次操作会把该坐标点本身以及它上、下、左、右四个相邻位置的棋子全部翻转0 变 11 变 0。如果某个相邻位置超出棋盘范围就忽略它。最后输出翻转完成后的棋盘状态。这类题在笔试里属于“送分题”但送分题最怕送命。很多人不是不会写而是漏了越界检查或者坐标转换时忘记减一。它的核心思路就是用一个方向数组枚举五个位置然后逐个判断是否在棋盘内在就翻转。如果你愿意多想一步会发现翻转操作是有交换律的因为对每个格子的翻转本质上是累计翻转次数取模 2。也就是说操作顺序不影响最终结果。如果操作次数特别多可以先统计每个格子被翻转的次数最后只需要看奇偶性。但对于一般的笔试数据量直接模拟就足够了。4.2 代码实现def solve(): n int(input()) board [] for _ in range(n): board.append(list(map(int, input().split()))) ops [] try: while True: line input().strip() if not line: break x, y map(int, line.split()) ops.append((x - 1, y - 1)) # 输入坐标从1开始转为0基 except EOFError: pass dirs [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)] for x, y in ops: for dx, dy in dirs: nx, ny x dx, y dy if 0 nx n and 0 ny n: board[nx][ny] ^ 1 for row in board: print( .join(map(str, row)))这里用try...except EOFError来读取不定数量的操作坐标在牛客网的多行测试输入场景下很实用。如果题目在开头 美团2016研发笔试编程题解析：单调栈、字典序与模拟
2016年的美团校招笔试放到今天再看依然是一套非常值得拿出来反复刷的题。我这几天重新把“美团2016研发工程师编程题(二)”完整做了一遍发现这套题没有那种偏难怪的题但每一道都精准戳中了面试官真正想考察的点单调栈、字典序计数、带边界的矩阵模拟。三个考点覆盖了笔试中最常见的数据结构、数学建模和代码实现能力。如果你正在准备研发工程师岗位的笔试或面试这套题很适合用来做一次完整的自测尤其是在牛客网上模拟真实笔试环境能把心态问题也一起暴露出来。1. 这套题的整体设计与考点拆解1.1 三道题分别考什么先给一个整体的表格方便你做题型定位题目核心考点推荐解法难度同类题出现频率直方图内最大矩形单调栈、贪心、边界处理单调栈 O(n)中等极高LeetCode 84 原题字符串计数字典序、组合计数、分类讨论按位统计中等偏难高变体非常多棋子翻转模拟、方向数组、越界处理直接模拟简单中笔试常客如果你只看难度会觉得这套题没有特别难的题。但真正做起来会发现三道题里有两道不是一次就能写对的。直方图最大矩形即使你知道要用单调栈边界条件处理不好也会卡很久字符串计数更是把“分类讨论”考到了极致长度不同的字符串和固定长度目标串之间的字典序关系特别容易绕晕。1.2 为什么美团这样出题2016年的美团还在高速扩张期研发工程师需要应对大量真实业务场景比如订单调度、商家数据检索、用户行为统计这些场景说白了就是数据结构和算法的基础应用。所以笔试题目不会故意刁难你它们考察的是三件事第一常用数据结构是否真的理解到位而不是背模板第二面对一个需要分类讨论的问题能不能把逻辑理清楚再动手第三在有限时间内能不能写出无 bug 的代码。这套题的区分度也做得很好。模拟题人人会写但写快写对的人不多单调栈那道题知道单调栈和不知道单调栈的人代码量和思考路径会差很多字符串计数那道题很多人会在“s1 本身长度等于 targetLen 时是否减一”这种细节上翻车。三道题综合起来基本能把候选人的代码能力分成几个梯队。现在很多公司的笔试喜欢堆题量动辄十几道选择题加三道编程题反而很难像这样用三道题精准定位水平这也是我建议大家回头做老题的原因。2. 直方图内最大矩形单调栈是标准解2.1 题目理解与暴力思路题目描述大意是给定 n 个非负整数表示直方图中各个柱子的高度每个柱子的宽度为 1求这个直方图中能够形成的最大矩形面积。这道题最直觉的做法是枚举矩形的左右边界然后在左右边界之间找最小高度面积等于最小高度乘以宽度。这个做法的时间复杂度是 O(n^2)代码写起来也很简单def max_area_bruteforce(heights): n len(heights) ans 0 for left in range(n): min_h heights[left] for right in range(left, n): min_h min(min_h, heights[right]) ans max(ans, min_h * (right - left 1)) return ans当 n 超过 10^4 时O(n^2) 就会超时。笔试里看到数组长度范围基本就要意识到必须优化到 O(n) 或者 O(n log n)。而这道题的最优解就是利用“最大矩形的高一定等于某个柱子的高度”这个关键观察。为什么最大矩形的高一定等于某个柱子的高度因为如果你的矩形高度不贴着任何柱子的顶边那它一定可以继续向上扩展一段距离直到碰到某个柱子的顶边这时候面积会更大。所以考虑每一个柱子让它作为矩形的高度然后向左右扩展直到遇到第一个高度小于它的柱子。这样以该柱子为高的最大矩形就确定了。朴素地做这件事也是 O(n^2)因为每个柱子都要向左右扫描。单调栈的用处就是把“向左右找第一个更矮柱子”这个过程优化到均摊 O(1)。2.2 单调栈解法推导单调栈的思路是维护一个高度单调递增的栈栈里存的是柱子的下标。从左到右遍历每个柱子当当前柱子的高度小于栈顶柱子的高度时说明栈顶柱子的右边界已经出现因为右边已经有一个柱子比它矮了。此时把栈顶柱子出栈它的高就是它自己的高度它的左边界是出栈后新的栈顶位置右边界就是当前遍历到的位置。用一个例子走一遍heights [2,1,5,6,2,3]遍历到下标 0高度 2栈空入栈栈为 [0]。遍历到下标 1高度 1栈顶高度 2 1出栈下标 0。此时高度 2 的柱子左边界是 -1栈空右边界是 1面积 2 * (1 - (-1) - 1) 2。然后当前高度 1 入栈栈为 [1]。遍历到下标 2高度 5栈顶高度 1 5入栈栈为 [1,2]。遍历到下标 3高度 6入栈栈为 [1,2,3]。遍历到下标 4高度 2栈顶高度 6 2出栈下标 3高度 6左边界是 2右边界是 4面积 6 * (4 - 2 - 1) 6。继续栈顶下标 2 高度 5 2出栈下标 2高度 5左边界是 1右边界是 4面积 5 * (4 - 1 - 1) 10。然后当前高度 2 入栈栈为 [1,4]。遍历到下标 5高度 3入栈栈为 [1,4,5]。遍历结束在数组末尾补一个高度为 0 的哨兵柱子强制把栈里剩余元素全部弹出来计算。这里最后一个哨兵非常重要。如果不在末尾补 0栈里会剩下高度 3、2、1 这三根柱子没有计算结果就漏了。代码实现def largest_rectangle_area(heights): stack [] max_area 0 # 末尾补0作为哨兵保证所有柱子最后都能出栈 for i, h in enumerate(heights [0]): while stack and heights[stack[-1]] h: height heights[stack.pop()] left stack[-1] if stack else -1 width i - left - 1 max_area max(max_area, height * width) stack.append(i) return max_area这段代码运行完后max_area 就是最大矩形面积。整体时间复杂度 O(n)因为每个下标最多入栈一次、出栈一次。2.3 代码实现的细节与易错点先说出栈时宽度计算的原理。当栈顶柱子出栈时当前遍历到的位置 i 是它右边第一个比它矮的柱子所以右边界是 i - 1。出栈后新的栈顶如果是 left那么 left 位置的柱子是它左边第一个比它矮的柱子所以左边界是 left 1。宽度就是 (i - 1) - (left 1) 1 i - left - 1。这个公式是单调栈解法的核心建议亲手推导一次不要死记。关于相等高度的处理while 条件用的是而不是。也就是说当遇到和栈顶高度相等的柱子时左边那根相同高度的柱子先不出栈它会等到右边出现一个更矮的柱子时才出栈。这样计算的宽度会把相等高度的柱子都包含进去最终面积不会变小。比如 heights [2,2]如果用第一个 2 会在遇到末尾哨兵 0 时出栈宽度是 2面积为 4正确。如果用第一个 2 在遍历到第二个 2 时就会出栈当时宽度是 1面积是 2虽然第二个 2 后面还会算一次但逻辑会多一层考虑不如干净。还有一个细节是栈里存下标而不是存高度。原因是下标能同时拿到柱子的高度和位置出栈后可以计算宽度。如果只存高度宽度没法算如果只存下标高度可以通过 heights[下标] 拿到。边界情况也要考虑空数组直接返回 0全 0 的数组任何柱子的高度都是 0面积也是 0数组长度为 1那就返回这一个柱子的高度。这些用例在笔试时建议自己先想一遍能有效减少低级失误。3. 字符串计数字典序计数的通用解法3.1 题目描述与思路转换题目描述大意是给定两个仅由小写字母组成的字符串 s1 和 s2以及一个整数 len求长度恰好为 len、只含小写字母、且字典序大于 s1 小于 s2 的字符串个数。结果对 1000007 取模。s1 和 s2 的长度都小于等于 50len 在 1 到 50 之间。第一眼看过去可能会想枚举所有长度为 len 的字符串那有 26^len 种直接爆炸。正确的思路是把问题拆成两个函数写一个count_less(t, length)统计长度恰好为 length 的字符串中字典序严格小于字符串 t 的个数。那么答案就等于count_less(s2, len) - count_less(s1, len)另外如果 s1 本身就是长度恰好为 len 的字符串那还要再减 1因为 s1 本身是合法候选字符串但它不小于自己而我们的目标是“大于 s1”。这里最需要小心的是s1 和 s2 的长度不一定等于 len。字典序比较时如果某个字符串是另一个字符串的前缀短的字符串字典序更小比如 ab abc。所以长度为 len 的候选字符串和长度不足 len 的 s1 比较时情况会比较微妙这也是多数人卡住的点。3.2 小于某个串的数量怎么算核心实现是count_less函数。先明确一点我们要统计的是长度固定为 length 的候选字符串而 t 的长度可能大于、等于或小于 length所以必须先统一处理。如果 t 的长度大于 length那么只需看 t 的前 length 个字符。所有长度 length 且字典序小于这个前缀的字符串显然都小于 t另外恰好等于这个前缀的那个长度为 length 的字符串也比 t 小因为 t 比它长所以要额外加 1。如果 t 的长度等于 length直接统计小于 t 的字符串个数即可。如果 t 的长度小于 length把 t 后面用空字符补齐到 length。这个空字符小于任何小写字母所以所有长度为 length 的候选字符串在 t 耗尽的位置上都会比 t 大这正好对应了字典序中“短前缀更小”的规则。统一之后就得到了一个长度恰为 length 的字符串 TT 里可能包含空字符现在只需要统计字典序严格小于 T 的候选字符串个数。方法是逐位统计对于第 i 位如果 T[i] 是普通小写字母 c那么候选字符串第 i 位可以选择 a 到 c-1 之间任意一个字母共ord(c) - ord(a)种选择后面 length - i - 1 位可以任意填有 26^(length-i-1) 种所以这一位的贡献就是这两个数相乘。然后让第 i 位等于 c继续看下一位。如果 T[i] 是空字符说明 T 已经结束任何候选字符串在这一位都有字符都比 T 大所以直接停止统计。代码实现MOD 1000007 def count_less(t, length): # 统计长度恰好为length的字符串中字典序严格小于t的个数 if len(t) length: # 截断并加上等于截断串的那一个 return count_less_prefix(t[:length]) 1 # 长度不足时用 \0 补齐\0 小于 a padded t \0 * (length - len(t)) return count_less_prefix(padded) def count_less_prefix(T): # T 的长度已经是 length可能包含 \0 total 0 L len(T) for i in range(L): c T[i] if c \0: break cnt ord(c) - ord(a) if cnt: total (total cnt * pow(26, L - i - 1, MOD)) % MOD return total % MOD主流程def solve(): # 牛客常见输入一行包含 s1、s2、len line input().strip().split() s1, s2 line[0], line[1] length int(line[2]) ans count_less(s2, length) - count_less(s1, length) if len(s1) length: ans - 1 print(ans % MOD)这里减法之后必须取模因为count_less(s2) - count_less(s1)可能为负Python 的%会正确处理负数其他语言可能需要(ans MOD) % MOD。3.3 取模、边界与验证示例先验证一个例子s1 as2 clength 2。count_less(c, 2)补齐为 c\0第 0 位 c 的贡献是(c-a) * 26^1 52遇到空字符停止结果 52也就是所有 a? 和 b? 开头的字符串。count_less(a, 2)第 0 位 a 的贡献是 0结果 0。len(s1) 1不等于 2不减 1。答案 52。手动验证长度 2 的字符串大于 a 小于 c 的包含 aa... az 和 ba... bz正好 52 个正确。再看一个容易出错的例子s1 abs2 aclength 3。count_less(ac, 3)补齐为 ac\0第 0 位贡献 0第 1 位 c 贡献(c-a) * 26^1 52结果 52。count_less(ab, 3)第 1 位 b 贡献(b-a) * 26^1 26结果 26。len(s1) 2不等于 3不减 1。答案 26。手动验证大于 ab 小于 ac 的长度 3 字符串第一位必须是 a因为 b?? 已经大于 ac 了第二位必须是 b因为 ab? 都大于 ab 且都小于 ac第三位任意因为第二位 b 已经小于 c所以是 aba 到 abz共 26 个正确。取模的坑主要出现在减法。如果答案是负数直接 print(ans % MOD) 在 Python 里没问题但在 C 或 Java 里要写成(ans % MOD MOD) % MOD否则会输出负数。另外pow(26, 0, MOD)结果是 1这个在代码里要保证不写错指数当 i 走到最后一位时remaining 为 0贡献就是cnt * 1。这道题还有一个容易忽略的点s1 和 s2 的输入可能包含空格或换行读取时要确定输入格式。牛客网上这道题的输入格式是同一行三个值用空格分隔所以input().split()就够了。如果做题平台不同格式可能变成三行写代码前先确认。4. 棋子翻转模拟题也要细心4.1 题目规则与思路我印象里这道题是这样的给定一个棋盘每个格子上有棋子用 0 和 1 表示两种状态。接下来给出一系列翻转操作的坐标每次操作会把该坐标点本身以及它上、下、左、右四个相邻位置的棋子全部翻转0 变 11 变 0。如果某个相邻位置超出棋盘范围就忽略它。最后输出翻转完成后的棋盘状态。这类题在笔试里属于“送分题”但送分题最怕送命。很多人不是不会写而是漏了越界检查或者坐标转换时忘记减一。它的核心思路就是用一个方向数组枚举五个位置然后逐个判断是否在棋盘内在就翻转。如果你愿意多想一步会发现翻转操作是有交换律的因为对每个格子的翻转本质上是累计翻转次数取模 2。也就是说操作顺序不影响最终结果。如果操作次数特别多可以先统计每个格子被翻转的次数最后只需要看奇偶性。但对于一般的笔试数据量直接模拟就足够了。4.2 代码实现def solve(): n int(input()) board [] for _ in range(n): board.append(list(map(int, input().split()))) ops [] try: while True: line input().strip() if not line: break x, y map(int, line.split()) ops.append((x - 1, y - 1)) # 输入坐标从1开始转为0基 except EOFError: pass dirs [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)] for x, y in ops: for dx, dy in dirs: nx, ny x dx, y dy if 0 nx n and 0 ny n: board[nx][ny] ^ 1 for row in board: print( .join(map(str, row)))这里用try...except EOFError来读取不定数量的操作坐标在牛客网的多行测试输入场景下很实用。如果题目在开头