字节跳动2023秋招研发第五场笔试【后端方向】题解
没想到9月底了我还在做字节笔试……
T1
某家族子孙众多，每个人只保留了部分的家族族谱，现在想知道该家族的第一代人是谁和第N代人的数量 现在给出N组数据，每组数据分别代表某一个人保留的部分族谱信息，如：[A B C]，表示当前C的父亲是B，B的父亲是A。 输入描述： 第1行输入为数值，代表有多少子族谱，数值范围在1-100 第2-n行输入为N组字符串数组，每组数组相当于一个家族关系的子链表，N<100 第n+1行输入表示要计算第n代人的数量，数值范围在1-100 输出描述： 第一行为字符串，家族第一代人的名称字符串 第二行为数值，第n代人的数量 input: 2 A B C B C D 4 output: A 1
拓扑排序就可以了。构造完图，找到入度为0的就是第一代，题目数据保证了第一代只有一个。
from collections import defaultdict, deque
n = int(input())
ru = defaultdict(int)
g = defaultdict(list)
for _ in range(n):
line = input().split()
for pre, nxt in zip(line, line[1:]):
g[pre].append(nxt)
ru[nxt] += 1
q = deque()
for i in g:
if ru[i] == 0:
print(i)
q.append((i, 1))
break
t = int(input())
ans = 0
while q:
cnt, v = q.popleft()
if v == t: ans += 1
for nxt in g[cnt]:
ru[nxt] -= 1
if ru[nxt] == 0:
q.append((nxt, v + 1))
print(ans)T2
双休在家的凯凯真的是太无聊了，他准备和他家的猫玩一个游戏。
给定一个长度为n的数列a0,a1,a2,a3,.…an-1,以及一个数k
求a数列有多少个满足以下条件的长度为k+1的子串
(2^0)*a_{i} < (2^1)*a_{i+1} < (2^2)*a_{i+2} < ... < (2^k)*a_{i+k}
这下喵喵不会做了，你可以帮帮它么？
输入描述：
会有多组询问
首先输入一个数字t(1<=t<=5)
接下来首先有两个数n，k，具体含义如题意所示。（3<=n<=1e5，0<k<n）
接下来有n个数表示数列a的n个数（0<ai<=1e8）
输出描述：
对于每个询问，输出a数列满足条件的长度为k+1的子串的个数
input:
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
output:
2
3
2
3
1
0其实就是找一个长度为k+1的子数组，数组中每一项*2都大于它的前一项。
只需要记录满足a[i]2>a[i-1]的连续次数，只要这个次数>k，说明可以组成一项。如果发现某一个位置a[i]2<a[i-1]，那么要重新开始计数。因为要求是子数组，那么只要这个位置不满足，任意子数组都不能包含这个位置。
for _ in range(int(input())):
n, k = map(int, input().split())
*a, = map(int, input().split())
ans = 0
pre = -1
cnt = 0
for i in a:
if i > pre / 2: cnt += 1
else: cnt = 1
pre = i
if cnt > k: ans += 1
print(ansT3
AB实验同学每天都很苦恼如何可以更好的进行AB实验，每一步的流程很重要，我们目标为了缩 短所需的步数。 我们假设每一步对应到每一个位置。从一个整数位置x走到另外一个整数位置y，每一步的长度是正整数，每步的值等于上一步的值-1，+0，+1。 求x到y最少走几步。并且第一步必须是1，最后一步必须是1，从×到y最少需要多少步。 样例说明： 整数位置×为12，另外一个整数位置y为6，我们需要从×走到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,3，2，1,所以我们需要走6步。 输入描述： 输入第一行包含一个整数n（1<=n<=1000），表示测试数组的组数， 以下每一行为一组数据。包含2个整数×，y。（0<=×<=y<2^31） 输出描述： 对于每一组数据，输出一行，仅包含一个整数，从x到y所需最小步数。 input： 3 12 6 34 45 50 30 output: 4 6 8
题目给的x和y不一定谁大，我们可以假定x<y。因为第一步和最后一步一定是1，那么假设我们走的步数中最大的数字为k，整个序列必然存在如下数字：1 2 3 ... k k-1 k-2 ... 1。可以计算得这里的贡献为(1+2+..+k)+(1+2+...+k-1)，用等差数列公式可以O(1)算出来这个贡献。然后考虑剩下的数字。
比如上面的贡献是v，那么我们还剩下remain=y-x-v，如果remain<=k，显然我们一步把remain走完。如果remain>k，那么我们优先走k，直到走到remain<k。
比如我们假设当前k=4，跑完第一轮贡献之后remain=9，显然我们尽可能走大步，先走2个4，再走1个1，变成1 2 3 4 4 4 3 2 1 1
如果k=4，跑完第一轮贡献之后remain=2，因为remain<=k，我们可以直接走一个2步。变成 1 2 3 4 3 2 2 1
def f(x):
return (1 + x) * x // 2
for _ in range(int(input())):
x, y = map(int, input().split())
if y < x: x, y = y, x
ans = y - x
for i in range(2, y - x):
v = f(i) + f(i - 1)
if v > y - x: break
r = y - x - v
ans = min(ans, 2 * i + r // i - int(r % i == 0))
print(ans)T4
题目描述 小明最近养了一只小狗，并且买了一袋狗粮，一共有M克。小狗每天可能会吃a_1,a_2,…,a_n 克，当剩余狗粮不足a_1,a_2,….,a_n中的最小值时,也算做一天。 小狗后一天吃的不会比前一天多，小明想知道这袋狗粮小狗吃完的情况有多少种 输入描述： 第一行：空格分割的小狗每天的食量，所有值都为正数并且不重复，最多10个 第二行：狗粮一共有多少克 输出描述： 一个数字，表示这袋狗粮小狗吃完的情况有多少种 input: 1 2 5 5 output: 4
经典dp，而且n很小，记忆化搜索，维护一下最大可选的数字即可。
from functools import lru_cache
import sys
sys.setrecursionlimit(int(2e5))
*a, = map(int, input().split())
a.sort()
m = int(input())
@lru_cache(None)
def f(x, pre):
if x <= a[0]: return 1
return sum(f(x - i, i) for i in a if i <= pre and i <= x)
print(f(m, float('inf')))#字节跳动##字节笔试#