题解：P14757 武汉之泪

Norfor · 2025-12-16 20:51:30 · 题解

题目大意

给你两个长度为 n 的序列 a 和 b，可以对序列 a 执行以下操作：

• 选择一个位置 i 满足 a_i+1=a_{i+1}。
• 将 a_i 和 a_{i+1} 同时加一或减一。
• 要求序列时刻保持单调递增。

问能否通过若干次操作将序列 a 变为 b。

解题思路

• 首先容易观察到序列的变化是可逆的，即若序列 c 能变为序列 d，那么也一定能由序列 d 变为序列 c。虽然这题想直接将 a 通过操作变为 b 比较困难，但根据该性质我们可以考虑将它们都化为最小形态比较是否相同。
• 对于一个已化为最小形态的序列，它的前缀一定是一个从 1 开始的连续串，剩余的后缀一定是不连续的数。
• 因为序列要求单调递增，因此我们考虑从前往后扫：
  1. 若第 i 位可操作且当前无不连续数时，则连续前缀长度加 2。
  2. 若第 i 位可操作且当前有不连续数时，a_i 会一直减至 a_{i-1}+1 然后转为操作第 i-1 位，第 a_{i+1} 位变为不连续数，效果上相当于连续前缀长度加 2，当前所有不连续数数值加 2。

实现方法

• 在扫的过程中我们可以用 lena 和 lenb 维护不连续数的数量，并开一个数组 val 来存不连续点被扫到时的值和一个差分数组 delt 来维护不连续的点的变化量，序列 a 对其做正贡献，序列 b 对其做负贡献。
• 然后比较 lena 是否等于 lenb，不相等则不可能满足题目要求。
• 最后将差分数组 delt 的效果加在 val 上，看 val 是否都为 0 即可，为 0 则可以实现题目要求，否则不能。

时间复杂度为 O(n)。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
long long int a[200005],b[200005];
long long int val[200005],delt[200005];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        val[i]=0;
        delt[i]=0;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    int la=1,lena=0;
    while(la<=n){
        if(la!=n&&a[la+1]-a[la]==1){
            la++;
            delt[1]+=2;
            delt[lena+1]-=2;
        }
        else{
            lena++;
            val[lena]=a[la];
        }
        la++;
    }
    int lb=1,lenb=0;
    while(lb<=n){
        if(lb!=n&&b[lb+1]-b[lb]==1){
            lb++;
            delt[1]-=2;
            delt[lenb+1]+=2;
        }
        else{
            lenb++;
            val[lenb]-=b[lb];
        }
        lb++;
    }
    long long int cur=0;
    if(lena!=lenb){
        cout<<"NO"<<"\n";
        return ;
    }
    for(int i=1;i<=n;i++){
        cur+=delt[i];
        val[i]+=cur;
        if(val[i]!=0){
            cout<<"NO"<<"\n";
            return ;
        }
    }
    cout<<"YES"<<"\n";
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}