美团笔试 美团软件算法笔试4-29

订阅专栏，方便查阅，时刻更新各厂软件算法笔试https://blog.nowcoder.net/zhuanlan/0oDWVm

题目1：踢皮球

某大学最近正在进行选课。对于学校开设的部分课程，只允许大一至大四中部分年级和部分学院的学生在选课系统中自行选课，年级或学院不符合要求的学生只能通过教务科代为选课。但是不幸的是，各个学院教务科只能帮自己学院的学生选择自己学院开设的课程。   此时出现的一个问题是，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

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }

    vector<vector<int> > f(4, vector<int>(n));
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> f[i][j];
        }
    }

    vector<vector<int> > g(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }

    for (int i = 0; i < q; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (f[b - 1][c - 1] && g[a - 1][c - 1]) {
            cout << "Help yourself" << endl;
        } else if (s[c - 1] == a) {
            cout << "Ask for help" << endl;
        } else {
            cout << "Impossible" << endl;
        }
    }

    return 0;
}

题目2：限行

在小美的城市，为了保证交通顺畅，在周一至周日的每一天都会对部分车辆限行。例如周一不允许车牌号最后一个数字为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

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <sstream>
#include <limits>

using namespace std;

vector<set<int>> days(7);
set<int> cars = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int res = numeric_limits<int>::max();

void dfs(int i, set<int>& chio) {
    if (i == 7) {
        if (!chio.empty()) {
            res = min(res, static_cast<int>(chio.size()));
        }
        return;
    }
    set<int> cur;
    for (int j : cars) {
        if (days[i].find(j) == days[i].end()) {
            cur.insert(j);
        }
    }
    for (int j : cur) {
        if (chio.find(j) == chio.end()) {
            chio.insert(j);
            dfs(i + 1, chio);
            chio.erase(j);
        } else {
            dfs(i + 1, chio);
        }
    }
}

int main() {
    for (int i = 0; i < 7; ++i) {
        string line;
        getline(cin, line);
        istringstream iss(line);
        int c;
        iss >> c; // discard the first number
        while (iss >> c) {
            days[i].insert(c);
        }
    }

    set<int> chio;
    dfs(0, chio);

    if (res == numeric_limits<int>::max()) {
        cout << -1 << endl;
    } else {
        cout << res << endl;
    }

    return 0;
}

题目3：超辣火锅

小美和她的朋友们共n人决定挑战超辣火锅，以决出最能吃辣的人。他们顺时针围成一圈，假设标号为