💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

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

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍠 得物秋招笔试，来啦！！！

🍥 本次难度中等偏上，其中最后一题是状态压缩DP，没接触过的小伙伴会有点懵，第二题也有坑，没保证数组有序

1️⃣ 简单的小学数学题

2️⃣ 哈希表的基础应用

3️⃣ BFS走迷宫的拓展版

🍏 01.LYA的水果切割难题

问题描述

LYA 开了一家水果店，专门为顾客提供切好的水果。每种水果都有其特定的切割方式，恰好可以切成 块（不论大小），也只能切成 块。

一位顾客想买一盒水果，但他有特殊要求：这盒水果中的水果块数必须在闭区间 中。

LYA 只按"个"卖水果，而不是按"块"卖水果。如果整数个水果不能满足顾客要求，LYA 就不会卖给这位顾客。如果存在整数个水果，使得这些水果切成的块数满足顾客要求，那么 LYA 希望知道她最少需要切多少个水果，以及最多需要切多少个水果。

输入格式

第一行输入一个正整数 ，代表测试数据的组数。

对于每组测试数据，一行输入三个正整数 ，含义如题所述。

输出格式

对于每组测试数据，如果 LYA 的卖水果规则不能满足顾客要求，则输出 ，否则输出两个正整数，依次代表 LYA 需要为这位顾客最少切多少个水果，最多切多少个水果。

样例输入

3
2 6 9
3 7 9
5 6 9

样例输出

3 4
3 3
-1

数据范围

题解

简单的小学数学题

1. 最少需要的水果数（左端点，向上取整）：
2. 最多需要的水果数（右端点，向下取整）：

参考代码

• Python

import math

def solve_fruit_cutting_problem():
    cuts_per_fruit, min_pieces, max_pieces = map(int, input().split())

    # 计算最少需要的水果数（向上取整）
    min_fruits = math.ceil(min_pieces / cuts_per_fruit)

    # 计算最多需要的水果数（向下取整）
    max_fruits = max_pieces // cuts_per_fruit

    # 判断是否能满足顾客要求
    if min_fruits > max_fruits:
        print(-1)
    else:
        print(min_fruits, max_fruits)

def main():
    num_test_cases = int(input())
    for _ in range(num_test_cases):
        solve_fruit_cutting_problem()

if __name__ == "__main__":
    main()

• Java

import java.util.Scanner;

public class FruitCuttingProblem {
    public static void solveFruitCuttingProblem(Scanner scanner) {
        int cutsPerFruit = scanner.nextInt();
        int minPieces = scanner.nextInt();
        int maxPieces = scanner.nextInt();

        // 计算最少需要的水果数（向上取整）
        int minFruits = (minPieces + cutsPerFruit - 1) / cutsPerFruit;

        // 计算最多需要的水果数（向下取整）
        int maxFruits = maxPieces / cutsPerFruit;

        // 判断是否能满足顾客要求
        if (minFruits > maxFruits) {
            System.out.println(-1);
        } else {
            System.out.println(minFruits + " " + maxFruits);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numTestCases = scanner.nextInt();

        for (int i = 0; i < numTestCases; i++) {
            solveFruitCuttingProblem(scanner);
        }

        scanner.close();
    }
}

• Cpp

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

void solveFruitCuttingProblem() {
    int cutsPerFruit, minPieces, maxPieces;
    cin >> cutsPerFruit >> minPieces >> maxPieces;

    // 计算最少需要的水果数（向上取整）
    int minFruits = (minPieces + cutsPerFruit - 1) / cutsPerFruit;

    // 计算最多需要的水果数（向下取整）
    int maxFruits = maxPieces / cutsPerFruit;

    // 判断是否能满足顾客要求
    if (minFruits > maxFruits) {
        cout << -1 << "\n";
    } else {
        cout << minFruits << " " << maxFruits << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int numTestCases = 1;
    cin >> numTestCases;

    while (numTestCases--) {
        solveFruitCuttingProblem();
    }

    return 0;
}

🍰 02.LYA的字符串收藏

问题描述

LYA是一位热爱收藏字符串的年轻人。她特别喜欢那些由相同字符组成的字符串，称之为"完美字符串"。有一天，LYA得到了一个长度为的字符串，她想知道在这个字符串中，最多能找到多少个互不重叠的、长度为的"完美字符串"。这些"完美字符串"必须是原字符串的连续子串。LYA需要你的帮助来解决这个问题。

输入格式

第一行包含两个正整数和，分别表示原字符串的长度和LYA想要寻找的"完美字符串"的长度。

第二行包含一个长度为的字符串，仅由小写英文字母组成。

输出格式

输出一个整数，表示LYA能找到的最大数量的互不重叠的长度为的"完美字符串"。

样例输入1

7 3
aaabaaa

样例输出1

3

样例解释1

LYA可以选择前三个字符"aaa"和最后三个字符"aaa"，这两个子串都是长度为3的"完美字符串"，且互不重叠。

样例输入2

7 2
aabaacc

样例输出2

2

样例解释2

LYA可以选择"aa"、"aa"，有两个，"cc"有一个，所以选择两个 'aa'

数据范围

题解

哈希表

"完美字符串"是由相同字符组成的字符串，我们只需要找到所有连续的相同字符序列，并且判断当前能分割成多少个长度为 的子串即可 。

参考代码

• Python

from collections import Counter

def count_perfect_substrings(n, k, s):
    # 初始化变量
    consecutive = 1  # 当前连续相同字符的数量
    char_count = Counter()  # 用于统计每个字符能形成的"完美字符串"数量
    
    # 遍历字符串
    for i in range(1, n):
        if s[i] == s[i-1]:
            consecutive += 1
        else:
            # 计算当前字符能形成的"完美字符串"数量并更新计数器
            char_count[s[i-1]] += consecutive // k
            consecutive = 1  # 重置连续计数
    
    # 处理最后一个字符
    char_count[s[-1]] += consecutive // k
    
    # 返回能形成的最大"完美字符串"数量
    return max(char_count.values()) if char_count else 0

# 读取输入
n, k = map(int, input().split())
s = input().strip()

# 计算并输出结果
result = count_perfect_substrings(n, k, s)
print(result)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        String s = scanner.next();
        
        System.out.println(countPerfectSubstrings(n, k, s));
    }
    
    public static int countPerfectSubstrings(int n, int k, String s) {
        // 用于统计每个字符能形成的"完美字符串"数量
        Map<Character, Integer> charCount = new HashMap<>();
        int consecutive = 1; // 当前连续相同字符的数量
        
        // 遍历字符串
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == s.charAt(i-1)) {
                consecutive++;
            } else {
                // 计算当前字符能形成的"完美字符串"数量并更新计数器
                char currentChar = s.charAt(i-1);
                charCount.put(currentChar, charCount.getOrDefault(currentChar, 0) + consecutive / k);
                consecutive = 1;