3.25美团算法笔试

a了3.18，那个0.18自认为思路没问题，自测也没问题，不知道为什么只对了0.18

python版本代码如下：

第一题

数火车，其实就是一个栈，给一个入栈顺序，一个出栈顺序，问你这种情况是不是可能的

T = int(input())

for _ in range(T):

    flag = True

    n = int(input())

    x_list = list(map(int, input().split()))

    y_list = list(map(int, input().split()))

    def is_possible_order(x_list, y_list):

        stack = []

        i = 0

        for x in y_list:

            while not stack or stack[-1] != x:

                if i == len(x_list):

                    return False

                stack.append(x_list[i])

                i += 1

            stack.pop()

        return True if not stack else False

    flag = is_possible_order(x_list, y_list)

    if flag is True:

        print('Yes')

    else:

        print('No')

第二题

糖果美味值

经典动态规划，就是看现在这个选不选。这个选了，意味着前两个都不能选了，所以是a[i]+dp[i-3]，如果不选，那就等于选到前面为止的美味值即dp[i-1]

n = int(input())

a = [int(x) for x in input().split()]

dp = [0] * n

dp[0] = a[0]

dp[1] = max(a[1], a[0])

dp[2] = max(a[2], a[0], a[1])

for i in range(3,n):

    dp[i] = max(dp[i-3] + a[i], dp[i-1])

print(dp[n-1])

第三题

也是很经典的动态规划，就是不知道为什么只a了18%，这个dp就是现在能拿几块巧克力，dp[?]这个？是当前背包的容量，每选一个，就要减去当前巧克力的重量（cho[i]^2），同时多一个巧克力

import sys

n, m = map(int, sys.stdin.readline().strip().split())

cho = list(map(int, sys.stdin.readline().strip().split()))

ask = list(map(int, sys.stdin.readline().strip().split()))

bagsize = max(ask)

dp = [0] * (bagsize + 1)

for i in range(n):

    for j in range(bagsize, cho[i] * cho[i]-1, -1):

        dp[j] = max(dp[j], dp[j-cho[i] * cho[i]] + 1)

res = []

for i in range(m):

    print(dp[ask[i]])

第四题

给一个字符串，以分号分割。每个key=value当做一个键值对存到字典里。给一串字符串查找，如果没有这个key输出empty，如果有一个就输出value，如果有多个就输出最新的（可以直接覆盖，这样找到的就是最新的）。唯一要注意的就是直接按照“;”分割会导致最后多一个空字符串，删了就可以

S = list(input().strip().split(';'))[:-1]

dic_ = {}

for i in S:

    left, right = i.split('=')

    dic_[left] = right

q = int(input())

for _ in range(q):

    q_str = input().split()

    if q_str[0] not in dic_:

        print('EMPTY')

    else:

        print(dic_[q_str[0]])