题解：CF2252D Array Replacement

fish_love_cat · 2026-08-09 20:40:12 · 题解

典完了。这个形式一眼交换差分。

具体的，我们令 b_i=a_i-a_{i-1}。

操作前 b_i=a_i-a_{i-1},b_{i+1}=a_{i+1}-a_i，操作后 b_i=(a_{i-1}-a_i+a_{i+1})-a_{i-1},b_{i+1}=a_{i+1}-(a_{i-1}-a_i+a_{i+1})，化简得到 b_i=a_{i+1}-a_{i},b_{i+1}=a_{i}-a_{i-1}，容易发现差分数组发生了邻位交换。

操作的要求是 a_{i-1} 和 a_{i+1} 奇偶性相同，然后注意到这个要求下每个点的奇偶性都必然不会改变。

于是一个点能不能操作是固定的，对于不能操作的点，左右差分数组会断开不能任意交换。

最小化字典序，将每段差分数组升序排序，最后还原即可。

int a[200005];
int b[200005];
inline void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<n;i++)
    b[i]=a[i+1]-a[i];
    vector<int>flc;
    flc.push_back(b[1]);
    int lst=1;
    for(int i=2;i<n;i++){
        if((a[i-1]&1)^(a[i+1]&1)){
            sort(flc.begin(),flc.end());
            for(int j=0;j<flc.size();j++)
            b[lst+j]=flc[j];
            lst+=flc.size();
            flc.clear();
            flc.push_back(b[i]);
        }else flc.push_back(b[i]);
    }
    sort(flc.begin(),flc.end());
    for(int j=0;j<flc.size();j++)
    b[lst+j]=flc[j];
    lst+=flc.size();
    for(int i=2;i<=n;i++)
    a[i]=a[i-1]+b[i-1];
    for(int i=1;i<=n;i++)
    cout<<a[i]<<' ';
    cout<<'\n';
}
// 馬鹿にされて指をさされても
// 中身の無いくだらない事をふたりで
// 一生分の思い出として
// 馬鹿みたいに抱え続けてさ
// 希望ひとつない世界を表裏一体で
// 駆け抜ける"ふり"をしましょうか