不是自己的场，补题记录下。有问题欢迎随时私戳。

T1 数字乘积

有n个元素的数组，元素由[0,1,2,4,8,16,32,64,128,256,512,1024]组成；
现在想从数组中选择一段连续的区间，得到尽可能大的乘积；

输入一个t，代表有t组样例。每个样例有2行：
第一行是n，代表数组长度。
第二行是n个整数，取值为[0,1,2,4,8,16,32,64,128,256,512,1024]。

每个样例输出一行，表示乘积最大的区间[x,y]。如果有多个答案，输出x尽量小的答案。如果仍然有多个答案，输出y尽量小。

input:
2
5
1 2 4 0 8
7
1 2 4 8 0 256 0

output:
1 3
6 6

思路：普通模拟，遇到0就重新开始模拟。模拟过程中更新结果即可。

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    x, y, v = 0, 0, arr[0]
    l = 0
    cnt = 1
    for r in range(n):
        if arr[r] == 0:
            l = r + 1
            cnt = 1
        else:
            cnt *= arr[r]
            if cnt > v:
                x, y, v = l, r, cnt
            elif cnt == v:
                if l < x:
                    x, y = l, r
                elif l == x and r < y:
                    y = r
    print(x + 1, y + 1)

T2 特征加工计算

在特征加工过程中，我们经常会遇到特征加工依赖，如特征A的加工依赖特征B和特征C，特征C加工又依赖于特征D和特征E，为了保证特征能够正常加工出结果，要避免特征间出现循环依赖，如A依赖B，B又依赖A。现在给出一组待加工的特征，判断指定的特征能否计算出结果，为了简化理解，下面用数字表示特征。

1、输入包含多行数字，每行包含至少1列数字，每列之间用空格分开
2、第一行只有一列，表示输入数据行数
3、第二行是要判断的特征，会包含多列，需要判断这些特征是否能够被计算，特征数字范围（1-9）
4、从第三行开始，每行数字表示特征之间的依赖关系（第一列的特征依赖其他列的特征）。如：134，表示1依赖3和4。

输出多列数字，每列表示一个待判定特征的结果，1表示该特征能够计算出结果，0表示不能计算出结果。输出顺序和第二行待判断特征的顺序保持一致。

input:
3
1
1 2
2 3 1

output:
0

input:
3
1 2
1 2 3
2 4

output:
1 1

input:
3
1 2
1 2 3
2 4 1

output:
0 0

思路：经典拓扑排序，构造好图，然后直接排序即可。

from collections import deque, defaultdict, Counter

n = int(input())
targets = list(map(int, input().split()))
g = defaultdict(list)
ind = Counter()
for _ in range(n - 1):
    arr = list(map(int, input().split()))
    for i in arr[1:]:
        ind[arr[0]] += 1
        ind[i] = ind[i]
        g[i].append(arr[0])

q = deque()
for i in ind:
    if ind[i] == 0:
        q.append(i)
while q:
    cnt = q.popleft()
    for nxt in g[cnt]:
        ind[nxt] -= 1
        if ind[nxt] == 0:
            q.append(nxt)

print(*[0 if ind[i] else 1 for i in targets])

T3 翻转后连续子数组的最大和

给定整数数组，其中连续的0个或多个整数构成一个子数组，求翻转任一子数组后，新数组中子数组的和的最大值。

第一行输入为N，代表数组长度。n<=1e6
第二行输入为N个整数，依次为数组的每个元素

输出一个整数K，代表所有可能的新数组中子数组的和的最大值

input:
5
1 2 3 -1 4

output:
10

首先考虑一个子问题：如果我们不能翻转数组，如何求最大子数组和？这个题目是leetcode 53。这个子问题有一个非常经典的dp算法，可以在时间复杂度为O(n)的情况下求最大子数组和，具体可以查询题目题解。

如果我们可以求整体的最大子数组和了，如何转化为我们目前面临的问题呢？

不难看出，对一个子数组进行翻转，实际上就是删除了一部分元素。比如我们要翻转的区间是[l,r]，假设我们有一个k，且l<=k<=r，这个k为[l,r]内部，sum(a[l..k])最大的下标，也就是说，我们要删除[k+1,r]这段元素。使得a[l..k]可以和a[r+1..]接上。

那我们本次翻转，可以得到的最大子数组和就是：以a[k]为结尾的最大子数组和+以a[r+1]开头的最大子数组和。

以更简单的方式说明一下上述过程：

原来数组：a[l], a[l+1], ..., a[k], a[k+1], ..., a[r] a[r+1] a[r+2] ...
经过翻转：a[r], r[r-1], ..., a[k], a[k-1]，..., a[l] a[r+1] a[r+2] ...

因为我们要删除的是[k+1,r]这段元素，删除之后会使得数组分为2段。那我们反向考虑，如果我们要将数组分成2段，如何得到最大子数组和呢？也就是左边段的最大子数组和+右边段的最大子数组和。

用变量形式考虑：我们先确定一个k，以a[k]为结尾的最大子数组和为基准，然后找k的右侧最大的子数组和。根据我们的规则，这两段数组和是一定可以粘在一起的。只要我们遍历k，用O(1)的方式求出来k右侧最大的子数组和，那么我们就可以以一个总体O(n)的复杂度求得答案。

可以把数字分2段求：

1. 以a[k]为结尾的最大子数组和，这个很好求，不多说了。
2. k右侧最大的子数组和，也就是以k右侧任意点为起点，可以得到的最大子数组和。那么我们可以反向考虑，可以考虑从右往左，以j(j>k)为结尾的最大子数组和，这样求得这部分的方式可以像第一步一样容易。

n = int(input())
a = list(map(int, input().split()))

r_maxv = [0] * n
r_maxv[-1] = a[-1]
rmv = a[-1]
for i in range(n - 2, -1, -1):
    rmv = max(rmv + a[i], 0)
    r_maxv[i] = max(r_maxv[i + 1], rmv)

ans = r_maxv[0]
lmv = 0
for i in range(n - 1):
    lmv = max(lmv + a[i], 0)
    ans = max(ans, lmv + r_maxv[i + 1])
print(ans)

T4 删除一次得到子数组最大和

给定整数数组，我们称其中连续的0个或多个整数为一个子数组，求删除任一元素后，新数组中长度为k的子数组的和的最大值

第一行输入为N和K，N代表数组长度，K代表子数组长度。k<n<=1e6
第二行输入为N个整数，依次为数组的每个元素
输出一个S，代表所有可能新数组中长度为k的子数组和的最大值。

input:
5 3
2 1 3 -1 4

output:
8

思路：滑动窗口，考虑前k+1个元素的数组的和，然后删除这k+1个元素里面最小的元素，作为本轮贡献。然后这个数组向右滑动，每次增加一个新元素，删除一个旧元素，用堆维护一下历史元素，懒惰删除保证复杂度不会恶化就可以了。

from collections import Counter
from heapq import *

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
deld = Counter()  # lazy del
h = []
for i in range(k):
    heappush(h, a[i])

s = sum(h)
for i in range(k, n):
    heappush(h, a[i])
    s += a[i]
    while deld[h[0]]:
        deld[h[0]] -= 1
        heappop(h)

    ans = max(ans, s - h[0])

    s -= a[i - k]
    deld[a[i - k]] += 1
print(ans)