自动搬运

查看原文

来自洛谷，原作者为

	ny_Dacong 你所热爱的，是你配热爱的吗？

搬运于2025-08-24 23:09:05，当前版本为作者最后更新于2025-01-31 22:00:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd on 2025.2.5：优化了语言。

思路

先给出这道题的万能策略：

每次操作的选段长度固定为 $2$。这样一次操作转化为让 $a_l,a_{l+1}(l+1 = r)$ 同时加上（或减去）$1$。

这样一来，依次遍历 $1 \sim n-1$，对 $a_i,a_{i+1}$ 进行 $|b_i-a_i|$ 次操作。如果大了就减，否则加。

注意由于操作后 $a_{i+1}$ 的值也会变，所以一会修改 $a_{i+1}$ 时要按照本次操作后的值计算。

如果最后，$a_n = b_n$，则有解（这就是一个解），否则一定无解。

以样例 1 为例，其变化过程为：

2 4 4 3 3
2 2 2 3 3
2 2 3 4 3
2 2 3 2 1

证明为什么本策略无法得出解，就一定无解。

假如本策略无解，然而有其它的方法使得有解，那么这个有解的方法一定使用了长度大于 $2$ 的操作。只要我们证明，一次长度大于 $2$ 的操作可以用万能策略替代，那么这个假设就可以证伪。

证明：

首先，对于长度任意的一次操作 $[l,r]$，令 $k_i = \left(|i-\frac{r+l}{2}|+\frac{1}{2}\right)$。例如，如果 $l=1$，$r=8$，$k_1 \sim k_8 = (4,3,2,1,1,2,3,4)$。

然后令 $d_i$ 表示，如果用开头的万能策略替代本次操作，需要进行 $d_i$ 次范围为 $[i,i+1]$ 的加法操作。特别的，如果 $d_i < 0$，表示需要执行 $-d_i$ 次减法操作。

可以得出 $d_l = k_l$。

然后可以发现 $d_{l+1} = k_{l+1}-d_l$。也就是说，$l+1$ 这一位已经加上 $d_l$ 了，还需要加上 $k_{l+1}-d_l$ 就可以等于 $k_{l+1}$ 了。

进而可以发现，$d_i = k_i-d_{i-1}(l < i < r)$。

那么如果 $d_r = 0$，也就是说前面的操作足以让 $r$ 这一位完成修改了，这一位不用再操作了，那么就说明万能策略可以替代。

对 $d_r$ 进行展开：

$$\begin{aligned} d_r & = k_r-d_{r-1} \\ & = k_r-k_{r-1}+d_{r-2} \\ & = k_r-k_{r-1}+k_{r-2}-d_{r-3} \\ & \dots \\ & = k_r-k_{r-1}+k_{r-2}-k_{r-3}+ \dots +k_{l+1}-d_{l} \\ & = k_r-k_{r-1}+k_{r-2}-k_{r-3}+ \dots +k_{l+1}-k_{l} \\ & = k_r+k_{r-2}+k_{r-4}+k_{r-6}+ \dots - (k_{r-1}+k_{r-3}+k_{r-5}+k_{r-7}+\dots) \\ & = 0 \end{aligned} $$

发现 $k$ 的奇数项之和一定等于偶数项之和（因为是对称的），所以最后 $d_r$ 一定为 $0$。

证毕。

AC 代码

#include<bits/stdc++.h>
using namespace std;
long long t;
long long n;
long long a[100050],b[100050];
int main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		memset(a,0,sizeof(long long)*(n+10));
		memset(b,0,sizeof(long long)*(n+10));
		for(long long i = 1; i <= n; i++){
			scanf("%lld",&a[i]);
		}
		for(long long i = 1; i <= n; i++){
			scanf("%lld",&b[i]);
		}
		if(n == 1){
			puts("No");
			continue;
		}
		for(long long i = 1; i < n; i++){
			static long long tp;
			tp = b[i]-a[i];
			a[i] += tp;
			a[i+1] += tp;
		}
		if(a[n] == b[n]){
			puts("Yes");
		}else{
			puts("No");
		}
	}
	return 0;
}