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