笔试题 1

字节跳动

[难度: 1 星] 开火车

问题描述

小 Byte 和小 Dance 在玩一种叫“开火车”的纸牌游戏，游戏规则如下：

1. 初始给两人随机平分 52 张扑克牌，每个人 26 张；
2. 小 Byte 先开始，将第一张牌放下；
3. 随后两人轮流按顺序（按从第 1 张到最后 1 张的顺序出牌，手牌中的顺序不可以被打乱）放置扑克牌，后一张扑克牌压在前一张扑克牌上；
4. 如果出现之前放下的某张扑克牌 $s$ 与将要放下的扑克牌 $t$ 点数相同，则当前玩家获得从 $s$ 到 $t$ 之间的所有牌（包括 $s$ 和 $t$ 这两张牌）；
5. 玩家手上的 26 张牌都出完后，游戏结束。并清点双方获得的牌数，牌数多的玩家获胜，若两名玩家牌数相同，则平局。

输入格式

输入包括两行，每行 26 个数字，分别表示两位玩家初始被随机分配到的牌的点数，第一行为小 Byte 被分到的牌。

输出格式

若平局则输出 Draw，否则输出获胜玩家的名字（Byte 或者 Dance）。

输入样例

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

输出样例

Byte

样例说明

对于样例输入，最终小 Byte 获得 31 张牌，小 Dance 获得 19 张牌，剩下两张点数为 6、9 的牌。

数据范围

所有数字都在区间 $[1,13]$ 内。数据保证所有点数分布与扑克牌点数相同。

解题思路

按题意模拟即可。

[难度: 1 星] 成立天数

问题描述

2019 年 3 月 12 日，全球的 Bytedancer 共同庆祝字节跳动成立七周年。七年前的今天，初创团队把营业执照领回锦秋家园，七年后的今天，字节跳动在不断地快速成长，吸纳全球优秀的人才加入。

为了纪念 2012 年 3 月 12 日这个重要的日子，我们希望能够对于之后的任何一个日期，计算出公司已经成立了多少天。人工计算或者 Excel 表操作是费时的，我们希望你能实现这个功能，并期待优秀的你加入我们。

输入格式

第一行为一个整数 $T$，表示有 $T$ 组数据，接下去 $T$ 行，每行三个整数 $y,m,d$，分别表示年、月、日。

输出格式

对于每组数据，输出 1 个整数，表示从 2012 年 3 月 12 日到给出的日期经过了多少天。

输入样例

2
2012 3 13
2019 3 12

输出样例

1
2556

数据范围

1 <= T <= 100, 2012 <= y <= 9999, 1 <= m <= 12, 1 <= d <= 31

数据保证给出的日期合法，且在 2012 年 3 月 12 日之后。

解题思路

2012/3/12 距 2011/12/31 有 72 天，计算给出的日期距 2011/12/31 有多少天，这样可以按整年、整月地计算，将计算得到的值减去 72 就是答案。

最后注意平年闰年的二月份。

[难度: 2 星] 小班教学

问题描述

Bytedance 决定对所有新人展开一次针对性的培训。公司有很多新人，每个人想学的内容都不一样。限制每个人只能在本次培训中学习一门课程，经过统计，新人们总共想学 $n$ 门课程，每门课程报名的人数分别为 $a_1,a_2,\cdots,a_n$。为了保证公平与方便管理，公司决定采用小班教学模式，所有的小班内人数相同，同一班级内的课程内容相同。由于人力有限，我们期望在满足以上前提条件的同时，班级数量尽可能地少，问：最少需要开多少个小班。

输入格式

第一行为一个整数 $n$，表示有 $n$ 门课程，第二行为 $n$ 个整数，每个整数之间用一个空格分隔，分别为 $a_1,a_2,\cdots,a_n$，表示门课程的报名人数。

输出格式

输出最少需要开多少个小班。

输入样例

3
1 1 2

输出样例

4

数据范围

对于 $50\%$ 的数据，$1\leq n\leq10000,1\leq a_i\leq1000$

对于 $70\%$ 的数据，$1\leq n\leq10000,1\leq a_i\leq1000000$

对于 $100\%$ 的数据，$1\leq n\leq1000000,1\leq a_i\leq2^{31}-1$, 答案不超过 int 能表示的范围

解题思路

1. 暴力解法是枚举所有可能的每个班级的人数，由班级人数计算需要分班的数量，取最小值，完全暴力枚举的做法可以通过 $50\%$ 的数据，如果及时加一些 break 剪枝可以通过 $70\%$ 的数据，最后 $30\%$ 的数据每个数字都有至少 1000 个约数，所以有 1000 个数字无法通过 break 优化；

2. 由于每个班级的人数越多，分班数量越少，而且要求满足每门课程的分班人数都相等，所以每个班的人数都要能整除每一门课程的人数，因此每个分班的最大人数就是这 $n$ 个数字的最大公约数，求最大公约数用辗转相除法，暴力枚举最大公约数的话，也无法通过最后的 $30\%$ 数据。

最后注意 $n$ 个数字的和爆 int。

[难度: 2 星] 封路工程

问题描述

在一个交通非常便捷的城市，总共有 $n$ 座建筑，建筑有 $A$ 和 $B$ 两种类型，建筑之间存在 $m$ 条相互连通的双向道路，任意两个城市之间可以直接或间接地通过道路相互到达，经过长时间的调研市长发现建筑之间的通道过多导致维护成本远高于收益，因此决定尽可能多地停用一些道路。

停用道路之后，城市之间仍然要保持便捷的交通，最终决定剩余的道路应满足以下要求：

1. $n$ 个建筑之间仍然可以直接或间接地相互到达；
2. 同类型的建筑之间不能直接到达，即：$A$ 类建筑只能直接到达 $B$ 类建筑，$B$ 类建筑只能直接到达 $A$ 类建筑；
3. 在满足以上条件的前提下，停用道路的数量应尽可能多。

现在将规划的任务交给你，请给出一个合理的方案。

输入格式

第一行为两个整数 $n$ 和 $m$，表示有 $n$ 座建筑和 $m$ 条道路，第二行为一个长度为 $n$ 的字符串，字符串只包含 $A$ 和 $B$，第 $i$ 位字母表示第 $i$ 座建筑的类型，接下去 $m$ 行每行两个整数 $u,v$，表示第 $u$ 座建筑和第 $v$ 座建筑之间有一条道路可以直接到达。

输出格式

第一行为一个整数 $k$，表示要继续运营的道路数量，第二行为 $k$ 个整数，每个整数表示一个道路编号，道路按照输入顺序从 1 开始编号。如果有多解输出任意一个即可，注意输入的编号必须在区间 $[1,m]$ 内，且两两互不相等。

输入样例

4 6
AABB
3 4
2 1
4 2
3 1
1 4
2 3

输出样例

3
5 3 4

数据范围

对于 $70\%$ 的数据，$1\leq n,m\leq1000$

对于 $100\%$ 的数据，$1\leq n\leq100000,~1\leq m\leq\min(\frac{n(n-1)}{2},100000),~1\leq u,v\leq n,~u\neq v$

数据中不存在重复的无序对 $(u,v)$，保证至少存在一组解。

解题思路

选择任意一个节点开始搜索（bfs 或者 dfs），搜索过程中若相邻节点类型相同则不搜索对应边，已经搜索到的节点不再继续搜索，最后必然得到一个 $n-1$ 条边的树形结构，将搜索过程中跑过的边的编号输出，就是答案。

用邻接矩阵可以通过 $70\%$ 的数据，用邻接链表或 vector 数组或链式前向星等结构可以通过 $100\%$ 的数据。

[难度: 3 星] 最长时延

问题描述

在一个树形的网络结构中，总共有 $n$ 个节点，它们在传输数据的过程中会产生各种时延，如节点处理时延、排队时延、传输时延、传播时延等，我们将所有传输过程中产生的时延求和取均值统一为一个数值。

为估计整个网络的效率，现在需要抽取某些网络节点，并计算在所有可能传输到的其他节点中，最长的总时延，如节点 $A$ 到节点 $B$ 的时延为 $x$ 毫秒，节点 $B$ 到节点 $C$ 的时延为 $y$ 毫秒，则节点 $A$ 到节点 $C$ 的总时延为 $x+y$ 毫秒，由于网络中存在大量的节点以及多次的抽样，你的程序需要用尽可能高效的方式运行以得到结果。

输入格式

第一行为一个整数 $n$，接下去 $n-1$ 行每行三个整数 $u,v,w$，表示节点 $u$ 与节点 $v$ 之间的时延为 $w$。第 $n+1$ 行为一个整数 $q$，表示有 $q$ 次抽样，接下去 $q$ 行每行一个整数 $pos$，表示被询问的节点编号。

输出格式

对于每个被抽样的节点，输出该节点到网络中所有其他节点的最大总时延。

输入样例

4
1 2 10
1 3 5
4 1 3
2
2
4

输出样例

15
13

数据范围

对于 $50\%$ 的数据，$1\leq n\leq1000,~1\leq q\leq1000$

对于 $70\%$ 的数据，$1\leq n\leq1000,~1\leq q\leq1000000$

对于 $100\%$ 的数据，$1\leq n\leq1000000,~1leq q\leq1000000,~1\leq u,v,pos\leq n,~1\leq w\leq100000$

数据保证结构为一棵树。

解题思路

1. 直接暴力对每个点 bfs 或 dfs 能通过前 $50\%$ 的数据；

2. 先对每个点暴力 bfs 或 dfs 预处理，将答案存到每个点上，可以通过 $70\%$ 的数据；

3. 用 $dp_i$ 记录到达节点 $i$ 的最大时延，首先有 dp 公式：
   

   $$dp_i=\max(dp_j+dis_{i,j})$$
   $j$ 为所有与节点 $i$ 相邻的节点。

   然后对整棵树进行两次 dfs，第一次从叶子节点往根节点 dp，可以得到所有节点到其子树上所有节点的最大时延，第二次从树根往叶子节点 dfs，将父节点的信息传到子节点，相当于将兄弟节点的信息传给该子节点，这里需要注意如果是从父节点 $f$ 传到子节点 $pos$，则需要取的是 $f$ 所记录的 $pos$ 的兄弟节点子树的信息（不能包含 $pos$ 所在子树的信息，否则会出错），这里需要预处理所有子节点的前缀 Max 与后缀 Max 以 $O(1)$ 求解得到该值，暴力求解的话其中一组数据返回超时（某个节点与所有其他节点相邻的情况，会被卡成 $O(n^2)$）。