校招笔试疑难杂症记录

摘要: 记录一些在各种群里见过的有意思的或者比较难的题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

1 (阿里2020)

Tag: 图论，数学

描述

3 个人陆行，目的地有 n 家酒店，通过 n - 1 条道路连通，每两个酒店之间有一个唯一路径。

每个人有自己的偏好酒店，每个人选择自己的偏好酒店入住，第二天再去某个酒店集合。集合点距离三个人所选酒店距离值和最短。

每个人有一个偏好清单，每个人从各自清单中等概率地随机选一个。

问三个人从所选酒店到集合点的最短距离之和的期望是多少。

输入:

第一行 n(1 <= n <= 2e5)
接下来 n-1 行：a, b, c(1 <= a, b <= n, 1 <= c <= 1000) 表示酒店 a, b 间有通路，长度 c
最后 3 行: 每行代表一个人的酒店清单。首先一个正整数 k(1 <= k <= n)，之后输入 k 个不同的正整数 h1,h2,...,hk

输出:

一个数字代表期望，误差不超过 1e-6

别人的思路

性质猜想:

1. 距离值和最近的哪个点是唯一的
2. 三个人走的路径是没有重合的

xy 是树上的一条边，y 为父节点。考虑 A 经过这条边的概率:

(1) x->y: A 在以 x 为根的子树中, B, C 不在以 x 为根的子树中。
(2) y->x: B, C 在以 x 为根的子树中, A 不在以 x 为根的子树中。

预处理：每个节点为根的子树里有多少个 A, B, C。

---

2 (美团2021)

Tag: Trie

描述

一个数组，规定一个最长子数组的长度 K。对于一个子数组，有一个分数 score

score 等于子数组中数字的连续异或

求 长度不大于 K 的子数组中 score 的最大值

思路

暂无

---

3 (字节2021)

Tag: 搜索

描述

在经典八数码的基础上，有同学延伸出了一个十四数码游戏:

• 给定的 $4 \times 4$ 棋盘的初始状态，其中包含 14 个 1 到 14 编号的棋子和两个空位。
• 与空位相邻的棋子可以移动至空位，计作一次移动

求至少多少次移动才可以把棋盘恢复至标准状态，标准状态如下

1  2  3  4
5  6  7  8
9  10 11 12
13 14 _  _

思路

八数码问题在文章 滑动谜题和八数码 中解决过。

---