CF2124E 题解

__vector__ · 2025-07-10 12:40:53 · 题解

被这题消耗了 5h 时间，记录一下。

首先，令 pre_i 表示 \sum\limits_{j=1}^ia_j，suf_i 表示 \sum\limits_{j=i}^na_j，sum 表示 \sum\limits_{i=1}^na_i。

首先，考虑无解条件怎么判定。

1. 注意到，每次操作减去的总和必然是偶数。

   所以，总和必须是偶数。

2. 最大值不能超过总和的一半。

   这是因为，一个数减去 1，必然至少有一个其他的数也得同时减去 1。

以上两种必然无解，其他情况还不知道。

先把无解情况判掉，再考虑剩余情况怎么处理。

注意到，所有 n \gt 3 的情况都可以转化为 n=3 的情况，且不会转为上述无解情况，可以这样：

1. 从前到后扫描，找到最大的 x，满足 pre_x \le suf_{x+1}：

   此时，可以得到性质 pre_x \le \frac{sum}{2}，suf_{x+2} \le \frac{sum}{2}。

   另外，x \lt n-1，否则就是无解情况（之前已经判掉了）。

2. 划分为 3 段，[1,x],[x+1,x+1],[x+2,n]：

   这 3 段的总和分别相当于新的 a_1,a_2,a_3，操作时将它们分别视为一个整体操作就可以了。

接下来，只需要分类讨论 n=2,3 的情况了。

• 注意到，此时必然满足 $a_1=a_2$，操作一次 $b_1=b_2=a_1$ 就可以了。
• 如果想要一次操作结束，只能是以下两种情况： 1. $a_1+a_2 = a_3$。 2. $a_1=a_2+a_3$。 现在，考虑其他的情况怎么操作。 - 转化为 $n=2$，且两个数字相等的情况： - 变为 $a_1=a_2$ 的情况： 前提条件是 $a_2 - a_1 \le a_3$ 且 $a_2-a_1 \equiv a_3\pmod 2$。 不过，最容易想到的一种条件是 $a_2 - a_3 = a_1$。 - 变为 $a_2=a_3$ 的情况： 前提条件是 $a_2 - a_3 \le a_1$ 且 $a_2 - a_3 \equiv a_1 \pmod 2$。 最容易想到的条件仍然是 $a_2-a_3=a_1$。 - 变为 $a_1=a_3$ 的情况： - 若 $a_1 \lt a_3$： 那么，操作 $b_2=a_2,b_3=a_3-a_1$。 也就是说，本种情况，能进行转化操作的前提是 $a_3-a_1 = a_2$。 但是，这种情况的答案就是 $1$，使用本转化就得 $2$ 次了，不优。 故，不考虑本情况。 - 若 $a_1 \ge a_3$： 那么，操作 $b_2 = a_2,b_1 = a_1 - a_3$。 本种情况，转化前提是 $a_1-a_3 = a_2$。 同样，本种情况答案是 $1$，使用本转化就得 $2$ 次了，不优。 故，同样不考虑本情况。 可以看出来，如果转为 $n=2$ 的情况，那么全局一定需要 $2$ 次操作。 - 变为 $a_1+a_3 = a_2$ 的情况： 此时，尝试求出一个 $d$，使得 $(a_1-d)+(a_3-d)=a_2$。 推导可得，$d = \frac{a_1+a_3-a_2}{2}$。 那么如何证明 $d$ 合法？ > $a_1+a_3-a_2 = a_1+a_2+a_3-2a_2$。 > > 由于 $a_1+a_2+a_3$ 为偶数，$a_1+a_3-a_2$ 也是偶数。 > > 所以 $d$ 是整数。 > > 然后需要证明 $d \le \min(a_1,a_3)$。 > > $a_1 \ge \frac{a_1+a_3-a_2}{2}$ 可以转化为 $2a_1 \ge a_1 + a_3-a_2$，即 $a_1 \ge a_3-a_2$。 > > 如果上述条件不满足，即 $a_1 \lt a_3-a_2$，这就属于无解情况，已经判掉了，不存在。 > > 同样方法也可以证明 $a_3 \ge \frac{a_1+a_3-a_2}{2}$。 由此可以构造出 $b_1=b_3=\frac{a_1+a_3-a_2}{2},b_2=0$。 如果推导到这一步就结束了，那么全局需要 $3$ 次操作。 但实际上，本情况只需要两次操作。 - 考虑一下 $a_1+a_3=a_2$ 的情况。 下一步转化为 $a_1=a_2$ 的情况，这就需要构造： $b_1=0,b_2=a_3,b_3=a_3

  注意到，本次转化操作，和下一次转化操作其实可以合并为一次进行操作。

  新的构造：

  这样，一次操作直接转化为了 a_1=a_2 的情况，也就是最终全局 2 次操作。

上述构造，说明了任意非无解情况都只需要最多两次操作。

这是一个比较丑陋的实现：

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
#define NO {puts("-1");return;}
const int maxn=2e5+5;
int n;
ll a[maxn],tot[4];
ll pre[maxn];
ll w(int l,int r){
    return pre[r]-pre[l-1];
}
int lef[4],rig[4];// 记录 a[1],a[2],a[3] 对应原数组实际范围
void op(ll* b,int len){
    FOR(id,1,len){// 目前减去 len 个中的第 id 个
        FOR(i,lef[id],rig[id]){
            ll _=min(a[i],b[id]);
            a[i]-=_;
            b[id]-=_;
            printf("%lld ",_);
        }
    }
    pln
}
void solve(int id_of_test){
    cin>>n;
    FOR(i,1,n){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    ll sum=pre[n];
    if(sum%2)NO
    if((*max_element(a+1,a+n+1))>sum/2)NO
    if(n>=4){
        FOR(i,1,n){
            if(w(1,i)>w(i+1,n)){
                lef[1]=1,rig[1]=i-1;
                lef[2]=i,rig[2]=i;
                lef[3]=i+1,rig[3]=n;
                tot[1]=w(1,i-1);
                tot[2]=w(i,i);
                tot[3]=w(i+1,n);
                break;
            }
        }
    }else{
        FOR(i,1,n)lef[i]=rig[i]=i,tot[i]=a[i];
    }
    if(n==2){
        puts("1");
        ll b[3]={-1,a[1],a[2]};
        op(b,2);
    }else{
        if(tot[1]+tot[2]==tot[3]||tot[1]==tot[2]+tot[3]){
            puts("1");
            ll b[4]={-1,tot[1],tot[2],tot[3]};
            op(b,3);
        }else{
            puts("2");
            ll b[4]={-1,(tot[1]+tot[3]-tot[2])/2,tot[3]-(tot[1]+tot[3]-tot[2])/2,tot[3]};
            op(b,3);
            b[1]=tot[1];
            b[2]=tot[2];
            b[3]=0;
            op(b,3);
        }
    }
}
int main()
{
    int T;
    cin>>T;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}
/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*/