美团笔试 美团实习 0325
笔试时间：2023年3月25日
第一题
题目：火车迷
小美是一个火车迷。最近她在观察家附近火车站的火车驶入和驶出情况，发现火车驶入和驶出的顺序并不一致。经过小美调查发现，原来这个火车站里面有一个类似于栈的结构，如下图所示：
例如可能1号火车驶入了火车站中的休息区s，在驶出之前2号火车驶入了。那么在这种情况下，1号火车需要等待2号火车倒车出去后才能出去（显然被后面驶入的2号火车挡住了，这个休息区s只有一个出入口）。出于好奇，小美统计了近些天的火车驶入驶出情况，开始统计和结束统计时休息区s中均是空的。由于中途疏忽，小美觉得自己好像弄错了几个驶入驶出顺序，想请你帮她验证一下。值得注意的是，小美虽然可能弄错了顺序，但对火车的记录是不重不漏的。形式化地来形容休息区s，我们视其为一个容量无限大的空间，假设两列火车 i 和 j 同时处于休息区s中，驶入时刻Tin满足Tin(i)<Tin(j)，则驶出时间Tout必定满足Tout(i)>Tout(j)，即，先进后出。
输入描述
第一行一个整数T表示数据组数。
对每组测试而言：
第一行一个整数n，表示观察到的火车数量。
第二行n个整数x1,x2,...,xn，表示小美记录的火车驶入休息区s的顺序。
第三行n个整数y1,y2,...,yn，表示小美记录的火车驶出休息区s的顺序。
1≤T≤10,1≤n≤50000,1≤xi,yi≤n, 且{xn} 、{yn} 均为{1,2,3,...,n}的一个排列，即1~n这n个数在其中不重不漏恰好出现一次。
输出描述
对每组数据输出一行：如果小美记录的驶入和驶出顺序无法被满足则输出No，否则输出Yes。
示例输入
3
3
1 2 3
1 2 3
3
1 2 3
3 2 1
3
1 2 3
3 1 2
示例输出
Yes
Yes
No
提示
对第一组数据：每辆火车刚驶入便立刻驶出即可满足此记录。
对第二组数据：
[ <- 休息区出口 （空 初始状态）
[1 <- 休息区出口 （1号驶入）
[1 2 <- 休息区出口 （2号驶入）
[1 2 3 <- 休息区出口 （3号驶入）
[1 2 <- 休息区出口 （3号驶出）
[1 <- 休息区出口 （2号驶出）
[ <- 休息区出口 （1号驶出）
记录可以被此种方案满足。
对第三组数据：
[ <- 休息区出口 （空 初始状态）
[1 <- 休息区出口 （1号驶入）
[1 2 <- 休息区出口 （2号驶入）
[1 2 3 <- 休息区出口 （3号驶入）
[1 2 <- 休息区出口 （3号驶出）
发现1号被2号堵住，无法先于2号驶出。可以证明，亦不存在其他驶入驶出方案使得第三组数据满足要求。
参考题解
我们可以使用栈这个数据结构来模拟火车驶入驶出的过程
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
bool isValidTrainSequence(vector<int>& in_sequence, vector<int>& out_sequence) {
stack<int> stk;
int in_index = 0, out_index = 0;
while (out_index < out_sequence.size()) {
while (stk.empty() || (stk.top() != out_sequence[out_index])) {
if (in_index < in_sequence.size()) {
stk.push(in_sequence[in_index]);
in_index++;
} else {
return false;
}
}
stk.pop();
out_index++;
}
return true;
}
int main() {
int T;
cin >> T;
for (int _ = 0; _ < T; ++_) {
int n;
cin >> n;
vector<int> in_sequence(n), out_sequence(n);
for (int i = 0; i < n; ++i) {
cin >> in_sequence[i];
}
for (int i = 0; i < n; ++i) {
cin >> out_sequence[i];
}
if (isValidTrainSequence(in_sequence, out_sequence)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static boolean isValidTrainSequence(int[] inSequence, int[] outSequence) {
Stack<Integer> stack = new Stack<>();
int inIndex = 0, outIndex = 0;
while (outIndex < outSequence.length) {
while (stack.empty() || (stack.peek() != outSequence[outIndex])) {
if (inIndex < inSequence.length) {
stack.push(inSequence[inIndex]);
inIndex++;
} else {
return false;
}
}
stack.pop();
outIndex++;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
for (int _ = 0; _ < T; ++_) {
int n = scanner.nextInt();
int[] inSequence = new int[n];
int[] outSequence = new int[n];
for (int i = 0; i < n; ++i) {
inSequence[i] = scanner.nextInt();
}
for (int i = 0; i < n; ++i) {
outSequence[i] = scanner.nextInt();
}
if (isValidTrainSequence(inSequence, outSequence)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
}
第二题
题目：分糖
小美因乐于助人的突出表现获得了老师的嘉奖。老师允许小美从一堆n个编号分别为1,2,...,n的糖果中选择任意多个糖果作为奖励（每种编号的糖果各一个），但为了防止小美一次吃太多糖果有害身体健康，老师设定了一个限制：如果选择了编号为 i 的糖果，那么就不能选择编号为 i-1, i-2, i+1, i+2的四个糖果了。在小美看来，每个糖果都有一个对应的美味值，小美想让她选出的糖果的美味值之和最大！作为小美的好朋友，请你帮帮她！
输入描述
第一行一个整数n，表示糖果数量。
第二行n个整数a1,a2,...,an，其中ai表示编号为 i 的糖果的美味值。
1≤n≤50000 , 1≤ai≤10000
输出描述
输出一行一个数，表示小美能获得的糖果美味值之和最大值。
示例输入
7
3 1 2 7 10 2 4
示例输出
14
参考题解
动态规划，类似打家劫舍
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <algorithm>
const int mxn = 50001;
std::vector<int> a(mxn);
std::vector<int> dp(mxn, -1);
int dfs(int i, int n) {
if (i > n) {
return 0;
}
if (dp[i] != -1) {
return dp[i];
}
dp[i] = std::max(dfs(i + 1, n), dfs(i + 3, n) + a[i]);
return dp[i];
}
int main() {
int n;
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}
std::cout << dfs(0, n) << std::endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
public class Main {
static final int mxn = 50001;
static int[] a = new int[mxn];
static int[] dp = new int[mxn];
static int dfs(int i, int n) {
if (i > n) {
return 0;
}
if (dp[i] != -1) {
return dp[i];
}
dp[i] = Math.max(dfs(i + 1, n), dfs(i + 3, n) + a[i]);
return dp[i];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt();
}
for (int i = 0; i < mxn; i++) {
dp[i] = -1;
}
System.out.println(dfs(0, n));
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
mxn = 50001
a = [0] * mxn
dp = [-1] * mxn
def dfs(i):
if i > n:
return 0
if dp[i] != -1:
return dp[i]
dp[i] = max(dfs(i + 1), dfs(i + 3) + a[i])
return dp[i]
n = int(input())
for i in range(1, n + 1):
a[i] = int(input())
print(dfs(0))
第三题
暂缺失
第四题
题目：解释器
小美因为自己差劲的表达能力而苦恼，小美想制作一个解释器，这样她可以在无法表达的情况下让解释器帮她解释。好巧不巧小美翻开了编译原理的书，找到了解释器的制作方式，她决定先制作一个书上习题中描述的小小解释器试试。小美需要读入一行字符串，其格式为"key1=val1; key2=val2; ...; keyn-1=valn-1; keyn=valn;"(不包含引号)这样的n对key,value对，其中keyi和vali为第 i 对key,value对，且均为仅包含大小写英文字母、数字与斜杠的非空字符串。例如对于字符串"SHELL=/bin/bash;HOME=/home/xiaomei;LOGNAME=xiaomei;"，那么其中包含三对key,value对，以(key,value)形式展示，分别为(SHELL,/bin/bash)、(HOME,/home/xiaomei)、(LOGNAME,xiaomei)。
接下来，小美的解释器需要接受q次询问，每次询问给出一个仅包含大小写英文字母、数字与斜杠的非空字符串，如果存在某对key,value对的key值与之相同，那么输出对应的value；如果存在多对key,value对的key值与之相同，那么输出其中编号最大的，也即最后那一对的value值；如果一对也不存在，那么输出EMPTY。
输入描述
第一行一个字符串S，满足题中所述格式。
接下来一个整数q，表示有q个询问。
接下来q行，每行一个仅包含大小写英文字母、数字与斜杠的非空字符串，分别为S1,S2,...,Sq，依次表示q次询问。
令|S|表示字符串S的长度。
输出描述
输出q行，每行一个字符串表示答案。
示例输入
LOGNAME=default;SHELL=/bin/bash;HOME=/home/xiaomei;LOGNAME=xiaomei;
4
SHELL
HOME
LOGNAME
logname
示例输出
/bin/bash
/home/xiaomei
xiaomei
EMPTY
提示：
第3个询问有两对满足，分别是第1对和第4对，选择编号大的（也就是后者），为xiaomei而不是default。第4个询问不存在满足的，输出EMPTY。
参考题解
模拟题
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
string s;
getline(cin, s);
int q;
cin >> q;
cin.ignore(); // Clear the newline character left in the buffer
unordered_map<string, string> pairs_dict;
size_t start = 0;
while (start < s.size()) {
size_t end = s.find(';', start);
if (end == string::npos) {
end = s.size();
}
string pair = s.substr(start, end - start);
if (!pair.empty()) {
size_t eq_pos = pair.find('=');
if (eq_pos != string::npos) {
string key = pair.substr(0, eq_pos);
string value = pair.substr(eq_pos + 1);
pairs_dict[key] = value;
}
}
start = end + 1;
}
for (int i = 0; i < q; ++i) {
string query;
getline(cin, query);
cout << pairs_dict[query] << endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int q = scanner.nextInt();
scanner.nextLine(); // Consume the newline character left in the buffer
HashMap<String, String> pairsDict = new HashMap<>();
int start = 0;
while (start < s.length()) {
int end = s.indexOf(';', start);
if (end == -1) {
end = s.length();
}
String pair = s.substring(start, end).trim();
if (!pair.isEmpty()) {
int eqPos = pair.indexOf('=');
if (eqPos != -1) {
String key = pair.substring(0, eqPos).trim();
String value = pair.substring(eqPos + 1).trim();
pairsDict.put(key, value);
}
}
start = end + 1;
}
for (int i = 0; i < q; ++i) {
String query = scanner.nextLine().trim();
System.out.println(pairsDict.getOrDefault(query, "EMPTY"));
}
}
}
第五题
题目：糖果盛宴
小美特别爱吃糖果。小美家楼下正好有一个糖果专卖店，每天供应不同种类的糖果。小美预先拿到了糖果专卖店接下来n天的进货计划表，并针对每天的糖果种类标注好了对小美而言的美味值。小美当然想每天都能去买糖果吃，不过由于零花钱限制（小美零花钱并不多！）以及健康考虑，小美决定原则上如果今天吃了，那么明天就不能吃。但小美认为凡事都有例外，所以她给了自己k次机会，在昨天已经吃了糖果的情况下，今天仍然连续吃糖果！简单来说，小美每天只能吃一次糖果，原则上如果昨天吃了糖果那么今天就不能吃，但有最多k次机会打破这一原则。小美不想浪费每次吃糖果的机会，所以请你帮帮她规划一下她的吃糖果计划，使得她能吃到的糖果美味值最大。
输入描述
第一行两个整数n和k，表示拿到的进货计划表的天数和最多打破原则的次数。
第二行n个整数a1,a2,...,an，其中ai表示接下来第 i 天糖果专卖店的糖果的美味值。
1≤n≤2000,1≤k≤1000,1≤ai≤10000
输出描述
输出一行一个数，表示小美能吃到的糖果美味值之和最大值。
示例输入
7 1
1 2 3 4 5 6 7
示例输出
19
参考题解
最优的方案是选择选择第2、4、6天吃糖果，并在第7天打破一次原则也吃糖果（因为第6天已经吃过，原则上不能继续吃，需要使用一次打破原则的机会）。
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
public class Main {
static int n, k;
static int[] a;
static int[][] dp;
static int dfs(int i, int j) {
if (i >= n) return 0;
if (dp[i][j] != -1) return dp[i][j];
int cur = dfs(i + 1, j);
cur = Math.max(cur, dfs(i + 2, j) + a[i]);
if (j >= 1) cur = Math.max(cur, dfs(i + 1, j - 1) + a[i]);
dp[i][j] = cur;
return dp[i][j];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
k = scanner.nextInt();
a = new int[2010];
dp = new int[2001][1001];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j] = -1;
}
}
System.out.println(dfs(0, k));
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def dfs(i, j):
if i >= n:
return 0
if dp[i][j] != -1:
return dp[i][j]
cur = dfs(i + 1, j)
cur = max(cur, dfs(i + 2, j) + a[i])
if j >= 1:
cur = max(cur, dfs(i + 1, j - 1) + a[i])
dp[i][j] = cur
return dp[i][j]
n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = [[-1] * 1001 for _ in range(2001)]
print(dfs(0, k))
#美团笔试##美团实习#
