题解：P9127 [USACO23FEB] Equal Sum Subarrays G

zcq_qwq · 2025-05-26 10:59:38 · 题解

说在前面

感觉想了三天才做出来的自己跟个人一样……

小建议：把思路写在代码下面是一种非常好的习惯，容易梳理思路，记得多提问。具体怎么做看后面。

题目分析

接下来，我将带领你一步一步，从根开始，找到解题思路。

首先，题目要求改变 a _ i 的值，找到两个不同的连续子序列，它们的和相等。求 \min \{ |\Delta a _ i|\}。

其中，| 是绝对值的意思，就是把满足 a < 0 的数变成 -a。\Delta x 指的是 x 的改变量，也就是现在的 x 减去原来的 x。

现在思考：这两个序列有什么特点？

题目中提到：初始状态下没有两个和相等的连续子序列。所以，如果序列中不包含 a_i，那么显然是不行的。因为如果这两个序列与 a _ i 无关，则 a _ i 的变化与对两个序列的和没有影响。那么现在我们得出：两个序列中至少包含 1 个 a _ i。

包含两个行不行？也不行。因为如果两个序列都与 a _ i 有关，那么两个序列同时加上或减去一个相同的数，大小关系不变。

得出结论：只有一个序列包含 a _ i。

则问题转化为：找到一个包含 a _ i 的序列和一个不包含 a _ i 的序列，他们差值的绝对值最小。

那么我们先求出所有子序列的和：

for (int i = 1; i <= n; i++) { // 前缀和
    s[i] = s[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        sum[i][j] = s[j] - s[i - 1];
    }
}

然后，统计答案。但是直接做时间复杂度大的逆天，光枚举区间就得六重循环。所以，考虑优化。

先把区间信息存进结构体数组：

struct arr {
    int l, r, sum;
} b[N];
...
int cnt = 0;
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        b[++cnt] = {i, j, s[j] - s[i - 1]};
    }
}

随后，我们想一想：最小差值可能出现在什么地方？

是不是很简单？排序后数组相邻的两个数。

所以，按 sum 由小到大排序。

struct arr {
    ...
    bool operator < (const arr & x) const {
        return sum < x.sum;
    }
} b[N];
...
sort(b + 1, b + cnt + 1); // 如果不重载小于号要手写比较函数。

那么，枚举相邻的两个序列就行了。

这里给出证明：

假设最小产生在 b _ i 和 b _ {i + 2} 之间（不相邻）。那么应有：

即

这与 b _ {i + 1} < b _ {i + 2} 矛盾！

所以假设不成立。

那么我们如何得知区间是否包含 a _ i 呢？

这时候，我们在结构体里存的 l 和 r 就有用了。

不用去枚举 l 到 r，只需要判断 l \le i \le r 就行了。还是那句话：初始状态下没有两个连续子区间的和相等。

对于每一个 a _ i，扫描整个序列数组，如果一个序列和跟它相邻的序列一共只包含一个 a _ i，那么将它们的和相减，与答案取最小值。这一轮结束后输出答案。

至此，分析结束，时间复杂度 O(n ^ 3)，三次方是因为子序列个数有 \frac{n \dot (n + 1)}{2} 个，乘上枚举 a _ i 的 O(n)，算下来是 \Theta (\frac{n ^ 2 \dot (n + 1)}{2})，差不多 O (n ^ 3)。

注意事项

这里不用加绝对值，因为是从小到大排序。

完整代码（最下面就是思路）

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 500 + 5;

int a[N], s[N];

struct arr {
    int l, r, sum;

    bool operator < (const arr & x) const {
        return sum < x.sum;
    }
} b[N * N];

int n;

bool check(int l, int r, int x) {
    return l <= x && x <= r;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            b[++cnt] = {i, j, s[j] - s[i - 1]};
        }
    }
    sort(b + 1, b + cnt + 1);
    for (int i = 1; i <= n; i++) {
        int ans = 0x3f3f3f3f3f3f3f3f;
        for (int j = 1; j < cnt; j++) {
            if (check(b[j].l, b[j].r, i) && !check(b[j + 1].l, b[j + 1].r, i) || !check(b[j].l, b[j].r, i) && check(b[j + 1].l, b[j + 1].r, i)) {
                ans = min(ans, b[j + 1].sum - b[j].sum);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

/*
题目说要求改变 ai 的值，使得有两个不同的连续子序列相等。
那么，这两个子序列有什么特点？
题目说一开始没有两个不同子序列的和相等，说明 ai 的值对序列有影响。
所以两个序列中至少有一个包含 ai？
不对，应该是只有一个。因为两个序列同时加上相同的值，大小关系不变。
所以要求包含 ai 的序列 和 不包含 ai 的序列 的 最小差值。
先求出所有子序列的和：
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        for (int k = i; k <= j; k++) {
            sum[i][j] += a[k];
        }
    }
}
时间复杂度是 O(n ^ 3)，会不会炸？
显然不会。题目指出 1 <= N <= 500。
随后来比较。但是直接比较显然会超时。
那我们如何高效的找到不含 ai 和 含 ai 的序列呢？
把序列信息存入结构体中。
struct arr {
    int l, r, sum;
} b[N];
.....
int cnt = 0;
for (int i .....n; i++) 
    for (int j .....n; j++) {
        b[++cnt] = {i, j, sum[i][j]};
    }
}
哦，不用这么麻烦，可以先预处理前缀和。
for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + a[i];
}
for (i......) 
    for (j.......)
        b[++cnt] = {i, j, sum[i] - sum[j - 1]};
现在怎么做？
可以排个序，这样相邻的差值一定是最小的。
假设 ai 的存在情况如下：

0 1 0 0 1 1 0 0 
怎么找？
看起来只要找相邻的就可以了。
每次枚举相邻两个区间。看如果一边有 ai 一边没有 ai，就计算答案。
如何证明？
可以知道，排序后差值最小一定产生在相邻两个数。假设不产生在 b(i + 1)，产生在 b(i + 2)：
则我们可知
bi < b(i + 1) < b(i + 2);
b(i + 1) - bi < b(i + 2);
证毕。
但怎么判断有没有ai这个数呢？
原始思路：枚举 l ~ r 看有没有 ai。
但是题目说了没有相同的子序列，也就是数互不相同！！！
所以 一旦 l <= i <= r，就说明他在这个区间内！！！
所以判断相邻两段区间是否一个包含一个不包含，如果是则 ans = min(ans, b[i + 1].sum - b[i].sum)；
输出答案即可。
至此，思路完全打开。
*/

说在后面

若思路、代码讲解有误，欢迎提出！