08-21 18:37 已编辑北京理工大学算法工程师发布于江苏

关注

【秋招笔试】8.10美团秋招第一场-三语言题解

🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试｜编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和喜欢💗 和手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🌰 团子春招第一场，启动!!!

💡据说今年除了算法岗是5道题，其他岗位的题目都变成了选择+3道题，分别是算法岗的第 2、4、5 题

1️⃣ 第一题比较打卡，简单

2️⃣ 第二题需要排序+去重，很多朋友因为没考虑去重导致没有通过全部

3️⃣ 第三题可以直接贪心，也可以动态规划

4️⃣ 第四题是状态压缩DP，之前没有接触过的朋友可能会比较蒙

5️⃣ 第五题比较困难，是luogu上的原题改编，需要离线+树状数组/线段树/莫队，也可以主席树在线做。

alt

🎥 01.K小姐的偶数因子探秘

问题描述

K小姐对数字的因子充满了好奇，尤其是偶数因子。她想知道，对于给定的正整数 $x$ ，是否存在至少一个偶数因子（不包括 $1$ 和 $x$ 本身）。请帮助K小姐解答这个问题。

输入格式

第一行输入一个整数 $T$ ，表示询问的次数 $(1 \leq T \leq 10^5)$ 。

接下来 $T$ 行，每行输入一个整数 $x$ ，表示K小姐询问的正整数 $(1 \leq x \leq 10^9)$ 。

输出格式

对于每次询问，如果 $x$ 存在至少一个偶数因子，输出 "YES"；否则输出 "NO"。

样例输入

2
1
4

样例输出

NO
YES

数据范围

$1 \leq T \leq 10^5$
$1 \leq x \leq 10^9$

题解

要判断一个整数 $x$ 是否存在至少一个偶数因子，可以利用以下性质：如果 $x$ 是偶数且大于 $2$ ，那么 $x$ 至少有一个偶数因子 $2$ 。如果 $x$ 是奇数或者等于 $2$ ，则没有符合条件的偶数因子。

如果 $x$ 是偶数并且大于 $2$ ，则输出 "YES"。
否则，输出 "NO"。

参考代码

Python

import sys

def has_even_factor(x):
    # 判断 x 是否有偶数因子
    if x % 2 == 0 and x > 2:
        return True
    return False

# 快速输入
input = lambda: sys.stdin.readline().strip()

# 读取询问次数
T = int(input())

# 处理每次询问
for _ in range(T):
    x = int(input())
    if has_even_factor(x):
        print("YES")
    else:
        print("NO")

Java

import java.util.Scanner;

public class EvenFactorChecker {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 读取询问次数

        for (int i = 0; i < T; i++) {
            int x = scanner.nextInt(); // 读取每个询问的整数
            if (hasEvenFactor(x)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        scanner.close();
    }

    // 判断 x 是否有偶数因子
    private static boolean hasEvenFactor(int x) {
        return x % 2 == 0 && x > 2;
    }
}

#include <iostream>
using namespace std;

// 判断 x 是否有偶数因子
bool has_even_factor(int x) {
    return x % 2 == 0 && x > 2;
}

int main() {
    int T;
    cin >> T; // 读取询问次数

    while (T--) {
        int x;
        cin >> x; // 读取每个询问的整数
        if (has_even_factor(x)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

🚕 02.K小姐的冒险

问题描述

K小姐正在尝试登录一个神秘的网站，她需要输入正确的密码才能进入。她记得密码可能是她手中一系列字符串中的一个。为了尽快找到正确的密码，K小姐决定按照密码的长度从短到长依次尝试每个字符串。如果长度相同，她会随机选择一个进行尝试，并且每个密码只会尝试一次。一旦成功登录，她将立即停止尝试。

K小姐希望知道，她最少需要尝试多少次才能成功登录，最多需要尝试多少次才能成功登录。

输入格式

第一行输入一个整数 $n$ ，表示密码字符串的个数。

第二行输入一个字符串 $s$ ，表示正确的密码。

接下来 $n$ 行，每行输入一个字符串，表示K小姐记得的密码。

输出格式

在一行上输出两个整数，表示最少和最多尝试次数。

样例输入

4
ab
abc
ab
ac
ac

样例输出

1 2

示例说明

在给定的样例中，K小姐有四个记得的密码：abc, ab, ac, ac。正确的密码是 ab。

K小姐可能按照 ["ab", "ac", "abc"] 的顺序尝试，第一次尝试 ab 就成功了。
也可能按照 ["ac", "ab", "abc"] 的顺序尝试，第一次尝试 ac 失败后，第二次尝试 ab 成功。
无论尝试的顺序如何，K小姐在尝试 ac 发现不正确后不会继续尝试 ac。

因此，最少尝试次数是 1，最多尝试次数是 2。

数据范围

$1 \leq n \leq 1000$
$1 \leq |s| \leq 1000$
每个字符串的长度不超过 1000

题解

模拟题，为了找出最少和最多的尝试次数，可以按照以下步骤进行：

将所有记得的密码去重，以避免重复尝试。
计算出比正确密码短的字符串数量，这些字符串将首先被尝试。
计算出与正确密码长度相同的字符串数量。
最少尝试次数为比正确密码短的字符串数量加一（因为正确密码可能是第一个尝试的）。
最多尝试次数为比正确密码短的字符串数量加上与正确密码长度相同的字符串数量。

参考代码

Python

# 读取输入
n = int(input())  # 密码字符串的个数
correct_password = input()  # 正确的密码
password_length = len(correct_password)  # 正确密码的长度
passwords = set(input() for _ in range(n))  # 使用集合去重存储所有记得的密码

# 计算比正确密码短的字符串数量
shorter_count = sum(1 for p in passwords if len(p) < password_length)
# 计算与正确密码长度相同的字符串数量
same_length_count = sum(1 for p in passwords if len(p) == password_length)

# 输出最少和最多尝试次数
print(shorter_count + 1, shorter_count + same_length_count)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 密码字符串的个数
        String correctPassword = scanner.next(); // 正确的密码
        int passwordLength = correctPassword.length(); // 正确密码的长度
        Set<String> passwords = new HashSet<>(); // 使用集合去重存储所有记得的密码
        
        // 读取所有记得的密码
        for (int i = 0; i < n; i++) {
            passwords.add(scanner.next());
        }
        
        int shorterCount = 0; // 比正确密码短的字符串数量
        int sameLengthCount = 0; // 与正确密码长度相同的字符串数量
        
        // 统计比正确密码短和相同长度的字符串数量
        for (String password : passwords) {
            if (password.length() < passwordLength) {
                shorterCount++;
            } else if (password.length() == passwordLength) {
                sameLengthCount++;
            }
        }
        
        // 输出最少和最多尝试次数
        System.out.println((shorterCount + 1) + " " + (shorterCount + sameLengthCount));
    }
}

#include <iostream>
#include <unordered_set>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n; // 密码字符串的个数
    string correctPassword;
    cin >> correctPassword; // 正确的密码
    int passwordLength = correctPassword.length(); // 正确密码的长度
    
    unordered_set<string> passwords; // 使用集合去重存储所有记得的密码
    for (int i = 0; i < n; ++i) {
        string password;
        cin >> password;
        passwords.insert(password);
    }
    
    int shorterCount = 0; // 比正确密码短的字符串数量
    int sameLengthCount = 0; // 与正确密码长度相同的字符串数量
    
    // 统计比正确密码短和相同长度的字符串数量
    for (const auto& password : passwords) {
        if (password.length() < passwordLength) {
            shorterCount++;
        } else if (password.length() == passwordLength) {
            sameLengthCount++;
        }
    }
    
    // 输出最少和最多尝试次数
    cout << shorterCount + 1 << " " << shorterCount + sameLengthCount << endl;
    return 0;
}

🗼 03.K小姐的魔法清理

题目描述

K小姐是一位魔法师，她拥有一个神奇的魔法袋，里面装满了各种魔法石。每颗魔法石都有一个能量值，排列成一个数组。为了进行新的魔法实验，K小姐需要清空这个数组。她可以选择逐一移除魔法石，或者使用强力魔法一次性清空整个袋子。每种方式都有其对应的魔法消耗，K小姐希望以最小的代价完成这个任务。

K小姐可以对数组进行如下操作：

移除第一个魔法石，消耗 $x$ 点魔法能量。
移除整个数组，消耗 $k \times \text{MEX}(a)$ 点魔法能量，其中 $\text{MEX}(a)$ 表示数组 $a$ 中未出现过的最小非负整数。

K小姐想知道，清空整个数组所需的最小魔法能量是多少。

输入格式

第一行输入一个整数 $T$ ，表示测试数据的组数。

接下来每组测试数据包含两行：

第一行包含三个正整数 $n, k, x$ ，分别表示数组的长度、清空整个数组的消耗系数、移除单个元素的消耗。
第二行包含 $n$ 个整数，表示数组中的元素。

输出格式

对于每组测试数据，输出一个整数，表示清空数组的最小魔法能量。

样例输入

1
6 3 3
4 5 2 3 1 0

样例输出

示例说明

对于给定的样例：

初始数组为 [4, 5, 2, 3, 1, 0]。
如果直接清空整个数组， $\text{MEX}$ 为 6，消耗为 $6 \times 3 = 18$ 。
如果先移除一个元素 4，数组变为 [5, 2, 3, 1, 0]， $\text{MEX}$ 为 4，消耗为 $3 + 4 \times 3 = 15$ 。
如果移除两个元素 4 和 5，数组变为 [2, 3, 1, 0]， $\text{MEX}$ 为 4，消耗为 $6 + 4 \times 3 = 18$ 。
如果移除三个元素 4, 5, 2，数组变为 [3, 1, 0]， $\text{MEX}$ 为 2，消耗为 $9 + 2 \times 3 = 15$ 。
继续移除会导致更高的消耗。

因此，最小消耗为 15。

数据范围

$1 \leq T \leq 1000$
$1 \leq n \leq 2 \times 10^5$
$1 \leq k, x \leq 10^9$
数组中所有 $n$ 之和不超过 $2 \times 10^5$

题解

从左往右，考虑两种操作的组合：

逐一移除元素：每次移除第一个元素，消耗 $x$ 点能量。
一次性清空数组：计算当前数组的 $\text{MEX}$ ，然后消耗 $k \times \text{MEX}$ 点能量
根据答案为之前消耗的能量总和加上当前的 $k \times \text{MEX}$

可以用优先队列等其他有序的数据结构动态维护数组中的 MEX

参考代码

Python

import heapq
from collections import defaultdict

def solve():
    n, k, x = map(int, input().split())
    a = list(map(int, input().split()))
    count = defaultdict(int)
    
    # 统计每个元素的出现次数
    for num in a:
        count[num] += 1
    
    # 优先队列用于计算 MEX
    mex_candidates = []
    for i in range(n + 1):
        if i not in count:
            heapq.heappush(mex_candidates, i)
    
    # 初始化最小花费
    min_cost = heapq.heappop(mex_candidates) * k
    heapq.heappush(mex_candidates, min_cost // k)
    
    current_cost = 0
    for num in a:
        count[num] -= 1
        if count[num] == 0:
            heapq.heappush(mex_candidates, num)
        
        current_cost += x
        min_cost = min(min_cost, heapq.heappop(mex_candidates) * k + current_cost)
        heapq.heappush(mex_candidates, min_cost // k)
    
    print(min_cost)

def main():
    T = int(input())
    for _ in range(T):
        solve()

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 读取测试数据组数
        while (T-- > 0) {
            int n = scanner.nextInt(); // 数组长度
            long k = scanner.nextLong(); // 清空数组的消耗系数
            long x = scanner.nextLong(); // 移除单个元素的消耗
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt(); // 读取数组元素
            }
            System.out.println(minCost(n, k, x, a)); // 输出最小花费
        }
    }

    private static long minCost(int n, long k, long x, int[] a) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : a) {
            count.put(num, count.getOrDefault(num, 0) + 1); // 统计每个元素的出现次数
        }

        PriorityQueue<Integer> mexCandidates = new PriorityQueue<>();
        for (int i = 0; i <= n; i++) {
            if (!count.containsKey(i)) {
                mexCandidates.add(i); // 初始化 MEX 候选队列
            }
        }

        long minCost = mexCandidates.poll() * k;
        mexCandidates.add((int)(minCost / k));
        long currentCost = 0;

        for (int num : a) {
            count.put(num, count.get(num) - 1);
            if (count.get(num) == 0) {
                mexCandidates.add(num); // 更新 MEX 候选队列
            }
            currentCost += x;
            minCost = Math.min(minCost, mexCandidates.poll() * k + currentCost);
            mexCandidates.add((int)(minCost / k));
        }

        return minCost;
    }
}

#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

void solve() {
    int n;
    long long k, x;
    cin >> n >> k >> x; // 读取数组长度、清空系数和单个移除消耗
    vector<int> a(n);
    unordered_map<int, int> count;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

学长刷题笔记文章被收录于专栏

这里收集了超全的刷题笔记，欢迎大家的订阅，会持续跟新的