codeforces：C. Zero-Sum Prefixes【前缀和 + 倒序贪心】

题目截图

题目分析

• 这道题很容易想到前缀和
• 改变后面的0不会影响前面的
• 前面的改完后，后面的可以再见机行事
• 每个0都希望后面（包括他）的前缀和变越多0越好
• 因此，统计每个0后面出现最多次数的前缀和的次数，统计完之后dict清0
• 这样保证了每个num = 0后面可以使得最多的preSum = 0
• 特别地，对于前缀没有0的那一段，直接统计preSum直接为0的个数

ac code

import sys
from itertools import accumulate
input = sys.stdin.readline
from collections import defaultdict

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    preSum = list(accumulate(a))

    # 若某个位置为0，统计其后面出现次数最多的即可
    # 倒序统计
    # 每次遇到一个0清空
    # 可以调整下一个0的数，使得下一个0后面出现次数最多的仍然保持为0
    ans = 0
    d = defaultdict(int)
    maxn = 0
    for i in range(n - 1, -1, -1):
        d[preSum[i]] += 1
        maxn = max(maxn, d[preSum[i]])
        if a[i] == 0:
            ans += maxn
            d = defaultdict(int)
            maxn = 0
    # 统计最前面没有遇到0但前缀和是0的个数
    ans += d[0]
    return print(ans)







if __name__ == '__main__':
    for _ in range(int(input())):
        solve()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结

• 前缀和很自然
• 改一个会影响后面的前缀和，同增同减
• 为了让更多的变成0，我们要贪心地让每个num = 0能变0的preSum最多，这就是统计其后面出现次数最多的前缀和即可
• 注意，比如倒数第二段使得多个preSum改成了0，倒数第一段只需修改num = 0的值，依然可以保持最多次数的前缀和全部为0
• 因此，为了保证互不干扰，应该倒序遍历统计出现次数最多的
• 如果顺序统计，还需要额外记录preSum的位置，会超出复杂度