题解 | 喜欢切数组的红

while 1:
    try:
        n = int(input().strip())
        arr = list(map(int, input().strip().split()))
        sumnum = sum(arr)
        if sumnum % 3 != 0:
            print(0)
        else:
            part = sumnum // 3
            pos1 = []
            pos2 = []
            pos = []
            dp = [0]*(n+1)
            f = [0]*(n+1)
            count = 0
            for i in range(1, n+1):
                dp[i] = dp[i-1]+arr[i-1]
                if arr[i-1] > 0:
                    f[i] = f[i-1]+1
                else:
                    f[i] = f[i-1]
                if dp[i] == part:
                    pos1.append(i)
                elif dp[i] == part*2:
                    pos2.append(i)
            for i in pos1:
                for j in pos2:
                    if j>i and j<n+1:
                        pos.append([i, j])
            # print(pos)
            # print(f)
            for k in pos:
                if f[k[0]]>0 and f[k[1]]-f[k[0]]>0 and f[-1]-f[k[1]]>0:
                    count += 1
            print(count)

    except:
        break    

1) 题目约束转化

把数组切成 3 段，设切点为 (i, j)，对应三段：

• 第 1 段：[1..i]
• 第 2 段：[i+1..j]
• 第 3 段：[j+1..n]

要求：

1. 三段和相等
2. 每段至少有一个正数

2) 代码里的关键数组含义

dp[i]：前缀和

dp[i] = dp[i-1] + arr[i-1]

表示前 i 个数的和。

若总和是 sumnum，要三段相等必须 sumnum % 3 == 0，每段和 part = sumnum / 3。

于是切点要满足：

• 第一刀 i：dp[i] == part
• 第二刀 j：dp[j] == 2*part（因为前两段和应为 2*part）

代码里就把这些位置分别收集到 pos1、pos2。

f[i]：前缀中正数个数

if arr[i-1] > 0:

f[i] = f[i-1] + 1

else:

f[i] = f[i-1]

用它可以 O(1) 判断一个区间是否有正数：

• 第1段有正数：f[i] > 0
• 第2段有正数：f[j] - f[i] > 0
• 第3段有正数：f[n] - f[j] > 0（代码用 f[-1] 等价于 f[n]）

3) 统计方案数

代码先枚举所有满足和条件的 (i, j)（j > i），再检查三段正数条件，满足就 count += 1。

这就是完整正确性来源：

• dp 保证三段“和相等”
• f 保证每段“至少一个正数”