字节跳动秋招笔试 – 20220925

1. 族谱还原

题目描述：
某家族子孙众多，每个人只保留了部分的家族族谱，现在想知道该家族的第一代人是谁和第N代人的数量
现在给出N组数据，每组数据分别代表某一个人保留的部分族谱信息，如：[A B C]，表示当前C的父亲是B，B的父亲是A。

输入描述：
第1行输入为数值，代表有多少子族谱，数值范围在1-100
第2-n行输入为N组字符串数组，每组数组相当于一个家族关系的子链表，N<100
第n+1行输入表示要计算第n代人的数量，数值范围在1-100

输出描述：
第一行为字符串，家族第一代人的名称字符串
第二行为数值，第n代人的数量

示例1：
输入：
2
A B C
B C D
4
输出：
A
1

示例2：
输入：
2
A B C
A B1 D
2
输出：
A
2

备注：
第N代人的数量可能为0

2. 二次方数组

题目描述：
双休在家的凯凯真的是太无聊了，他准备和他家的猫玩一个游戏。
给定一个长度为n的数列a0,a1,a2,a3..an-1，以及一个数k
求a数列有多少个满足以下条件的长度为k+1的子串

这下喵喵不会做了，你可以帮帮它么？

输入描述：
会有多组询问
首先输入一个数字t（1<=t<=5）
接下来首先有两个数n，k，具体含义如题意所示。（3<=n<=100000，0<k<n）
接下来有n个数表示数列a的n个数（0<ai<=100000000）

输出描述：
对于每个询问，找出a数列满足条件的长度为k+1的子串的个数

示例1：
输入：
6
4 2
20 22 19 84
5 1
9 5 3 2 1
5 2
9 5 3 2 1
7 2
22 12 16 4 3 22 12
7 3
22 12 16 4 3 22 12
9 3
3 9 12 3 9 12 3 9 12
输出：
2
3
2
3
1
0
说明：
样例一
子串[20,22,19] 1*20<2*22<4*19 满足要求
子串[22,19,84] 1*22<2*19<4*84 满足要求
所以输出2

样例二
子串[9,5] 1*9<2*5 满足要求
子串[5,3] 1*5<2*3 满足要求
子串[3,2] 1*3<2*2 满足要求
子串[2,1] 1*2=2*1 不满足
所以输出3

样例三
子串[9,5,3] 1*9<2*5<4*3 满足要求
子串[5,3,2] 1*5<2*3<4*2 满足要求
子串[3,2,1] 1*3<2*2=4*1 不满足
所以输出2

备注：
1<=t<=5
3<=n<=100000, 0<k<n
0<ai<=100000000

3. AB实验同学的冲刺

题目描述：
AB实验同学每天都很苦恼如何可以更好的进行AB实验，每一步的流程很重要，我们目标为了缩短所需的步数。
我们假设每一步对应到每一个位置。从一个整数位置x走到另外一个整数位置y，每一步的长度是正整数，每步的值等于上一步的值-1，+0，+1。求x到y最少走几步。并且第一步必须是1，最后一步必须是1，从x到y最少需要多少步。

样例说明：
整数位置×为12，另外一个整数位置y为6，我们需要从x走到y，最小的步数为：1，2，2，1，所以我们需要走4步。
整数位置x为34.另外一个整数位置y为45，我们需要从x走到y，最小的步数为：1，2，3，2，2，1，所以我们需要走6步。
整数位置x为50，另外一个整数位置y为30，我们需要从x走到y，最小的步数为：1，2，3，4，4，3，2，1，所以我们需要走6步。

输入描述：
输入第一行包含一个整数n（1<=n<=1000），即表示测试数组的组数，以下每一行为一组数据。包含2个整数x，y。（0<=x<=y<2^31）

输出描述：
对于每一组数据，输出一行，仅包含一个整数，从x到y所需最小步数。

示例1：
输入：
3
12 6
34 45
50 30
输出：
4
6
8

4. 喂狗粮

题目描述：
小明最近养了一只小狗，并且买了一袋狗粮，一共有M克。小狗每天可能会吃a_1,a_2,…,a_n克，当剩余狗粮不足a_1,a_2,…,a_n中的最小值时，也算做一天，小狗后一天吃的不会比前一天多，小明想知道这袋狗粮小狗吃完的情况有多少种

输入描述：
第一行：空格分割的小狗每天的食量，所有值都为正数并且不重复，最多10个
第二行：狗粮一共有多少克

输出描述：
数字，表示这袋狗粮小狗吃完的情况有多少种

示例1：
输入：
1 2 5
5
输出：
4

备注：
其中，1 <= a_1,a_2,…,a_n <= 10^4, 1 <= n <= 10
1 <= M <= 10^4 – 1