题解：P13494 【MX-X14-T4】分门别类

· · 题解

不太明白 O(n\log n) 为啥开 1000。

这是个序列构造问题，显然这些时候无解：

容易证明剩下的情况有解。

一个答案下界是绝对众数个数，但是不对，比如：

8
1 1 1 2 2 2 3 3

这个的答案做不到 3，是 4。考虑对着数据构造方案：

先把数据按照个数按列划分，就像这样：

1 2 3 
1 2 3
1 2

我们注意到可以在奇数的行上分别提取一个 2 和 3 新开一行即可。

这种操作会新开序列。为了尽可能减少上面的操作，我们如果碰见奇数的序列对了我们可以小序列去 "偷" 大序列尾数，就像这样：

3 2 1 5 4 
3 2 1   |
3   <---/

考虑列出所有的长度是奇数的序列，容易发现我们可以进行类似于匹配的操作。具体的，除了两个相同的序列以外都可以进行匹配。这个操作很像证明有解性。

不过这种东西即使是存在绝对众数也是有解的。我们不做这种操作，而是进行大小匹配。最后会如果剩下东西，会剩下一些长度相等的奇数序列（如果不是，已经构造出答案且达到答案下界，直接输出就行。），这些序列的个数一定是偶数。

考虑现在的序列样子：设中间还是奇数的序列，则上面的序列只是被移除了数。且这些两两的 LCP 是较短序列本身。也就是说，后面多出来的数一定可以无损的插入到目前是奇数的序列里。拿出多出的数（一定是偶数），尽可能消去目前的奇数序列。

1 2 3 4 5 6
1 2 3 <-+-/
1 2 3 <-/

如图所示。

现在还是可能剩下一些序列，考虑下面的序列：来自的数一定是上面的数或者奇数序列的最后一个数（因为可能是等长序列先偷的）。注意到剩下的奇数序列都是完全相同的。考虑记录序列的原来长度，检查最后一个数，记录可以插入的区间。然后按照顺序顺次从奇数序列中拿出数即可。

1 2 3 (4) 5
1 2 (3) 4 5
1 5 [3 4]

如图所示。

如果还有序列？那没办法了，新开空序列就行。然后当成原来的长度为 0 的序列进行操作。

以上的操作过程中如果发现不存在奇数序列了，直接停止就行。

时间复杂度 O(\sum n\log n)，瓶颈在排序和 map。不知道为啥开 1000。

#include<bits/stdc++.h>
using namespace std;
vector<int>res[1003];
int siz[1003];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        map<int,int>s;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            s[x]++;
        }
        if(n&1){
            cout<<"-1\n";
            continue;
        }
        priority_queue<pair<int,int>>fc;
        for(auto f:s){
            fc.push({f.second,f.first});
        }
        if(fc.top().first>n/2){
            cout<<"-1\n";
            continue;
        }
        int m=fc.top().first;
        for(int i=1;i<=n+1;i++)res[i].clear(),siz[i]=0;
        while(fc.size()){
            auto p=fc.top();fc.pop();
            for(int i=1;i<=p.first;i++){
                res[i].push_back(p.second);
                siz[i]++;
            }
        }
        int d=m,u=1;
        while(1){
            while(d>=u&&res[d].size()%2==0){
                d--;
            }
            while(d>=u&&res[u].size()%2==0){
                u++;
            }
            if(d<=u)break;
            if(res[d].size()!=res[u].size()){
                res[d].push_back(res[u].back());
                res[u].pop_back();
            }else{
                for(int i=u-1;i>=1;i--){
                    while(d>=u&&res[i].size()>res[u].size()+1){
                        res[u].push_back(res[i].back());res[i].pop_back();
                        u++;
                    }
                    if(d<u)break;
                }
                if(d<u)break;
                for(int i=d+1;;i++){
                    if(i>m){
                        m++;
                        res[m].clear();
                    }
                    int h=siz[u]-siz[i];
                    if(res[i].size()&&res[i].back()==res[u].back())h--;
                    if(h%2)h--;
                    int pos=siz[u]-1;
                    if(res[i].size()&&res[i].back()==res[u].back())pos--;
                    while(d>=u&&h){
                        swap(res[u][pos],res[u].back());
                        res[i].push_back(res[u].back());res[u].pop_back();
                        pos--;u++;h--;
                    }
                    if(d<u)break;
                }
                assert(d<u);
            }
        }
        cout<<m<<'\n';
        for(int i=1;i<=m;i++){
            cout<<res[i].size()<<' ';
            for(auto j:res[i]){
                cout<<j<<' ';
            }
            cout<<'\n';
        }
    }
    return 0;
}