T1 乒乓球

乒乓球，被称为中国的“国球”，是一种世界流行的球类体育项目。一局比赛的获胜规则如下：
当一方赢得至少11分，并且超过对方2分及以上时，获得该局的胜利。
按照上述规则，小美和小团正在进行一局比赛，当前比赛尚未结束，此时小美的得分为a，小团的得分为b。小美想知道，在
最理想的情况下，她至少还要得多少分才可以赢下这场比赛。
输入描述
输入两个整数a、b。a表示当前小美获得的分数，b表示小团的分数。
0≤ a,b≤ 99.保证输入的比分合法，并且在该比分下比赛尚未结束。

输出猫述
输出一个整数，表示小美至少还要得多少分才能获得这局比赛的胜利。

input:
30 31

output:
3

签到题。

a, b = list(map(int, input().split()))
if a >= 11 and a - b > 2:
    print(0)
else:
    print(max(11, b + 2) - a)

T2 mex

若S表示一个非负整数集合，mex(S)的值为不属于集合S的最小非负整数。例如，mex({0,1,4})=2，mex({1，2})=0。
有n个互不相同的非负整数a1，a2，…an构成了一个非负整数集合A。小美想知道若将a；(1≤i≤n)从集合A中删除，剩下的n-
1个数构成的新集合A'的mex值为多少？请输出i从1到n所有取值下新集合的mex值。
输入描述
第一行输入一个整数n，表示集合A的大小。
第二行输入n个整数a1，a2,…an。
n<5e4,ai≤1e9，保证ai互不相同。数字间两两有空格隔开。

输出描述
输出n个整数，相邻两个数之间用空格隔开。其中第i个数表示从集合A中删除aj，剩下n-1个数构成的新集合的mex值。

input:
4
5 0 3 1

output:
2 0 2 1

首先求得原数组的mex值。删除一个数的时候，如果比这个mex值大，则不影响mex值，否则删除的数字为新的mex值。

n = int(input())
a = list(map(int, input().split()))
ans = []
s = set(a)
cnt = 0
for i in range(n + 2):
    if i not in s:
        cnt = i
        break

print(*[min(cnt,a[i]) for i in range(n)])

T3 字母树

给定一棵有n个节点的树，节点用1,2,…n编号。1号节点为树的根节点，每个节点上有一个用大写字母表示的标记。求每个
节点的子树中出现的字母标记种类数。
注：子树的定义：设T是有根树，a是T中的一个顶点，由a以及a的所有后裔（后代）导出的子图称为有根树T的子树。
输入描述
第一行输入一个正整数n，表示树的节点数量。
第二行输入n-1个正整数，第i个整数表示第i+1号节点的父亲节点。
第三行输入长度为n的由大写字母组成的字符串s1s2s3...sn，第i个字符si表示第i号节点的标记。
3≤n≤50000.
数据保证形成一棵合法的树，字符串由大写字母组成。
输出描述
输出n个整数，相邻两个数之间用空格隔开，第i个整数表示第i号节点的子树中出现不同的字母种类数。

input:
6 
1 2 2 1 4
ABCCAD

output:
4 3 1 2 1 1

经典树遍历，因为只需要计算某个节点及其子树的出现的字母种类数，那么可以利用状态压缩的思想。假设你有一个26位的整数，某一位为0表示某个字母没出现过，某一位为1表明某字母出现过。比如10000000..0，表示只有一个A。

后序遍历即可，每次把子节点的结果汇聚到父节点。

n = int(input())
fa = list(map(int, input().split()))
s = input()
ans = [0] * n
g = [[] for _ in range(n)]
for i, c in enumerate(fa, start=1):
    g[c - 1].append(i)


def solve(cnt):
    v = (1 << (ord(s[cnt]) - ord('A')))
    for nxt in g[cnt]: v |= solve(nxt)
    ans[cnt] = bin(v)[2:].count('1')

    return v


solve(0)
print(*ans)

T4 任务

有n个城市，城市从1到n进行编号。小美最初住在k号城市中。在接下来的m天里，小美每天会收到一个任务，她可以选择完
成当天的任务或者放弃该任务。第i天的任务需要在ci号城市完成，如果她选择完成这个任务，若任务开始前她恰好在ci号城
市，则会获得ai的收益；若她不在c号城市，她会前往c号城市，获得bi的收益。当天的任务她都会当天完成，任务完成后，
她会留在该任务所在的ci号城市直到接受下一个任务。如果她选择放弃任务，她会停留原地，且不会获得收益。小美想知道，
如果她合理地完成任务，最大能获得多少收益？

输入描述
第一行三个正整数n，m和k，表示城市数量，总天数，初始所在城市。
第二行为m个整数c1, c2...cm，其中ci表示第i天的任务所在地点为ci
第三行为m个整数a1, a2...am，其中ai表示完成第i天任务且地点不变的收益。
第四行为m个整数b1, b2...bm，其中bi表示完成第i天的任务且地点改变的收益。
1<=k,ci<=n<=3e4
1<=m<=3e4
0<=ai,bi<=1e9

输出描述
输出一个整数，表示小美合理完成任务能得到的最大收益。

input:
3 5 1
2 1 2 3 2
9 6 2 1 7
1 3 0 5 2

output:
13

先考虑一个自顶向下的dp，考虑函数f(i, k)，表示从第i个任务开始，当前所在位置为k可以得到的最大收益。不难写出，一共有3种情况：

1. 不完成这个任务，直接选择f(i+1, k)
2. 完成这个任务，且c[i]==k，那么此时贡献为f(i+1, k)+a[i]
3. 完成这个任务，且c[i]!=k，那么此时贡献为f(i+1, c[i])+b[i]

选大的即可，可以写出如下代码：

n, m, k = list(map(int, input().split()))
c = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

@lru_cache(None)
def f(i, k):
    if i == m: return 0
    if c[i] == k: return f(i+1, k) + a[i]
    return max(
        f(i + 1, k),
        f(i + 1, c[i]) + b[i]
    )
print(f(0, k))

因为n和m都是3e4，上面这个代码复杂度显然无法全部通过。现在考虑优化：

假设现在位置为k，当前任务所在地为c[i]。c[i]==k很好考虑，直接加上即可。如果c[i]!=k呢？我们需要考虑的是从某一个非k的位置转移过来。

注意，c[i]!=k时，我们只需要找一个非k的位置转移过来即可，并不需要考虑从哪个位置过来。而且无论从哪个位置转移过来，假设是j位置，贡献都是 上一次到达j位置的最大贡献+b[i]。那么我们只需要找到最大的上一次到达j位置的最大贡献。

我们可以维护一个数组pre，pre[i]表示上次到达i位置可以获得的最大价值，利用这个数组，我们可以构造一版，假设当前位置为c[i]：pre[c[i]]=max(pre[c[i]], max{pre[j]+b[i] for j in range(1,n+1) if j!=c[i]} )

但是仍然不够，遍历pre仍然是一个n^2的过程，我们需要继续优化。可以发现，上面的pre[j]和i是无关的。我们每次转移的时候，只需要找到最大的pre[j]即可。但是如果单纯维护一个pre[j]，有可能j和c[i]是相等的，可能造成转移出问题。那么我们只需要维护2个最大的pre[j]，这样可以保证一定有一个值和c[i]不相等，最终达成一个时间复杂度O(n)的解法。

n, m, k = list(map(int, input().split()))
c = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

h = [(0, i) for i in range(1, n + 1)]
pre = [-1] * (n + 1)
pre[k] = 0
v1 = (0, k) # 最大
v2 = (0, 0) # 次大

for i in range(m):
    v = 0
    # 直通
    if pre[c[i]] != -1:
        v = max(v, pre[c[i]] + a[i])

    if c[i] != v1[1]:
        v = max(v, v1[0] + b[i])
    elif c[i] != v2[1]:
        v = max(v, v2[0] + b[i])

    pre[c[i]] = max(pre[c[i]], v)

    if v > v1[0]:
        if c[i] == v1[1]:
            v1 = (v, c[i])
        else:
            v1, v2 = (v, c[i]), v1
    elif v > v2[0]:
        v2 = (v, c[i])

print(max(pre))