Codeforces 1352E - Special Eleme

蔚蓝的天空，这么看起来，小区还是蛮好看的。请忽略右边的隔离带[狗头]。

翻译

特别的元素

请注意特殊的内存限制，64megabytes 大概是 64000000bytes。

这道题时间卡的也很紧，推荐使用静态类型语言，如果使用Python，推荐使用 PyPy 编写，尝试写高效的方案。

给一个数组 a = [a(1), a(2), ... , a(n)]，如果一个元素 a(i) 存在一对数字 l 和 r (1 <= l < r <= n) 使得 a(i) = a(l) + a(l+1) + ... + a(r)，那么它被称为特殊的元素。

打印出数组包含的特殊元素的个数。

如果数组中有多个相同的数字，并且是特殊元素，那么计算多次。

输入格式

第一行输入一个整数 t，接下来输入 t 组测试用例。

每个测试用例包含两行输入，第一行输入整数 n ，第二行输入 n 个数字。

保证，所有的 n 相加不大于 8000

输出格式

输出特别的元素个数。

分析

这道题要求内存不大于 64MB，并且时间为 1s。也就是说，需要 O(n^2) 的方案来解决问题。

为了计算每段数字的和需要三重for循环，也就是 O(n^3) 时间超标，需要优化。

可以滚动计算，使用上一个值的结果，但是这样空间复杂度是 O(n^2)，8000 * 8000 * 4 > 64MB。这个 4 是一个整数占用4个字节的意思。空间超标需要优化。

图中就是每一步需要计算的值，每个值表示当前位置到前面每段的和。

因为可以滚动计算，并别一边算一边用，所以用长度为 8001 的数组来存储结果即可，再申请一个 8001 的数组来存储每个数字的个数，滚动计算出一个值，就用这个数组来增加结果值，因为每个元素只计算一次，所以计算完要清空为0。

以上就是全部思路，其实这个内存的限制就是在提醒可以重用数组，滚动计算，同时可以减少代码的复杂度。

代码(PyPy3)

# https://codeforces.com/problemset/problem/1352/E

import sys

# sys.stdin = open(r"./file/input.txt", 'r')
# sys.stdout = open(r"./file/output.txt", 'w')

t = int(input())

for _ in range(t):
    n = int(input())
    arr = input().split(" ")
    arr = list(map(int, arr))
    # print(arr)

    number = [0] * (n + 1)
    add = [0] * (n + 1)
    result = 0

    for a in arr:
        number[a] += 1

    for i, a in enumerate(arr):
        for j in range(i + 1):
            add[j] += a
            if j < i and add[j] <= n:
                result += number[add[j]]
                number[add[j]] = 0

    print(result)

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.05.13 长春