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

X_X_M · 2025-01-31 23:24:31 · 题解

这是一道侧重于结论的题目。

思路：

题目给出的操作看似复杂，但实际上所有对段的操作满足左右两边的对称性，于是猜想一个涉及到4个元素及以上较为复杂的操作可以被分解为若干对两个元素的简单操作。

以对某段加上 3,2,1,1,2,3 为例，我们将其改写为：

同理，能被变换为目标序列的序列一定可以用若干二元操作变为目标序列。

现在希望确定这些二元变换从而验证或推出矛盾。有鉴于题设操作无关操作先后顺序，我们按照从左至右的顺序，先确定较易确定的对区间端点的变换，再依次确定所有变换。核心部分如下：

for(int i=0;i<n-1;i++){
    int d=b[i]-a[i];
    a[i]+=d;
    a[i+1]+=d;
}

最后检查序列右端点是否与目标序列一致即可。

Code：

#include <bits/stdc++.h>
using namespace std;

#define MXN 100010
#define int long long

int n;
int a[MXN],b[MXN];

signed main(){
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        int s=0;
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
        for(int i=0;i<n;i++){
            cin >> b[i];
        }
        for(int i=0;i<n-1;i++){
            int d=b[i]-a[i];
            a[i]+=d;
            a[i+1]+=d;
        }
        if(b[n-1]==a[n-1]){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}