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

· · 题解

题外话

这题看起来很像贪心啊，但由于本人贪心太废了，所以只好使用二分加动态规划来做了。

思路

先把相同的数缩成一个数，将原本长度为 n 的 a 数组变为长度为 m 的互不相同的 a 数组，用 b_i 记录 i 的出现次数。观察到答案具有单调性，考虑二分答案 x。问题关键在于如何判断划分出的集合数量能不能为 x。我们枚举每一个 a_i，用 dp_{i,j} 表示前 i 个数，能不能划分出 j 个大小为奇数的集合，若能 dp_{i,j} 为 1，否则为 0。则最后 dp_{m,0} 就是答案。

考虑转移，对于 dp_{i,j}，我们枚举 k 表示使用了 k 个 a_i 放入了之前的 k 个大小为奇数的集合，剩余的 (b_{a_i}-k) 个 a_i 放入了之前的 (b_{a_i}-k) 个大小为偶数的集合，其余集合的奇偶性不变。既然放一个数字集合奇偶性会取反，那么 dp_{i,j} 就是可以从 dp_{i-1,j+2\times k-b_{a{i}}} 转移过来的，取最大值即可。

求出最小值后我们还要构造一种方案，此时只需要用 f_{i,j} 记录 dp_{i,j} 是从哪里转移过来的即可。

由于循环前两维总和为 n，总时间复杂度 O(n^2\log n)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,a[1005],b[1000005],c[1005],dp[1005][1005],f[1005][1005];
vector<int> v[1005];
bool check(int x) {
    memset(dp,0,sizeof(dp));
    dp[1][b[a[1]]]=1;
    for(int i=2; i<=m; i++) {
        if(b[a[i]]>x)return 0;
        for(int j=0; j<=x; j++) {
            for(int k=0; k<=b[a[i]]; k++) {
                if(j+k-b[a[i]]>=0&&x-j-k>=0)dp[i][j]=max(dp[i][j],dp[i-1][j+2*k-b[a[i]]]);
            }
        }
    }
    return dp[m][0];
}
bool cmp(vector<int> x,vector<int> y){
    return x.size()%2>y.size()%2;
}
void gx(int x) {
    memset(dp,0,sizeof(dp));
    dp[1][b[a[1]]]=1;
    f[1][b[a[1]]]=0;
    for(int i=2; i<=m; i++) {
        for(int j=0; j<=x; j++) {
            for(int k=0; k<=b[a[i]]; k++) {
                if(j+k-b[a[i]]>=0&&x-j-k>=0) {
                    if(dp[i-1][j+2*k-b[a[i]]]) {
                        dp[i][j]=1;
                        f[i][j]=k;
                        break;
                    }
                }
            }
        }
    }
    int j=0;
    for(int i=m; i>=1; i--) {
        c[i]=f[i][j];
        j+=2*f[i][j]-b[a[i]];
    }
    for(int i=1; i<=m; i++) {
        int y=1;
        for(int j=1; j<=b[a[i]]; j++) {
            if(v[y].size()%2==1) {
                if(c[i]) {
                    c[i]--;
                    v[y].push_back(a[i]),y++;
                }
                else{
                    while(v[y].size()%2==1)y++;
                    v[y].push_back(a[i]),y++;
                }
            } else v[y].push_back(a[i]),y++;
        }
        sort(v+1,v+x+1,cmp);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        for(int i=1; i<=n; i++)cin>>a[i];
        if(n%2==1) {
            cout<<-1<<"\n";
            continue;
        }
        for(int i=1; i<=n; i++)b[a[i]]++;
        sort(a+1,a+n+1);
        m=unique(a+1,a+n+1)-a-1;
        int l=1,r=n/2,mid,ans=-1;
        while(l<=r) {
            mid=(l+r)/2;
            if(check(mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        cout<<ans<<"\n";
        if(ans!=-1) {
            gx(ans);
            for(int i=1; i<=ans; i++) {
                cout<<v[i].size()<<" ";
                for(int j=0;j<v[i].size();j++){
                    cout<<v[i][j]<<" ";
                }
                v[i].clear();
                cout<<"\n";
            }
        }
        for(int i=1; i<=m; i++)b[a[i]]=0;
    }
    return 0;
}

后记

贪心我们分手吧，我怕动态规划误会。