题解：P15267 「UTOI 1B」Chaotic Time Trio

He_XY · 2026-02-11 18:07:05 · 题解

这里是官方题解。

闲话

我是良心出题人，本来是要 n\ge 3 的，也就是只有两个无解情况。但由于 UKBwyx 的要求，改成了 n\ge 1，这增加了很多corner case。最后还改成了多测 + 捆绑。

思路

观察 \operatorname{mex} 运算的性质，发现：

• 任何数与 0 的 \operatorname{mex} 都不为 0；
• 任意两个非零数 \operatorname{mex} 都为 0。

首先先考虑 corner case：

接下来考虑既有 0，又有非零数的情况（称为一般情况）：

• 可以想到，要想最后 S=\{0\}，必须满足：在最后一步之前，S 包含两个非零数。也就是说，我们需要两个非零数，还要消除集合中所有的零和多余的非零数。

• 考虑如何构造这样的非零数：可以先单独拎出一个非零数，留住它。

  在剩下的数中，无论你中途怎么选择，只要保证最后一次是一个数和 0 取 \operatorname{mex}，就可以使它剩下一个非零数。

• 两个非零数取 \operatorname{mex}，可以得到全 0。

再去考虑特殊情况：

1. 全 0：

   可以先取两个 0 进行一次操作，弄出一个非零数，然后归约到上述一般情况。

2. 全非零：

   可以先取两个非零数弄出一个 0，然后归约到上述一般情况。

std

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
int mex(int a,int b){
    if(a>b) swap(a,b);
    if(a!=0) return 0;
    else if(b!=1) return 1;
    else return 2;
}
void solve(){
    int n; cin>>n;
    multiset<int> st; //使用multiset从后往前取可以保证最后一次取0
    bool allzero=1,allnotzero=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st.insert(a[i]);
        allzero&=(a[i]==0);
        allnotzero&=(a[i]!=0);
    }

    //corner case 特判
    if(n==1){
        cout<<(allzero?"":"-1")<<"\n";
        return;
    }else if(n==2){
        if(allnotzero) cout<<a[1]<<" "<<a[2]<<endl;
        else cout<<"-1\n";
        return;
    }else if(n==3){
        if(allzero) return void(cout<<-1<<endl);
        else if(allnotzero) return void(cout<<-1<<endl);
    }

    if(allzero){//全零
        cout<<"0 0\n";
        int cur=0;
        for(int i=1;i<=n-3;i++){
            cout<<cur<<" 0\n";
            cur=mex(0,cur);
        }
        cout<<cur<<" "<<1<<endl;
        return;
    }else if(allnotzero){//全非零
        int a=*st.begin(); st.erase(st.find(a));
        int b=*st.begin(); st.erase(st.find(b));
        cout<<a<<" "<<b<<"\n";
        st.insert(0);
        int left=*st.rbegin(); st.erase(st.find(left));
        while(st.size()>1){
            int p=*st.rbegin(); st.erase(st.find(p));
            int q=*st.rbegin(); st.erase(st.find(q));
            cout<<p<<" "<<q<<endl;
            st.insert(mex(p,q));
        }
        cout<<left<<" "<<*st.begin()<<endl;
        return;
    }

    //一般情况
    int left=*st.rbegin(); st.erase(st.find(left));
    while(st.size()>1){
        int p=*st.rbegin(); st.erase(st.find(p));
        int q=*st.rbegin(); st.erase(st.find(q));
        cout<<p<<" "<<q<<endl;
        st.insert(mex(p,q));
    }
    cout<<left<<" "<<*st.begin()<<endl;
}
main(){
    int T; cin>>T;
    while(T--) solve();
    return 0;
}