0827 美团笔试总结

该死，第四题 0 1 背包忘掉了，明明数据结构课程可算法设计与分析课程里面都讲过，当时没有仔细下去看，该死。

第一题

题目描述

小美在摆弄她的字符串。最近小团送了小美一个特殊字符 '*'，这个字符可以和其他所有字符匹配，除了这个字符外，其他字符只能自己和自己匹配。小美先前有一个字符串 S，长度为 n，现在她又新组合了一个可有特殊字符 '*' 的字符串 s，长度为 n。小美想知道有多少个位置 i，使得 S[i+j] 与 s[j] 对于 $1 \leqslant j \leqslant m$ 均能匹配上？其中 X[y] 代表字符串 X 中第 y 位的字符。

输入描述

第一行两个空格隔开的整数 n 和 m，分别表示字符串 S 和字符串 s 的长度。
接下来一行长度为 n 的仅包含小写英文字母的字符串 S。
接下来一行长度为 m 的包含小写英文字母以及特殊字符 '*' 的字符串。
对于所有数据，$1 \leqslant n \leqslant m \leqslant 2000$。

输出描述

输出一行一个整数，表示满足要求的位置数量。

样例输入

1
2
3

7 3
abcaacc
a*c

样例输出

代码

import java.util.Scanner;

public class Main {

    private int getAllCount(String S, String s, int n, int m) {
        int res = 0;

        for (int i = 0; i <= n - m; i++) {
            res += isEqual(s, S.substring(i, i + m));
        }

        return res;
    }

    private int isEqual(String str1, String str2) {
        int n = str1.length();
        for (int i = 0; i < n; i++) {
            if (str1.charAt(i) != '*' && str1.charAt(i) != str2.charAt(i)) {
                return 0;
            }
        }
        return 1;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            String S = sc.next();
            String s = sc.next();

            int res = main.getAllCount(S, s, n, m);
            System.out.println(res);
        }
    }

}

第二题

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] operations = new int[m];
            for (int i = 0; i < m; i++) {
                operations[i] = sc.nextInt();
            }
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                map.put(i + 1, 0);
            }
            int count = 0;
            for (int i = 0; i < m; i++) {
                map.put(operations[i], -(++count));
            }
            List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
            Collections.sort(list, (o1, o2) -> o1.getValue() - o2.getValue());
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(list.get(i).getKey().toString());
                if (i == n - 1) {
                    break;
                }
                sb.append(" ");
            }
            System.out.println(sb);
        }
    }
}

第三题

题目描述

小团最近获得了美美团团国的裁缝资格证，成为了一个裁缝！现在小团有一个长度为 n 的大布料 S(在这个国家布料其实是一个仅包含小写英文字母的字符串)，小团可以将布料在任意位置剪切，例如布料 abcd 可以被裁剪为 a 与 bcd 或 ab 与 cd 或 abc 与 d，不过，裁剪完之后是不能拼接起来的，因为小团还不是很擅长拼接布料。现在小团想知道能不能有一种裁剪方式能让她把布料恰好裁剪成客人要求的小布料。
形式化地，有一个串 S，问是否能将其划分成 m 个不相交的连续字串，使得这些连续字串可以要求的连续字串可以与要求的连续子串一一对应。两个串相对应是指这两个串完全相等。例如 "aab"="aab" 但 "aab"≠"baa"。

输入描述

第一行两个空格隔开的正整数 n 和 m，分别表示大布料 S 长度和客人要求的小布料数量。
接下来一行一个长度为 n 的仅包含小写英文字母的串 S，表示大布料的组成。
接下来一行 m 个空格隔开的数 $x_1, x_2, \dots, x_m$，依次表示所要求的小布料长度。
接下来开始 m 行，每行一个长度为 $x_i$ 的仅包含小写字母的串 $s_i$，表示第 i 个小布料的组成。
对于所有数据，$1 \leq m \leq 9, ; 1 \leq n \leq 20, ; 1 \leq x_i \leq n$ 且 $\sum_{i = 1}^{m} x_i = n$。

输出描述

如果存在这样的方案，输出方案总数。如果不存在任何方案，输出 0。两个方案 A、B 不相同当且仅当方案 A 中存在一个相对于原始长布料的裁剪位置 i，而方案 B 中并未在该位置 i 裁剪。
例如 aaaaaa 裁剪方案 aaa|aaa 是相同的方案。而方案 aa|aaaa 与方案 aaaa|aa 是不同的方案，虽然划分出的结果都是 aa 与 aaaa，但前者在第二个 a 进行了裁剪，后者并没有在这里进行裁剪，所以视为不同的裁剪方案。

样例输入

6 2
aaaaaa
4 2
aaaa
aa

样例输出

提示

有两种解决方案，第一种是 aaaa|aa，第二种是 aa|aaaa，代表一次裁剪。

代码

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    private int count = 0;

    public int getRes(int n, int m, String S, int[] x, String[] s) {
        List<String> sList = Arrays.stream(s).collect(Collectors.toList());
        dfs(S, sList);

        return this.count;
    }

    private void dfs(String S, List<String> sList) {
        if (S.length() == 0) {
            this.count++;
        }
        for (int i = 0; i < sList.size(); i++) {
            if (S.startsWith(sList.get(i))) {
                String cur = sList.get(i);
                sList.remove(i);
                dfs(S.substring(cur.length()), sList);
                sList.add(i, cur);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            String S = sc.next();
            int[] x = new int[m];
            for (int i = 0; i < m; i++) {
                x[i] = sc.nextInt();
            }
            String[] s = new String[m];
            for (int i = 0; i < m; i++) {
                s[i] = sc.next();
            }

            Main solu = new Main();
            int res = solu.getRes(n, m, S, x, s);
            System.out.println(res);
        }
    }

}

第四题

题目描述

小团正忙着用机器人收衣服！因为快要下雨了，小团找来了不少机器人帮忙收衣服。他有 n 件衣服从左到右成一行排列，所在位置分别为 1~n，在每个位置上已经有一个就绪的机器人可以帮忙收衣服，但第 i 个位置上的机器人需要 $p_i$ 的电量来启动，然后这个机器人会用 $t_i$ 的时间来收衣服，当它收完当前衣服后，会尝试去收紧邻的右边的一件衣服(如果存在的话)，即 i + 1 处的衣服，如果 i + 1 处的衣服已经被其他机器人收了或者其他机器人正在收，这个机器人就会进入休眠状态，不再收衣服。不过如果机器人没有休眠，它会同样以 $t_i$ 时间来收这件 i + 1 处的衣服(注意，不是 $t_{i + 1}$ 的时间，收衣服的时间为每个机器人固有属性)，然后它会做同样的检测来看能否继续收 i + 2 处的衣服，一直直到它进入休眠状态或者右边没有衣服可以收了。形象地来说，机器人会一直尝试往右边收衣服，收 k 件的话就耗费 $k * t_i$ 的时间，但是当它遇见其他机器人工作的痕迹，就会认为后面的事情它不用管了，开始摸鱼，进入休眠状态。
小团手里总共有电量 b，他准备在 0 时刻的时候将所有他想启动的机器人全部一起启动，过后不再启动新的机器人，并且启动的机器人的电量之和不大于 b。他想知道在最佳选择的情况下，最快多久能收完衣服。若无论如何怎样都收不完衣服，输出 -1。

输入描述

第一行两个正整数 n 和 b，分别表示衣服数量和小团持有电量。
接下来一行 n 个数 $p_1, p_2, \dots, p_n$，含义如题所述，为机器人唤醒需求电量。
接下来一行 n 个数 $t_1, t_2, \dots, t_n$，含义如题所述，为机器人收衣服所需时间。
数字间两两有空格隔开。
对于所有数据，$1 \leq n \leq 1000, 1 \leq p_i \leq 100, 1 \leq t_i, b \leq 10^5$。

输出描述

输出最短所需时间。

样例输入

1
2
3

3 5
1 2 3
7 5 3

样例输出

提示

样例解释 1：

可以同时启动第一个机器人和第二个机器人，耗电量为 1 + 2 = 3，这样花费时间为 max(7, 5 * 2) = 10。
也可以同时启动第一个机器人和第三个机器人，耗电量为 1 + 3 = 4，这样花费时间为 max(7 * 2, 3) = 14。

输入样例 2：

1
2
3

3 5
6 2 3
7 5 3

输出样例 2：

-1

样例解释 2：

因为必须要启动第一个机器人，耗电量至少为 6，但是持有电量只有 5，因此无法收完所有衣服，输出 -1。

第五题

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int T = sc.nextInt();

            int[] t = new int[k];
            for (int i = 0; i < k; i++) {
                t[i] = sc.nextInt();
            }

            int[] e = new int[n];
            for (int i = 0; i < n; i++) {
                e[i] = sc.nextInt();
            }

            Queue<Integer> queue = new PriorityQueue<>();
            int res = 0;
            for (int i = 0; i < n; i++) {
                if (e[i] == 0) {
                    if (queue.size() == 0) {
                        res += T;
                    } else {
                        if (queue.peek() < T) {
                            res += queue.poll();
                        } else {
                            res += T;
                        }
                    }
                } else {
                    queue.offer(t[e[i] - 1]);
                }
            }
            System.out.println(res);
        }
    }
}

#笔试 #工作

0827 美团笔试总结

http://fanlumaster.github.io/2022/08/31/0827-美团笔试总结/

作者

fanlumaster

发布于

2022年8月31日

许可协议

MySQL 索引的使用上一篇

暑期实训报告下一篇