没想到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 接下来有n个数表示数列a的n个数（0 输出描述： 对于每个询问，输出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 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 比如上面的贡献是v，那么我们还剩下remain=y-x-v，如果remain<=k，显然我们一步把remain走完。如果remain>k，那么我们优先走k，直到走到remain 比如我们假设当前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')))#字节跳动##字节笔试#