3868. [USACO23 Feb Gold] Equal Sum Subarrays

【题目描述】

给定一个长度为 $N$ 的整数数组 $a_1,a_2,…,a_N$。

数组 $a$ 有 $\frac{N(N+1)}{2}$ 个子区间，它们的内部元素和各不相同。

对于每个 $i∈[1,N]$，请你找到一个最小正整数 $x$，使得 $a_i$ 加上或减去 $x$ 后（加、减满足其一即可），数组 $a$ 存在至少一对不同子区间的内部元素和相同。

【输入格式】

第一行包含整数 $N$。

第二行包含 $N$ 个整数 $a_1,a_2,…,a_N$。

【输出格式】

共 $N$ 行，其中第 $i$ 行输出最小正整数 $x$，使得 $a_i$ 加上或减去 $x$ 后（加、减满足其一即可），数组 $a$ 存在至少一对不同子区间的内部元素和相同。

【样例1输入】

2
2 -3

【样例1输出】

2
3

【样例1解释】

$i=1$ 时，通过让 $a_1$ 减去 $2$，可以使得 $a_1+a_2=a_2$。

$i=2$ 时，通过让 $a_2$ 加上 $3$，可以使得 $a_1+a_2=a_1$。

【样例2输入】

3
3 -10 4

【样例2输出】

1
6
1

【样例2解释】

$i=1$ 时，通过让 $a_1$ 加上 $1$，可以使得 $a_1=a_3$。

$i=2$ 时，通过让 $a_2$ 加上 $6$，可以使得 $a_1=a_1+a_2+a_3$。

$i=3$ 时，通过让 $a_3$ 减去 $1$，可以使得 $a_1=a_3$。

【样例3】

点击下载样例3 

【数据规模与约定】

测试点 $1$: $N \le 40$

测试点 $2$: $N \le 80$

测试点 $3-5$: $N \le 200$

对于 $100\%$ 的数据，$2≤N≤500,−10^{15}≤a_i≤10^{15}$。