【秋招笔试-试读版】9.14京东秋招(已改编)-三语言题解

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

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

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

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

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

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍠 京东秋招笔试，来啦！！！

🍥 本次的京东是较为简单的一场，前两题比较白给，最后一题是最小生成树，看出来也就不难了

1️⃣ 前后缀分解求最大乘积，比较简单

2️⃣ 自定义排序

3️⃣ 最小生成树的应用，不难

本次的三题已全上OJ啦

🎗️ 01.LYA 的珍珠项链

评测链接🔗

问题描述

LYA 是一位珠宝设计师，她最近设计了一条独特的珍珠项链。这条项链由 $n$ 颗珍珠组成，每颗珍珠都有其独特的价值。LYA 想要将这条项链切割成两部分，以制作成一对手链。

为了使这对手链看起来协调，LYA 决定将项链切割成两部分，使得左边部分珍珠的总价值乘以右边部分珍珠的总价值最小。她希望你能帮她计算出这个最小值。

输入格式

第一行输入一个整数 $n$，表示珍珠项链的长度。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n$，表示每颗珍珠的价值。

输出格式

输出一个整数，表示切割后两部分珍珠总价值的乘积的最小值。

样例输入

5
1 2 3 4 5

样例输出

14

样例解释

将项链在第一颗珍珠后切割，左边部分价值为 1，右边部分价值为 14（2+3+4+5=14），乘积为 14，这是最小的可能值。

数据范围

• $2\le n\le 10^6$
• $-10^3\le a_i\le 10^3$

题解

前后缀分解

1. 算出总和 $sum$ 后对原数组进行遍历
2. 维护一个 $lsum$ 表示数组左边的和，最后答案为 min($lsum\times (sum-lsum)$)

⚠️ 会爆 int，CPP和Java选手要注意

参考代码

🔒订阅专栏后解锁 $\to$ 🧷春秋招笔试合集

📚 02.LYA的书籍整理

评测链接🔗

问题描述

LYA是一位图书馆管理员，她最近收到了一批新的书籍。这些书籍需要按照特定的规则进行排序和整理。LYA发现每本书的书名都是由小写字母组成的，但图书馆有一套独特的字母排序规则。

为了帮助LYA更好地整理这些书籍，你需要编写一个程序，根据给定的字母排序规则，对书名进行排序。排序规则如下：

1. 比较两个书名时，从左到右逐个字符比较。
2. 字符的大小关系由给定的字母顺序决定。
3. 如果一个书名是另一个书名的前缀，较短的书名排在前面。

输入格式

第一行输入一个字符串，包含 26 个不同的小写字母，表示字母的排序规则。字母在字符串中出现的顺序即为它们的排序顺序。

第二行输入一个整数 $n$，表示书籍的数量。

接下来 $n$ 行，每行包含一个小写字母组成的字符串 $s_i$，表示一本书的书名。

输出格式

按照排序规则从小到大输出排序后的书名，每行一个字符串。

样例输入

abcdefgijklmnpqrstuvwxyz
3
aaaa
aac
aaaa

样例输出

aaa
aac
aaaa

数据范围

• $1\le n\le 1000$
• $1\le |s_i|\le 1000$

题解

自定义排序

按照给定的字符权重进行自定义排序。

还有一种简单的办法是直接吧字符串映射成一个 [0, 25] 的权值数组，直接按照默认排序

参考代码

🔒订阅专栏后解锁 $\to$ 🧷春秋招笔试合集

🌇 03.LYA的城市规划

评测链接🔗

问题描述

LYA是一个新兴城市的规划师。她的任务是设计一个由 $n$ 个区域组成的城市网络。每个区域都有其独特的地理坐标 $(x_i,y_i)$。为了促进区域间的交流，LYA决定在这些区域之间修建道路。

城市有多个建设团队，每个团队的施工速度都是每年1个单位距离。每个区域的负责人会向所有其他区域派遣建设团队，沿着最短路径修建道路。当两个来自不同区域的建设团队相遇时，这两个区域就被认为是连通的。

LYA想知道，最少需要多少年，所有的区域才能全部连通起来。两个区域被认为是连通的，当且仅当它们之间存在一条直接或间接的道路。

输入格式

第一行包含一个整数 $n$ $(1\le n\le 1000)$，表示城市区域的数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ $(-10^8\le x_i,y_i\le 10^8)$，用空格分隔，表示第 $i$ 个区域的坐标。

输出格式

输出一个整数，表示所有区域连通所需的最少年数。如果计算结果不是整数，请向上取整。

样例输入

3
0 0
0 5
6 0

样例输出

3

样例解释

当坐标为 $(6,0)$ 和 $(0,0)$ 的区域连接时，所有区域都连通了，这需要3年。

数据范围

• $1\le n\le 1000$
• $-10^8\le x_i,y_i\le 10^8$

题解

最小生成树

将问题精简一下；

1. 每对区域之间都有一条潜在的道路。
2. 道路的"权重"是两个区域之间距离的一半（因为两边同时开始建设）。关键
3. 需要找到一种方式，使所有区域连通，且最长的道路长度最小。

那比较熟悉图论的朋友可能就 我悟了，没错，问题转换完之后就是经典的最小生成树问题了。

我们采用 kruskal 的办法来解决

解题步骤：

1. 计算所有区域对之间的距离，并除以2（因为双向施工）。
2. 将所有可能的连接按照距离排序。
3. 使用并查集来跟踪区域的连通性。
4. 从最短的连接开始，如果两个区域还没有连通，就连接它们。
5. 记录最后一次连接的距离，这就是我们需要的时间。

时间复杂度分析：

• 计算距离：$O(n^2)$
• 排序：$O(n^2\log n)$
• 并查集操作：$O(n^2\alpha (n))$，其中 $\alpha (n)$ 是阿克曼函数的反函数，实际上可以认为是常数。

总的时间复杂度是 $O(n^2\log n)$，对于 $n\le 1000$ 的数据范围来说是可以接受的，python选手比较危险

参考代码

🔒订阅专栏后解锁 $\to$ 🧷春秋招笔试合集