25届-8.24团子(改编题)

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

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

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

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

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

alt

🍥 本次后两题难度较大，对数据结构的要求较高

1️⃣ 打卡题，原题的描述有点问题

2️⃣ 枚举+贪心，难度不大

3️⃣ 小学数学题，分情况讨论即可

4️⃣ LCA + st表，难度较大

5️⃣ 线段树处理区间最值+单点修改

🍥 01.视频分辨率评级系统

问题描述

LYA 是一家视频网站的技术负责人，她正在开发一个视频分辨率评级系统。该系统根据视频的长度和宽度（以像素为单位）来确定视频的清晰度等级。具体的评级标准如下：

  • 如果长和宽低于 360 像素，视频被认为是损坏的，系统应输出 "break"。
  • 长和宽不低于 360 像素，视频被评为 "360P"。
  • 长和宽不低于 480 像素，视频被评为 "480P"。
  • 长和宽不低于 720 像素，视频被评为 "720P"。
  • 长和宽不低于 1080 像素，视频被评为 "1080P"。
  • 长和宽不低于 2160 像素，视频被评为 "4K"。

LYA 需要你帮忙编写一个程序，快速判断给定视频的最高分辨率等级。

输入格式

第一行输入一个整数 ，表示需要评级的视频数量。

接下来的 行，每行包含两个整数 和 ，分别表示视频的高度和宽度（以像素为单位）。

输出格式

对于每个视频，输出一行字符串，表示该视频能够达到的最高分辨率等级。

样例输入

2
1080 1960
500 2170

样例输出

1080P
480P

样例解释

对于第一个视频，其高度为 1080 像素，宽度为 1960 像素。根据评级标准，这个视频可以达到 1080P 的分辨率等级。

对于第二个视频，虽然其宽度达到了 2170 像素，但高度只有 500 像素。根据评级标准，我们需要考虑较小的那个维度，因此这个视频的最高分辨率等级为 480P。

数据范围

题解

签到题，原题的题意说的或有点问题，实际要写与的逻辑才是对的，这点看样例能看出里

按照题意模拟就可以了

参考代码

  • Python 
import sys

def get_resolution(h: int, w: int) -> str:
    """
    根据屏幕高度和宽度判断清晰度等级
    :param h: 屏幕高度
    :param w: 屏幕宽度
    :return: 清晰度等级
    """
    if h >= 2160 and w >= 2160:
        return "4K"
    elif h >= 1080 and w >= 1080:
        return "1080P"
    elif h >= 720 and w >= 720:
        return "720P"
    elif h >= 480 and w >= 480:
        return "480P"
    elif h >= 360 and w >= 360:
        return "360P"
    else:
        return "break"

def main():
    """
    主函数：处理输入输出
    """
    input = sys.stdin.read
    data = input().split()
    
    T = int(data[0])  # 读取放映厅数量
    index = 1
    results = []
    
    for _ in range(T):
        h = int(data[index])
        w = int(data[index + 1])
        index += 2
        result = get_resolution(h, w)
        results.append(result)
    
    print("\n".join(results))  # 输出结果

if __name__ == "__main__":
    main()
  • Java 
import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    
    /**
     * 判断视频分辨率等级
     * @param h 视频高度
     * @param w 视频宽度
     * @return 分辨率等级
     */
    public static String getResolution(int h, int w) {
        if (h >= 2160 && w >= 2160) {
            return "4K";
        } else if (h >= 1080 && w >= 1080) {
            return "1080P";
        } else if (h >= 720 && w >= 720) {
            return "720P";
        } else if (h >= 480 && w >= 480) {
            return "480P";
        } else if (h >= 360 && w >= 360) {
            return "360P";
        } else {
            return "break";
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 读取测试用例数量
        
        ArrayList<String> results = new ArrayList<>();
        
        for (int i = 0; i < T; i++) {
            int h = scanner.nextInt(); // 读取视频高度
            int w = scanner.nextInt(); // 读取视频宽度
            String result = getResolution(h, w);
            results.add(result);
        }
        
        // 输出结果
        for (String result : results) {
            System.out.println(result);
        }
        
        scanner.close();
    }
}
  • Cpp 
#include <iostream>
#include <vector>
#include <string>

using namespace std;

/**
 * 判断视频分辨率等级
 * @param h 视频高度
 * @param w 视频宽度
 * @return 分辨率等级
 */
string getResolution(int h, int w) {
    if (h >= 2160 && w >= 2160) {
        return "4K";
    } else if (h >= 1080 && w >= 1080) {
        return "1080P";
    } else if (h >= 720 && w >= 720) {
        return "720P";
    } else if (h >= 480 && w >= 480) {
        return "480P";
    } else if (h >= 360 && w >= 360) {
        return "360P";
    } else {
        return "break";
    }
}

int main() {
    int T;
    cin >> T; // 读取测试用例数量
    
    vector<string> results;
    
    for (int i = 0; i < T; i++) {
        int h, w;
        cin >> h >> w; // 读取视频高度和宽度
        string result = getResolution(h, w);
        results.push_back(result);
    }
    
    // 输出结果
    for (const string& result : results) {
        cout << result << endl;
    }
    
    return 0;
}

🪣 02.K小姐的快递配送

问题描述

K小姐是一名快递配送员，她每天都需要在城市中穿梭，将包裹送到指定地点。城市可以看作是一个二维平面，K小姐的初始位置为 ，而公司的仓库位置为 。

今天，K小姐需要配送 个包裹，每个包裹的位置为 。K小姐每次可以向上、下、左、右移动一个单位距离，每次移动的体力消耗为1。她每次只能携带一个包裹，必须先移动到包裹所在位置，然后将包裹送到仓库 。

K小姐想知道，要将所有包裹送到仓库，她最少需要消耗多少体力？

输入格式

第一行：四个整数 ，表示K小姐的初始位置和仓库位置。

第二行：一个整数 ，表示包裹的数量。

接下来 行：每行两个整数 ，表示第 个包裹的位置。

输出格式

输出一个整数，表示K小姐最少需要消耗的体力值。

样例输入

0 0 1 1
2
1 0
2 2

样例输出

6

样例解释

K小姐的最优配送路线如下：

  1. 从 (0,0) 移动到 (1,0)，拿起包裹，移动到 (1,1)，放下包裹。体力消耗为2。
  2. 从 (1,1) 移动到 (2,2)，拿起包裹，移动到 (1,1)，放下包裹。体力消耗为4。 总体力消耗：2 + 4 = 6。

数据范围

题解

贪心，找出第一个包裹该拿哪个

对于每个包裹，我们计算两个值：

  1. 直接配送的成本
  2. 顺路配送的额外成本。

直接配送成本是从当前位置到包裹位置再到仓库的距离。

顺路配送的额外成本是直接配送成本减去从初始位置到包裹位置的距离。

参考代码

  • Python 
# 读取输入
a, b, c, d = map(int, input().split())
n = int(input())

res = 0  # 总体力消耗
z = 0    # 最大节省量

# 遍历每个包裹
for _ in range(n):
    x, y = map(int, input().split())
    
    # 计算直接配送成本
    k = (abs(c - x) + abs(d - y)) * 2
    
    # 计算并更新最大节省量
    z = max(z, k - (abs(a - x) + abs(b - y) + abs(c - x) + abs(d - y)))
    
    res += k  # 累加直接配送成本

# 输出结果
print(res - z)
  • Java 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取初始位置和仓库位置
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        long c = scanner.nextLong();
        long d = scanner.nextLong();
        
        int n = scanner.nextInt();
        long res = 0;  // 总体力消耗
        long z = 0;    // 最大节省量
        
        // 遍历每个包裹
        for (int i = 0; i < n; i++) {
            long x = scanner.nextLong();
            long y = scanner.nextLong();
            
            // 计算直接配送成本
            long k = (Math.abs(c - x) + Math.abs(d - y)) * 2;
            
            // 计算并更新最大节省量
            z = Math.max(z, k - (Math.abs(a - x) + Math.abs(b - y) + Math.abs(c - x) + Math.abs(d - y)));
            
            res += k;  // 累加直接配送成本
        }
        
        // 输出结果
        System.out.println(res - z);
        
        scanner.close();
    }
}
  • Cpp 
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    LL a, b, c, d;
    cin >> a >> b >> c >> d;
    
    int n;
    cin >> n;
    
    LL res = 0;  // 总体力消耗
    LL z = 0;    // 最大节省量
    
    // 遍历每个包裹
    for (int i = 0; i < n; i++) {
        LL x, y;
        cin >> x >> y;
        
        // 计算直接配送成本
        LL k = (llabs(c - x) + llabs(d - y)) * 2;
        
        // 计算并更新最大节省量
        z = max(z, k - (llabs(a - x) + llabs(b - y) + llabs(c - x) + llabs(d - y)));
        
        res += k;  // 累加直接配送成本
    }
    
    // 输出结果
    cout << res - z << "\n";
    
    return 0;
}

📫 03.魔法花园的最佳收成

问题描述

K小姐是一位魔法园丁，她的花园里有三种神奇的魔法植物，分别记为 、 和 。这些植物每天都会产生魔法能量。K小姐每天可以对其中一株植物施加特殊的魔法肥料，使其魔法能量增加1点。她最多可以使用 次魔法肥料。

K小姐想知道，在最多使用 次魔法肥料的情况下，她能获得的最大魔法能量乘积（即 ）是多少？

输入格式

一行四个正整数 、、 和 （），分别表示三种魔法植物的初始能量值和可使用的魔法肥料次数。

输出格式

输出一个整数，表示K小姐能获得的最大魔法能量乘积。

样例输入

1 2 3 1

样例输出

12

样例解释

K小姐选择对初始能量为1的植物使用一次魔法肥料，使其能量变为2。此时三株植物的能量为 [2, 2, 3]，乘积为12，这是最大可能的乘积。

数据范围

对于所有测试数据，保证 。

题解

贪心

应该优先提升能量较低的植物，使三株植物的能量尽可能接近。

具体步骤如下：

  1. 首先将三个数排序。
  2. 尝试将最小的数提升到第二小的数的水平。
  3. 如果还有剩余操作次数，尝试将两个较小的数提升到最大数的水平。
  4. 如果仍有剩余操作次数，平均分配给三株植物。

参考代码

  • Python 
# 读取输入
a, b, c, k = map(int, input().split())
MOD = 10**9 + 7

# 将三个数排序
nums = sorted([a, b, c])

# 计算最大乘积
def max_product(nums, k):
    # 尝试将最小的数提升到第二小的数的水平
    diff = nums[1] - nums[0]
    if k >= diff:
        nums[0] = nums[1]
        k -= diff
        
        # 尝试将两个较小的数提升到最大数的水平
        diff = nums[2] - nums[1]
        if k >= 2 * diff:
            k -= 2 * diff
            nums[0] = nums[1] = nums[2]
            
            # 平均分配剩余的操作次数
            inc = k // 3
            k %= 3
            for i in range(3):
                nums[i] += inc
                if i < k:
                    nums[i] += 1
        else:
            # 平均分配剩余的操作次数给两个较小的数
            inc = k // 2
            k %= 2
            for i in range(2):
                nums[i] += inc
                if i < k:
                    nums[i] += 1
    else:
        # 所有操作都用于提升最小的数
        nums[0] += k
    
    # 计算乘积并取模
    result = 1
    for num in nums:
        result = (result * num) % MOD
    
    return result

# 输出结果
print(max_product(nums, k))
  • Java 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static final long MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        long c = scanner.nextLong();
        long k = scanner.nextLong();
        scanner.close();

        long[] nums = {a, b, c};
        Arrays.sort(nums);

        System.out.println(maxProduct(nums, k));
    }

    private static long maxProduct(long[] nums, long k) {
        // 尝试将最小的数提升到第二小的数的水平
        long diff = nums[1] - nums[0];
        if (k >= diff) {
            nums[0] = nums[1];
            k -= diff;

            // 尝试将两个较小的数提升到最大数的水平
            diff = nums[2] - nums[1];
            if (k >= 2 * diff) {
                k -= 2 * diff;
                nums[0] = nums[1] = nums[2];

                // 平均分配剩余的操作次数
                long inc = k / 3;
                k %= 3;
                for (int i = 0; i < 3; i++) {
                    nums[i] += inc;
                    if (i < k) nums[i]++;
                }
            } else {
                // 平均分配剩余的操作次数给两个较小的数
                long inc = k / 2;
                k %= 2;
                for (int i = 0; i < 2; i++) {
                    nums[i] += inc;
                    if (i < k) nums[i]++;
                }
            }
        } else {
            // 所有操作都用于提升最小的数
            nums[0] += k;
        }

        // 计算乘积并取模
        long result = 1;
        for (long num : nums) {
            result = (result * num) % MOD;
        }

        return result;
    }
}
  • Cpp 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const long long MOD = 1e9 + 7;

// 计算最大乘积
long long maxProduct(vector<long long>& nums, long long k) {
    // 尝试将最小的数提升到第二小的数的水平
    long long diff = nums[1] - nums[0];
    if (k >= diff) {
        nums[0] = nums[1];
        k -= diff;
        
        // 尝试将两个较小的数提升到最大数的水平
        diff = nums[2] - nums[1];
        if (k >= 2 * diff) {
            k -= 2 * diff;
            nums[0] = nums[1] = nums[2];
            
            // 平均分配剩余的操作次数
            long long inc = k / 3;
            k %= 3;
            for (int i = 0; i < 3; ++i) {
                nums[i] += inc;
                if (i < k) ++nums[i];
            }
        } else {
            // 平均分配剩余的操作次数给两个较小的数
            long long inc = k / 2;
            k %= 2;
            for (int i = 0; i < 2; ++i) {
                nums[i] += inc;
                if (i < k) ++nums[i];
            }
        }
    } else {
        // 所有操作都用于提升最小的数
        nums[0] += k;
    }
    
    // 计算乘积并取模
    long long result = 1;
    for (int i = 0; i < 3; ++i) {
        result = (result * nums[i]) % MOD;
    }
    
    return result;
}

int main() {
    long long a, b, c, k;
    cin >> a >> b >> c >> k;
    
    vector<long long> nums = {a, b, c};
    sort(nums.begin(), nums.end());
    
    cout << maxProduct(nums, k) << endl;
    
    return 0;
}

🥦 04.魔法森林的秘密通道

问题描述

K小姐是一位魔法森林的守护者。她负责管理一片由 棵魔法树组成的森林，这些树通过魔法藤蔓相连，形成了一个树状结构,根节点为1号树。每棵树都有一个独特的魔法等级，用 表示， 数组由 组成,且任意两棵树的魔法等级都不同。

K小姐获得了一次使用"秘密通道"魔法的机会。她可以选择任意两棵不同的树 和 ，在它们之间创建一条秘密通道(即使它们之间已经存在魔法藤蔓连接)。

创建秘密通道后,森林中会形成一个唯一的魔法环。这个魔法环的能量值定义为

其中 表示环中所有树的魔法等级中未出现的最小非负整数。K小姐的目标是最大化这个魔法环的能量值。

输入格式

第一行一个整数 ，表示魔法森林中树的数量。

第二行 个整数,第 个数为 ，表示每棵树的魔法等级。

接下来 行,每行 2 个数 ，表示树 和树 之间存在一条魔法藤蔓连接。

数据保证输入的是一个树状结构。

输出格式

输出一个整数,表示K小姐能创造的魔法环的最大能量值。

样例输入

6
0 3 2 1 4 5
1 2
1 3
2 4
2 5
5 6

样例输出

4

样例解释

初始的魔法森林结构如下：

    0
   / \
  3   2
 / \
1   4
   /
  5

       0 (1号节点)
      /         \
 3 (2号节点)   2 (3号节点)
    /     \
1 (4号节点) 4 (5号节点)
              /
         5 (6号节点)

K小姐可以在树3和树4之间创建秘密通道,形成魔法环 {0, 2, 1, 3}。这个魔法环的能量值为 ,这是可能获得的最大能量值。

数据范围

对于所有测试数据,保证 ,。

题解

显然可以发现，我们可以选择一条链把它两端相连作为环，而这条链上必须又有值为 0 的点。

我们将值为 0 的点作为根，可以发现，一条合法的链，一定是从 0 节点连出来的两条链或一条链合起来作为答案。

使用 LCA 判断新的 值的点是否在两条链上并动态维护两条链即可。

复杂度

参考代码

  • Python 
import sys
sys.setrecursionlimit(10**6)

class LCA:
    def __init__(self, n):
        self.n = n
        self.log = 20
        self.depth = [0] * (n + 1)
        self.parent = [[0] * (n + 1) for _ in range(self.log)]
        self.tin = [0] * (n + 1)
        self.tout = [0] * (n + 1)
        self.timer = 0

    def dfs(self, v, p, adj):
        # DFS遍历,记录每个节点的访问时间和父节点
        self.tin[v] = self.timer
        self.timer += 1
        self.parent[0][v] = p
        for i in range(1, self.log):
            self.parent[i][v] = self.parent[i-1][self.parent[i-1][v]]
        for u in adj[v]:
            if u != p:
                self.depth[u] = self.depth[v] + 1
                self.dfs(u, v, adj)
        self.tout[v] = self.timer
        self.timer += 1

    def is_ancestor(self, u, v):
        # 判断u是否是v的祖先
        return self.tin[u] <= self.tin[v] and self.tout[u] >= self.tout[v]

    def lca(self, u, v):
        # 查找u和v的最近公共祖先
        if self.is_ancestor(u, v):
            return u
        if self.is_ancestor(v, u):
            return v
        for i in range(self.log - 1, -1, -1):
            if not self.is_ancestor(self.parent[i][u], v):

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

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

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

全部评论

相关推荐

头像
12-19 20:01
腾讯_PCG_腾讯视频(实习员工)
26届三段大厂实习，前端打怪升级路线（大一到大三）
bg:&nbsp;末流985技术岗&nbsp;实习经历:&nbsp;（大一）绿盟TVM，（大二上）小红书基础架构，（大二下）腾讯PCG实习意义:技术岗多段大厂实习会很吃香【1.】赶在秋招前可以提升技术深度和广度，对比同届在简历和面试上更有优势，同一个问题你实习中实践过和单纯背过的差距是显而易见【2.】提前知道每个公司薪资水平，部门发展和竞争压力，包括公司裁员速度与坑点。例如某司平均在职1.8年，如果技术不行，不提前了解进去等着裁？某司早11晚11，工作六天。某司pua实力强，进去全是牛鬼蛇神？【3.】可以拥有自己小金库，和同层次的朋友吃喝聊八卦，和部门同事约饭知道很多信息差。同批校招中你怎样成长速度更快？okr...
iu圈外男友：太强了希望以后能做同事
牛客激励计划
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
12-19 12:07
点赞 评论 收藏
分享
11-01 19:18
蚌埠坦克学院 智能驾驶系统工程师
不是哥们
这面试时间是认真的吗😰
Natrium_：这时间我以为飞机票
点赞 评论 收藏
分享
11-15 18:12
北京航空航天大学 算法工程师
点赞 评论 收藏
分享
12-19 16:16
西南交通大学 用户运营
急招产品运营实习
公司：科大讯飞职位名称：智算平台工单产品运营实习生工作地点：科大讯飞薪资范围：100-150元/天岗位职责：-&nbsp;协助管理平台运维团队的日常运作，确保工单的高效流转。-&nbsp;接收用户提交的问题和请求，进行初步分类并分发给技术支持人员。-&nbsp;跟踪工单状态，及时更新和关闭，通知用户处理进度。-&nbsp;定期生成工单处理报告，分析数据以发现潜在问题。-&nbsp;参与优化工单处理流程，提高服务质量和效率。-&nbsp;与技术团队合作，提供培训和指导，提升工单处理能力。-&nbsp;了解最新IT技术和工具，以更好地支持团队和用户。招聘要求：1.&nbsp;在校大学生，计算机科学、信息技术或相关专业优先。2.&nbsp;对IT系统管理和工单处理有浓厚兴趣，愿意学习相关...
投递科大讯飞等公司10个岗位 >
点赞 评论 收藏
分享
评论
8
11
分享

招聘动态

查看更多

快手

2025届校园招聘

26届实习社群招新啦！

全站热榜

正在热议
# 秋招感动瞬间 #
3334次浏览 54人参与
# 你都收到了哪些公司的感谢信？ #
3790101次浏览 32695人参与
# 被同事甩锅了怎么办 #
10596次浏览 74人参与
# 职场吐槽大会 #
99751次浏览 808人参与
# 上班到公司第一件事做什么？ #
20162次浏览 214人参与
# 哪个瞬间让你对大厂祛魅了？ #
162174次浏览 1003人参与
# 如何一边实习一边秋招 #
1056558次浏览 13160人参与
# 打杂的实习你会去吗？ #
90864次浏览 813人参与
# 工作压力大怎么缓解 #
41144次浏览 707人参与
# 通信硬件知识分享 #
2414次浏览 38人参与
# 小米求职进展汇总 #
609813次浏览 4715人参与
# 想实习转正，又想准备秋招，我该怎么办 #
518660次浏览 5208人参与
# 实习与准备秋招该如何平衡 #
762583次浏览 8791人参与
# 字节跳动工作体验 #
247415次浏览 3248人参与
# 毕业后不工作的日子里我在做什么 #
126715次浏览 1150人参与
# 测测你的职业性格 #
16255次浏览 210人参与
# 选择和努力，哪个更重要？ #
27146次浏览 290人参与
# 机械人还在等华为开奖吗？ #
166098次浏览 864人参与
# 今年形式下双非本找得到工作吗 #
63007次浏览 567人参与
# 我的实习求职记录 #
6366755次浏览 85567人参与
牛客网
牛客企业服务