P10830 题解

· · 题解

题目大意

给定 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，剩下的元素任意操作，不可操作时奇数偶数都至多一个。

综上此时我们一定能构造出解，实现时对 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;
}