本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$ 的情况了。

• $n=2$ 的情况：

  注意到，此时必然满足 $a_1=a_2$，操作一次 $b_1=b_2=a_1$ 就可以了。

• $n=3$ 的情况：

  如果想要一次操作结束，只能是以下两种情况：

  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$

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

    新的构造：

    1. $b_1=\frac{a_1+a_3-a_2}{2}$。
    2. $b_2= 0 + (a_3-\frac{a_1+a_3-a_2}{2})$，括号里的数字代表 $a_3$ 第一次操作后的新值。
    3. $b_3 = \frac{a_1+a_3-a_2}{2} + (a_3-\frac{a_1+a_3-a_2}{2})=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？
*\/