美团 · 模拟 · 算法编程题
美团 模拟 n ≤ 200000 时限 1 秒 / 256 MB

题目描述

小美有一个长度为 n ，仅由大小写英文字母组成的字符串 s 。小美将对字符串执行以下 m 次操作：
当操作类型 op=1 且给定两个小写字母 letter1,letter2 （满足 letter1≤ letter2 ）时，将字符串中所有位于字母表中 [letter1,letter2] 的小写字母转换为对应的大写字母；
当操作类型 op=2 且给定两个大写字母 letter1,letter2 （满足 letter1≤ letter2 ）时，将字符串中所有位于字母表中 [letter1,letter2] 的大写字母转换为对应的小写字母。

输入输出

输入描述
在一行上输入两个整数 n,m(1≤ n,m≤ 2×10^5) ，分别表示字符串长度和操作次数；
在一行上输入一个长度为 n ，仅由大小写英文字母组成的字符串 s ；
接下来 m 行，每行输入三个元素：整数 op 和两个字符 letter1,letter2 ，满足：
若 op=1 ，则 letter1,letter2 为小写字母，且 letter1≤ letter2 ；
若 op=2 ，则 letter1,letter2 为大写字母，且 letter1≤ letter2 。
输出描述
输出执行完所有操作后得到的最终字符串。

样例共 2 组

样例 1 · 在此样例中，初始字符串 "abc" ，将区间 [a,c] 的小写字母统一转换成大写，得到 "ABC" 。
输入
3 1
abc
1 a c
输出
ABC
样例 2 · 在此样例中， 第一次操作将字符串中所有满足字母表区间 [a,b] 所有小写字母的变为大写字母，得到 "AABBcC" ； 第二次操作将字符串中所有满足字母表区间 [B,C] 所有大写字母的变为小写字母，最终得到 "AAbbcc" 。
输入
6 2
aAbBcC
1 a b
2 B C
输出
AAbbcc

算法解析依据充分

考点：字符串 · 模拟

数据规模 n ≤ 200000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 200000，m ≤ 200000
  • 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：模拟

不涉及复杂算法，把题目描述的流程原样翻译成代码逐步执行即可。

思路框架（模拟 通法 · 非本题专属）

  1. 用变量记录题目要求的「状态」（当前值、剩余数量、当前位置等）。
  2. 按题面给出的顺序，把每一步操作写成一段代码，逐条执行。
  3. 每一步执行后更新状态，并在题目要求的位置输出或累计答案。
  4. 注意循环的边界：执行多少次、何时终止、是否能终止。

实现要点：结构上通常是一个外层循环包住若干 if/else 分支；只要状态定义清楚，正确率很高。

复杂度：时间 O(操作次数) ｜ 空间 O(状态数)

该范式的通法易错点

  • 终止条件写错导致死循环或漏做最后一次操作。
  • 状态更新顺序颠倒（先改了下标又用旧下标）。
  • 题目里「最多 / 恰好 / 至少」的语义差别没区分。

对照本题

  • 数据规模 n ≤ 200000，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。

样例解读

样例 1：输入 3 1 / abc / 1 a c → 输出 ABC

在此样例中，初始字符串 "abc" ，将区间 [a,c] 的小写字母统一转换成大写，得到 "ABC" 。

样例 2：输入 6 2 / aAbBcC / 1 a b / 2 B C → 输出 AAbbcc

在此样例中，

第一次操作将字符串中所有满足字母表区间 [a,b] 所有小写字母的变为大写字母，得到 "AABBcC" ；

第二次操作将字符串中所有满足字母表区间 [B,C] 所有大写字母的变为小写字母，最终得到 "AAbbcc" 。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-美团-测试岗-第一批笔试；2025年秋招-美团-运维&安全岗-第一批笔试；2025年秋招-美团-算法策略端-第一批笔试 等。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解