没想到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(ans

T3

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')))