题解：CF2252D Array Replacement

Galx_Trail · 2026-08-07 08:49:32 · 题解

D

神秘观察题，观察到题中更改操作是将相邻两个同奇偶的差分值相交换（可以自己手推一下）。

所以我们可以贪心将所有同奇偶的差分块处理出来，内部排序，再还原a即可。

#include<bits/sdtc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
    using ll = long long;
    using ull = unsigned long long;
    using i128 = __int128;
    using lb = long double;
    void Main() {
        int n; cin>>n;
        vec<ll> a(n+1,0),diff(n+1,0);
        for (int i=1;i<=n;++i) cin>>a[i];
        for (int i=1;i<=n;++i){
            diff[i]=a[i]-a[i-1];
        }
//      cout<<"diff:"<<endl;
//      for (int i=1;i<=n;++i) cout<<diff[i]<<' ';
//      cout<<endl;
//      cout<<"----------"<<endl;
        for (int i=2;i<=n;){
            int j=i;
            while(j+1<=n&&abs(diff[j+1]-diff[i])%2==0){
                ++j;
            }
//          cout<<i<<' '<<j<<endl;
            sort(diff.begin()+i,diff.begin()+j+1);
//          for (int k=i;k<=j;++k) cout<<diff[k]<<' ';
//          cout<<endl;
//          cout<<"---------------"<<endl;
            i=j+1;
        }
        a[1]=diff[1];
        cout<<a[1]<<' ';
        for (int i=2;i<=n;++i){
            a[i]=a[i-1]+diff[i];
            cout<<a[i]<<(i==n?endl:" ");
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Test = 1;
    cin >> Test;
    while (Test--) CZW::Main();
    return 0;
}