P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方 题解

· · 题解

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;
}