Codeforces Round 1042 (Div. 3)

Problem - F - Codeforces ​

题目类型 ​

#数论 #前缀和 #二分

解题思路 ​

通过公式推理，转换求解函数，通过二分查找 prea(x) = preb(y) 的分界点，然后通过前缀和求累加和，公式推理如下：

$$\min(A, B) = \frac{A + B}{2} - \frac{|A - B|}{2}$$

$$f(x, y) = \min(\text{cnt}_0(x, y), \text{cnt}_1(x, y)) = \frac{\text{cnt}_0(x, y) + \text{cnt}_1(x, y)}{2} - \frac{|\text{cnt}_0(x, y) - \text{cnt}_1(x, y)|}{2} = \frac{x + y}{2} - \frac{|\text{cnt}_0(x, y) - \text{cnt}_1(x, y)|}{2}$$

$$\sum f(x, y) = \sum \frac{x + y}{2} - \sum \frac{|\text{cnt}_0(x, y) - \text{cnt}_1(x, y)|}{2} = \frac{n^2(n + 1)}{2} - \frac{\sum |\text{cnt}_0(x, y) - \text{cnt}_1(x, y)|}{2}$$

$$|\text{cnt}_0(x, y) - \text{cnt}_1(x, y)| = |\text{cnt}_0(x, 0) + \text{cnt}_0(0, y) - \text{cnt}_1(x, 0) + \text{cnt}_1(0, y)| = |(\text{cnt}_0(x, 0) - \text{cnt}_1(x, 0)) - (\text{cnt}_1(0, y) - \text{cnt}_0(0, y))|$$

$$\text{prea}(x) = \text{cnt}_0(x, 0) - \text{cnt}_1(x, 0)$$

$$\text{preb}(y) = \text{cnt}_1(0, y) - \text{cnt}_0(0, y)$$

$$|\text{cnt}_0(x, y) - \text{cnt}_1(x, y)| = |\text{prea}(x) - \text{preb}(y)|$$

参考：Codeforces Round 1042 (Div. 3) Editorial - Codeforces

示例代码 ​

def helltractor():
    for _ in range(II()):
        n = II()
        a = I()
        b = I()

        a0 = [0] * (n + 1)
        a1 = [0] * (n + 1)
        b0 = [0] * (n + 1)
        b1 = [0] * (n + 1)
        for i in range(n):
            a0[i + 1] = a0[i] + (a[i] == "0")
            a1[i + 1] = i + 1 - a0[i + 1]
            b0[i + 1] = b0[i] + (b[i] == "0")
            b1[i + 1] = i + 1 - b0[i + 1]

        delta_a = [a0[i] - a1[i] for i in range(n + 1)]
        delta_b = [b1[i] - b0[i] for i in range(1, n + 1)]
        delta_b.sort()

        sum_db = list(accumulate(delta_b, initial=0))
        res = 0
        for x in range(1, n + 1):
            val = delta_a[x]
            idx = bisect_left(delta_b, val)
            res += val * idx - sum_db[idx]
            res += (sum_db[n] - sum_db[idx]) - val * (n - idx)

        ans = n * n * (n + 1) / 2 - res / 2
        print(ans)