【备战秋招】每日一题:4月29日美团春招第一题:题面+题目思路 + C++/python/js/Go/java带注释_美团2024年春招第一场笔试【算法策略】

作者：代码探险家 | 2024-07-09 11:33:04

踩

美团2024年春招第一场笔试【算法策略】

为了更好的阅读体检，为了更好的阅读体检，，可以查看我的算法学习博客第一题-选修课

在线评测链接:P1266

题目内容

某大学一共有 n 门课程，编号为 1 ~ n ， m 个学院，编号为1 ~ m 。最近开学季，很多学院都开放了选课窗口，但是很多课程在选课窗口也不一定能选择上，因为课程没有给某些学生开放选择权限，但是学生可以去找教务处帮忙选择该课程。

也就是说，如果塔子哥是计算机学院的一名学生，如果他可以选择计算机学院的一个课程，但是该课程没有开放权限让他选，他可以去找计算机学院的教务处帮忙选课，如果开放了权限，他就可以自己选课。但是如果塔子哥可以选择电气工程学院的一个课程，如果该课程没有开放权限，他就算是去找电气工程学院的教务处，这个教务处也无法帮塔子哥选课，因为塔子哥不是电气工程学院的学生，但如果该课程开放了权限，那么塔子哥就可以自己选课了。

因为这些过程自己一门门课程去想，很麻烦，所以学校想请你帮学生们制作一个能快速判断自己选课情况的程序，你能帮学校编写这个程序吗？

学校给出 n 门可选课程及其开课学院、允许在系统选课的年级和专业，进行 q 次查询，每次查询给出学生所属学院和待选课程，请你帮这些学生判断他们是否能选择该课程，如果能选，他应该怎样去选课。

若可以自行在选课，输出 Help yourself ，否则若可以由教务处成功代选，输出 Ask for help ，否则说明该学生无法选择该门课程，输出 Impossible 。

注意：

只有年级和学院都不被限制的学生可以自行选课。

输入描述

第一行输入为 3 个正整数 $n , m , q (1 \leq n , m \leq 10 , 1 \leq q \leq 1000)$ ；

第二行输入 n 个正整数 $s_i(1 \leq s_i \leq 10)$ ，表示编号为 i 的课程的开课学院为 $s_i$ ；

接下来 4 行输入一个 4×n 的 01矩阵 f ， $f_{ij}=0$ 表示没给 i 年级的学生开放选 j 课程的权限， $f_{ij}=1$ 则表示开放了；

接下来 m 行输入一个 $m\times n$ 的 01 矩阵 g ， $g_{ij}=0$ 表示没给 i 学院的学生开放自行选 j 课程的权限， $g_{ij}=1$ 则表示开放了；

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

输出描述

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

样例

输入

输出

Impossible
Help yourself
Impossible
Impossible
Help yourself
Ask for help
Help yourself
Help yourself
Ask for help
Ask for help

思路

模拟

按题意模拟即可。

自行选课：当前学生所在年级开放了选择当前课的权限，且当前学生所在学院开放了选择当前课的权限
教务处代选：不满足自行选课条件，且当前学生所在学院和课程所在学院是统一学院
无法选择：不满足上述两个条件

时间复杂度：O(nm)

类似题目推荐

LeetCode

周赛/双周赛第一题

Codefun2000

代码

CPP

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n, m, Q;
int s[N];
int f[5][N];
int g[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &Q);
    for (int i = 1; i <= n; ++i) scanf("%d", &s[i]);
    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &f[i][j]);

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &g[i][j]);

    while (Q--) {
        int A, B, c;
        scanf("%d%d%d", &A, &B, &c);
        if (f[B][c] == 1 && g[A][c] == 1) {
            puts("Help yourself");
        } else if (s[c] == A) {
            puts("Ask for help");
        } else {
            puts("Impossible");
        }
    }

    return 0;
}

python

n, m, Q = map(int, input().split())

f = []
g = []

s = list(map(int, input().split()))
for i in range(len(s)):
    s[i] -= 1
for i in range(1, 5):
    f.append(list(map(int, input().split())))

for i in range(1, m + 1):
    g.append(list(map(int, input().split())))

for _ in range(Q):
    A, B, c = map(int, input().split())
    A -= 1
    B -= 1
    c -= 1
    if f[B][c] == 1 and g[A][c] == 1:
        print("Help yourself")
    elif s[c] == A:
        print("Ask for help")
    else:
        print("Impossible")

Java

import java.util.Scanner;

public class Main {
    static final int N = 20;
    static int n, m, Q;
    static int[] s = new int[N];
    static int[][] f = new int[5][N];
    static int[][] g = new int[N][N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Q = sc.nextInt();
        for (int i = 1; i <= n; ++i) s[i] = sc.nextInt();
        for (int i = 1; i <= 4; ++i)
            for (int j = 1; j <= n; ++j)
                f[i][j] = sc.nextInt();

        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                g[i][j] = sc.nextInt();

        while (Q-- > 0) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            int c = sc.nextInt();
            if (f[B][c] == 1 && g[A][c] == 1) {
                System.out.println("Help yourself");
            } else if (s[c] == A) {
                System.out.println("Ask for help");
            } else {
                System.out.println("Impossible");
            }
        }
    }
}

Go

package main

import "fmt"

const N = 20

func main() {
    var n, m, Q int
    fmt.Scan(&n, &m, &Q)

    s := make([]int, n+1)
    for i := 1; i <= n; i++ {
        fmt.Scan(&s[i])
    }

    f := make([][]int, 5)
    for i := 1; i <= 4; i++ {
        f[i] = make([]int, n+1)
        for j := 1; j <= n; j++ {
            fmt.Scan(&f[i][j])
        }
    }

    g := make([][]int, m+1)
    for i := 1; i <= m; i++ {
        g[i] = make([]int, n+1)
        for j := 1; j <= n; j++ {
            fmt.Scan(&g[i][j])
        }
    }

    for ; Q > 0; Q-- {
        var A, B, c int
        fmt.Scan(&A, &B, &c)
        if f[B][c] == 1 && g[A][c] == 1 {
            fmt.Println("Help yourself")
        } else if s[c] == A {
            fmt.Println("Ask for help")
        } else {
            fmt.Println("Impossible")
        }
    }
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const [n, m, Q] = lines.shift().trim().split(' ').map(Number);

    const s = new Array(n + 1);
    const row = lines.shift().trim().split(' ').map(Number);
    for (let i = 0; i < n; ++i) s[i + 1] = row[i];
    

    const f = new Array(5).fill(null).map(() => new Array(n + 1));
    for (let i = 1; i <= 4; ++i) {
        const row = lines.shift().trim().split(' ').map(Number);
        for (let j = 1; j <= n; ++j) {
            f[i][j] = row[j - 1];
        }
    }

    const g = new Array(m + 1).fill(null).map(() => new Array(n + 1));
    for (let i = 1; i <= m; ++i) {
        const row = lines.shift().trim().split(' ').map(Number);
        for (let j = 1; j <= n; ++j) {
            g[i][j] = row[j - 1];
        }
    }

    for (let i = 0; i < Q; ++i) {
        const [A, B, c] = lines.shift().trim().split(' ').map(Number);
        if (f[B][c] === 1 && g[A][c] === 1) {
            console.log("Help yourself");
        } else if (s[c] === A) {
            console.log("Ask for help");
        } else {
            console.log("Impossible");
        }
    }
});

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】