笔试时间：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::