自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:01:39，当前版本为作者最后更新于2024-08-06 17:39:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定 $a_1\sim a_n$，每次操作选择 $a_x,a_y$ 使得他们的和为偶数，删除 $a_x,a_y$ 并加入 $\dfrac{a_x+a_y}2$。

构造一种方案使得最终仅剩一个数，或报告无解。

数据范围：$n\le 10^6$。

思路分析

按 $a_i \bmod 4$ 分成四个集合 $S_0\sim S_3$。

先考虑全是偶数的情况，每次操作取出两个 $\bmod 4$ 同余数操作，一定得到偶数。

不断操作，停止时一定合法，或是 $|S_0|=|S_2|=1$，操作两个偶数即可。

全是奇数的情况也类似。

然后考虑一般的情况。

我们观察到：如果 $S_0,S_2$ 均非空，或 $S_1,S_3$ 均非空，一定有解。

设 $S_0,S_2$ 非空，各取出一个元素 $x_0,x_2$，剩下的元素任意操作，不可操作时奇数偶数都至多一个。

• 如果仅剩一个奇数 $y$，操作 $x_0,x_2$ 再和 $y$ 操作。

• 如果仅剩一个偶数 $y$，操作与 $y$ 模 $4$ 同余的 $x$ 得到一个偶数，再和另一个 $x$ 操作。

• 否则设剩一奇一偶，设他们 $\bmod 4$ 余 $0,1$，不妨当前的四个数是 $4a,4b,4c+1,4d+2$：

  如果 $a+d$ 为奇数：那么操作 $4a,4d+2$ 再与 $4c+1$ 操作得到：$a+d+2c+1$ 为偶数，和 $4b$ 操作即可。

  如果 $b+d$ 为奇数同样可构造，否则一定有 $a\equiv b\pmod 4$，此时操作 $4a,4b$ 再和 $4d+2$ 操作得到 $a+b+2d+1$ 为奇数再和 $4c+1$ 操作即可。

综上此时我们一定能构造出解，实现时对 $n\le 4$ 的情况爆搜即可。

否则我们要尝试构造 $x_0,x_2$。

不妨假设存在若干偶数，我们找到最小的 $d$ 使得这些偶数第 $d$ 位不全相同。

取出两个第 $d$ 位不同的数 $x,y$，可以写成 $x=2^{d+1}a+2^d+r,y=2^{d+1}b+r$，操作这两个数得到 $2^d(a+b)+(2^{d-1}+r)$。

容易发现这个数的第 ${d-1}$ 位和其他数的第 $d-1$ 位不同，重复构造到 $d=2$ 为止即可，记得判断偶数数量是否足够。

可以证明以上条件是充分的。

时间复杂度 $\mathcal O(n\log V)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
#define sz(a) (int(a.size()))
using namespace std;
const int inf=1e9;
vector <array<ll,2>> wys;
vector <ll> a[4];
void opr(int x,int y) {
	ll u=a[x].back(); a[x].pop_back();
	ll v=a[y].back(); a[y].pop_back();
	ll w=(u+v)>>1;
	wys.push_back({u,v}),a[w&3].push_back(w);
}
void sol() {
	vector <ll> rem;
	if(sz(a[0])&&sz(a[2])) rem={a[0].back(),a[2].back()},a[0].pop_back(),a[2].pop_back();
	else rem={a[1].back(),a[3].back()},a[1].pop_back(),a[3].pop_back();
	while(true) {
		if(sz(a[0])+sz(a[2])>1) {
			if(sz(a[0])&&sz(a[2])) opr(0,2);
			else sz(a[0])?opr(0,0):opr(2,2);
		} else if(sz(a[1])+sz(a[3])>1) {
			if(sz(a[1])&&sz(a[3])) opr(1,3);
			else sz(a[1])?opr(1,1):opr(3,3);
		} else break;
	}
	for(int o:{0,1,2,3}) for(ll x:a[o]) rem.push_back(x);
	vector <array<ll,2>> cur;
	function<bool(vector<ll>)> dfs=[&](vector<ll> q) {
		if(sz(q)==1) {
			for(auto z:wys) cout<<z[0]<<" "<<z[1]<<"\n";
			for(auto z:cur) cout<<z[0]<<" "<<z[1]<<"\n";
			return true;
		}
		for(int i=0;i<sz(q);++i) for(int j=i+1;j<sz(q);++j) if((q[i]+q[j])%2==0){
			cur.push_back({q[i],q[j]});
			vector <ll> p{(q[i]+q[j])/2};
			for(int k=0;k<sz(q);++k) if(k!=i&&k!=j) p.push_back(q[k]);
			if(dfs(p)) return true;
			else cur.pop_back();
		}
		return false;
	};
	dfs(rem);
}
int cnt(int o) {
	for(int i=0;i<60;++i) for(int j=1;j<sz(a[o]);++j) {
		if((a[o][0]^a[o][j])>>i&1) return i;
	}
	return inf;
}
void go(int o) {
	for(int i=cnt(o);i>1;--i) {
		int j=1;
		for(;!((a[o][0]^a[o][j])>>i&1);++j);
		ll x=a[o][0],y=a[o][j];
		vector <ll> q;
		for(int k=1;k<sz(a[o]);++k) if(k^j) q.push_back(a[o][k]);
		q.push_back(x),q.push_back(y);
		a[o].swap(q),opr(o,o);
	}
}
void solve() {
	wys.clear();
	for(int o:{0,1,2,3}) a[o].clear();
	int n; cin>>n;
	for(ll x;n--;) cin>>x,a[x&3].push_back(x);
	if(!sz(a[0])&&!sz(a[2])) {
		while(sz(a[1])>1||sz(a[3])>1) sz(a[1])>1?opr(1,1):opr(3,3);
		if(sz(a[1])&&sz(a[3])) opr(1,3);
		for(auto z:wys) cout<<z[0]<<" "<<z[1]<<"\n";
		return ;
	}
	if(!sz(a[1])&&!sz(a[3])) {
		while(sz(a[0])>1||sz(a[2])>1) sz(a[0])>1?opr(0,0):opr(2,2);
		if(sz(a[0])&&sz(a[2])) opr(0,2);
		for(auto z:wys) cout<<z[0]<<" "<<z[1]<<"\n";
		return ;
	}
	if((sz(a[0])&&sz(a[2]))||(sz(a[1])&&sz(a[3]))) return sol();
	for(int o:{0,1,2,3}) if(sz(a[o])>1&&cnt(o)<sz(a[o])) return go(o),sol();
	cout<<"-1\n";
}
signed main() {
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	ios::sync_with_stdio(false);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}