2023 美团笔试题 0429

笔试时间：2023年04月29日春招

第一题

题目：踢皮球

某大学最近正在进行选课。对于学校开设的部分课程，只允许大一至大四中部分年级和部分学院的学生在选课系统中自行选课，年级或学院不符合要求的学生只能通过教务科代为选课。但是不幸的是，各个学院教务科只能帮自己学院的学生选择自己学院开设的课程。此时出现的一个问题是，A学院的小美想请教务处代选B学院开设的课程时，A学院的教务科没有权限将学生添加到B学院开设的课程，因此让小美去找B学院的教务科，B学院的教务科没有权限调取就读A学院学生的个人信息，因此让小美去找A学院的教务科。此时我们说小美被踢皮球了。为了方便处理，可以认为一共有n门课程，编号为1~n；m个学院，编号为1~m 。给出n门可选课程及其开课学院、允许在系统选课的年级和专业，进行q次查询，每次查询给出学生所属学院和待选课程。若可以自行在选课，输出"Help yourself"（不包括引号，下同）；否则若可以由教务处成功代选，输出"Ask for help"；否则说明该学生会被踢皮球，输出"Impossible"。注意：只有年级和学院都不被限制的学生可以自行选课。

输入描述

第一行输入3个正整数n,m,q

第二行输入n个正整数si，表示编号为i的课程的开课学院为si；

接下来4行输入一个4×n的01矩阵f，fij=0表示不允许i年级的学生自行选j课程，fij=1则表示允许；

接下来m行输入一个m×n的01矩阵g，gij=0表示不允许i学院的学生自行选j课程，gij=1则表示允许；

接下来q行，每行输入3个正整数a,b,c ，表示学生所属学院、年级、待选课程。

输出描述

输出共q行，每行一个字符串表示对应查询的结果。

样例输入

5 2 4

1 2 2 1 1

1 0 0 0 0

0 0 1 1 1

0 0 0 0 1

0 0 1 0 1

1 0 0 1 1

0 1 0 0 0

2 2 3

2 3 2

2 3 1

1 2 4

样例输出

Ask for help

Ask for help

Impossible

Help yourself

对第一个查询，3号课程不限制2年级学生自行选课，但限制2号学院的学生选课，因此该学生不能自行选课。幸运的是，3号课程是2号学院开设的课程，因此该学生可以找2号学院教务处帮忙代选。对第二个查询，2号课程不限制2号学院的学生自行选课，但限制3年级学生选课，因此该学生不能自行选课。同样的，2号课程由2号学院开设，可以找2号学院教务处代选。对第三个查询，1号课程限制2号学院和3年级学生自行选课，因此该学生不能自行选课。由于开课学院是1学院，2学院教务科没有添加权限；由于学生学院是2学院，1学院没有查看学生信息的权限，因此该学生被踢皮球。对第四给查询，4号课程不限制1号学院和2年级学生自行选课。

参考题解

模拟

Python：

n, m, q = map(int, input().split())
s = list(map(int, input().split()))
f = [list(map(int, input().split())) for _ in range(4)]
g = [list(map(int, input().split())) for _ in range(m)]
for _ in range(q):
    a, b, c = map(int, input().split())
    if f[b-1][c-1] and g[a-1][c-1]:
        print("Help yourself")
    elif s[c-1] == a:
        print("Ask for help")
    else:
        print("Impossible")

第二题

题目：限行

在小美的城市，为了保证交通顺畅，在周一至周日的每一天都会对部分车辆限行。例如周一不允许车牌号最后一个数字为0、1、2的车辆出行，周二不允许车牌号最后一个数字为3、4、5的车辆出行……然而小美是个有钱人，因此她决定多买几辆车，以保证她每天都至少有一辆车可以出行。假设小美可以任意选择车牌号的最后一位数字，请你告诉她至少需要买几辆车？如果小美无法达到目标，输出-1即可。

输入描述

输入共7行，表示周一至周日的限行情况。

每行第一个数字ci表示当天限行数字个数，随后输入ci 个互不相同的数字aij，表示限行数字。

对于所有的数据，0≤ci≤10, 0≤aij≤9。

输出描述

一行，输出一个整数，表示小美需要的最少车辆数或小美不能保证每天都至少有一辆车可以出行。

样例输入

8 0 1 2 3 4 5 6 7

8 1 2 3 4 5 6 7 8

8 2 3 4 5 6 7 8 9

8 0 1 2 3 4 5 8 9

8 0 1 2 3 6 7 8 9

8 0 1 4 5 6 7 8 9

8 2 3 4 5 6 7 8 9

样例输出

5

一种可能的方案是，选购最后车牌一位数字分别为0,2,4,6,8的5辆车，此时每天都有车辆可以出行。

参考题解

Python：

from math import inf

days = []
for _ in range(7):
    days.append(set([int(c) for c in input().split(" ")[1:]]))

cars = set(range(10))

res = inf
def dfs(i,chio):
    if i == 7:
        if len(chio) > 0:
            global res
            res = min(res, len(chio))
        return
    cur = cars - days[i]
    for j in cur:
        if j not in chio:
            chio.add(j)
            dfs(i + 1, chio)
            chio.remove(j)
        else:
            dfs(i+1,chio)

dfs(0, set())
if res == inf: print(-1)
else: print(res)

第三题

题目：超辣火锅

小美和她的朋友们共n人决定挑战超辣火锅，以决出最能吃辣的人。他们顺时针围成一圈，假设标号为1到n。从1号开始，每一次从当前的人顺时针数k个，然后这个人吃一口超辣火锅。第i个人对辣椒的耐受值为ai, 意味着当他吃了ai口火锅后将因无法忍受而离席（每次数k个人时，离席的人不算入其中，详见样例解释）。请你依次输出离席的人的编号。