美团笔试 美团秋招 美团笔试题 1011
笔试时间：2025年10月11日
往年笔试合集：
第一题
给定一个长度为n、由大小写字母组成的字符串s（下标从1开始）。存在一个计数器x，初始x=1。你需要按下标从小到大的顺序，依次对每个下标i执行如下操作：
- 若i+x≤n且s[i+x]为大写字母，则将s[i+x]修改为小写字母，然后将x增加1；同时，若s[i]为小写字母，则将s[i]修改为大写字母。
- 若不满足上述条件，则本次不进行任何修改。
请输出全部操作结束后的字符串。
输入描述
第一行输入一个整数n（1≤n≤10^5），表示字符串长度。 第二行输入一个长度为n、仅由大小写字母组成的字符串s。
输出描述
在一行上输出一个长度为n的字符串，表示全部操作结束后的结果。
样例输入
4
abcX
样例输出
abCx
样例说明1： 初始x=1。当i=1,2,3时对应的字符均不满足大写，当i=4时，4+1=5>4不满足条件。当i=3时，3+1=4且s[4]='X'为大写，故将其改为小写'x'，x增加为2；同时s[3]='c'为小写，改为大写'C'；其他位置不触发条件，不进行修改，最终得到"abCx"。
参考题解
解题思路： 操作顺序性：必须按i=1,2,3,...的顺序处理，因为x的变化会影响后续的判断。条件判断：只有当i+x≤n且s[i+x]是大写字母时，才会触发修改操作。双重修改：触发条件后，会同时修改两个位置：i+x位置（大写→小写），i位置（小写→大写，如果原本是小写）。
C++：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
// Convert to 1-indexed
s = " " + s;
int x = 1;
for (int i = 1; i <= n; i++) {
int target_idx = i + x;
bool condition = (target_idx <= n) && (s[target_idx] >= 'A' && s[target_idx] <= 'Z');
if (condition) {
// Convert target to lowercase
s[target_idx] = s[target_idx] + 32;
x++;
// If current is lowercase, convert to uppercase
if (s[i] >= 'a' && s[i] <= 'z') {
s[i] = s[i] - 32;
}
}
}
// Output without the first space
cout << s.substr(1) << endl;
return 0;
}
Java：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = sc.next();
// Convert to character array for easy manipulation
char[] arr = (" " + s).toCharArray();
int x = 1;
for (int i = 1; i <= n; i++) {
int targetIdx = i + x;
boolean condition = (targetIdx <= n) && (arr[targetIdx] >= 'A' && arr[targetIdx] <= 'Z');
if (condition) {
// Convert target to lowercase
arr[targetIdx] = (char)(arr[targetIdx] + 32);
x++;
// If current is lowercase, convert to uppercase
if (arr[i] >= 'a' && arr[i] <= 'z') {
arr[i] = (char)(arr[i] - 32);
}
}
}
// Output without the first space
System.out.println(new String(arr, 1, n));
}
}
Python：
import sys
def solve():
n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
a = [''] + list(s)
x = 1
for i in range(1, n + 1):
target_idx = i + x
condition = (target_idx <= n) and ('A' <= a[target_idx] <= 'Z')
if condition:
a[target_idx] = chr(ord(a[target_idx]) + 32)
x += 1
if 'a' <= a[i] <= 'z':
a[i] = chr(ord(a[i]) - 32)
res = "".join(a[1:])
print(res)
solve()
第二题：好数变换
小美定义一个正整数是好的，当且仅当其十进制表示中仅包含一个非零有效位，例如4000、9、20都是好的数，而110、301、6666不是好的数，非正整数也不是好的数；给定一个长度为n的正整数数组a，你可以对数组执行若干次以下三种操作中的一种：
- 选择一个索引i，将a[i]增加1；
- 选择一个索引i，如果a[i]>1，则将a[i]减少1；
- 选择一个索引i，如果a[i]是10的整数倍，则将a[i]除以10，否则该操作无效；
输出将数组中所有元素都变为好的数所需的最少操作次数。
输入描述
第一行输入一个整数n（1≤n≤10^5），表示数组的长度； 第二行输入n个整数a[i]（1≤a[i]≤200000），表示数组的初始元素。
输出描述
输出一个整数，表示将数组中所有元素都变为好的数的最少操作次数。
样例输入
3
1 2 3
样例输出
0
参考题解
解题思路： 这道题的关键在于反向思考：不是从初始值出发寻找变成好数的最少操作，而是从所有好数出发，计算到达每个数的最少操作次数。通过BFS从所有好数出发，可以一次性计算出到达所有数字的最少操作次数。操作的反向理解：加1操作←→从当前数减1；减1操作←→从当前数加1；除以10操作←→从当前数乘以10。
C++：
#include <bits/stdc++.h>
using namespace std;
bool isGood(int x) {
if (x <= 0) return false;
int temp = x;
int powerOf10 = 1;
while (temp >= 10) {
temp /= 10;
powerOf10 *= 10;
}
return x == temp * powerOf10;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
const int MAX_A = 200000;
vector<int> dist(MAX_A + 1, INT_MAX);
queue<int> q;
// Initialize all good numbers
for (int i = 1; i <= MAX_A; i++) {
if (isGood(i)) {
dist[i] = 0;
q.push(i);
}
}
// BFS
while (!q.empty()) {
int u = q.front();
q.pop();
int d = dist[u];
// Operation 1: multiply by 10 (reverse of divide by 10)
long long v1 = (long long)u * 10;
if (v1 <= MAX_A && d + 1 < dist[v1]) {
dist[v1] = d + 1;
q.push(v1);
}
// Operation 2: subtract 1 (reverse of add 1)
int v2 = u - 1;
if (v2 >= 1 && d + 1 < dist[v2]) {
dist[v2] = d + 1;
q.push(v2);
}
// Operation 3: add 1 (reverse of subtract 1)
int v3 = u + 1;
if (v3 <= MAX_A && d + 1 < dist[v3]) {
dist[v3] = d + 1;
q.push(v3);
}
}
int ans = 0;
for (int x : a) {
if (x <= MAX_A) {
ans += dist[x];
}
}
cout << ans << endl;
return 0;
}
Java：
import java.util.*;
public class Main {
static boolean isGood(int x) {
if (x <= 0) return false;
int temp = x;
int powerOf10 = 1;
while (temp >= 10) {
temp /= 10;
powerOf10 *= 10;
}
return x == temp * powerOf10;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
final int MAX_A = 200000;
int[] dist = new int[MAX_A + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
Queue<Integer> q = new LinkedList<>();
// Initialize all good numbers
for (int i = 1; i <= MAX_A; i++) {
if (isGood(i)) {
dist[i] = 0;
q.offer(i);
}
}
// BFS
while (!q.isEmpty()) {
int u = q.poll();
int d = dist[u];
// Operation 1: multiply by 10
long v1 = (long)u * 10;
if (v1 <= MAX_A && d + 1 < dist[(int)v1]) {
dist[(int)v1] = d + 1;
q.offer((int)v1);
}
// Operation 2: subtract 1
int v2 = u - 1;
if (v2 >= 1 && d + 1 < dist[v2]) {
dist[v2] = d + 1;
q.offer(v2);
}
// Operation 3: add 1
int v3 = u + 1;
if (v3 <= MAX_A && d + 1 < dist[v3]) {
dist[v3] = d + 1;
q.offer(v3);
}
}
int ans = 0;
for (int x : a) {
if (x <= MAX_A) {
ans += dist[x];
}
}
System.out.println(ans);
}
}
Python：
import sys
from collections import deque
def solve():
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
MAX_A = 200000
inf = float('inf')
dist = [inf] * (MAX_A + 1)
q = deque()
def is_good(x):
if x <= 0:
return False
temp = x
power_of_10 = 1
while temp >= 10:
temp //= 10
power_of_10 *= 10
return x == temp * power_of_10
for i in range(1, MAX_A + 1):
if is_good(i):
dist[i] = 0
q.append(i)
while q:
u = q.popleft()
d = dist[u]
v1 = u * 10
if v1 <= MAX_A and d + 1 < dist[v1]:
dist[v1] = d + 1
q.append(v1)
v2 = u - 1
if v2 >= 1 and d + 1 < dist[v2]:
dist[v2] = d + 1
q.append(v2)
v3 = u + 1
if v3 <= MAX_A and d + 1 < dist[v3]:
dist[v3] = d + 1
q.append(v3)
ans = 0
for x in a:
if x <= MAX_A:
ans += dist[x]
print(ans)
solve()
第三题：最长上升子序列计数
给定一个长度为n的数组a，请你计算其中所有本质不同最长上升子序列的数量。由于答案可能非常大，请将结果对998244353取模后输出。
【子序列】如果一个序列可以通过删除原序列的若干（可能为零）元素得到，则称前者为后者的一个子序列。【上升序列】我们称b为一个上升序列，当且仅当其中任意相邻元素满足b[i]<b[i+1]。【本质不同序列】若两个序列的长度不同，或在某一位置上的元素不同，则认为它们是不同的序列。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数T（1≤T≤10）代表数据组数，每组测试数据描述如下：
第一行输入一个正整数n（1≤n≤5000），代表数组a的长度。
第二行输入n个正整数a[i]（1≤a[i]≤10^9），代表a中的元素。
除此之外，保证单个测试文件的n之和不超过5000。
输出描述
对于每组测试数据，输出一行一个整数，代表数组a中本质不同最长上升子序列的数量，对998244353取模后的结果。
样例输入
5
1
1
2
1 1
6
1 1 4 5 1 4
7
3 2 2 4 5 8 7
7
1 9 1 9 8 1 0
样例输出
1
1
1
4
2
样例说明： 在最后一组测试数据中，两个本质不同最长上升子序列分别为[1,9]和[0,1,9]。
参考题解
解题思路： 解决这个问题需要分两步走：1.计算最长上升子序列的长度：使用动态规划结合线段树，快速求出以每个位置结尾的最长上升子序列长度。2.统计本质不同的最长上升子序列数量：在已知长度的基础上，通过另一棵线段树维护不同长度对应的方案数，并避免重复计数。
C++：
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
class SegTreeMax {
public:
int n;
vector<int> tree;
SegTreeMax(int n) : n(n), tree(4 * n, 0) {}
void update(int pos, int val, int node = 1, int start = 1, int end = -1) {
if (end == -1) end = n;
if (start == end) {
tree[node] = max(tree[node], val);
return;
}
int mid = (start + end) / 2;
if (pos <= mid) update(pos, val, node * 2, start, mid);
else update(pos, val, node * 2 + 1, mid + 1, end);
tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
int query(int l, int r, int node = 1, int start = 1, int end = -1) {
if (end == -1) end = n;
if (l > end || r < start) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return max(query(l, r, node
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
投递上海得物信息集团有限公司等公司10个岗位
查看2道真题和解析