P13341 题解

lmh_qwq · 2025-10-27 21:06:43 · 题解

建议降蓝。

考虑如下构造：任取 12 的约数 k，以及 d\ge \frac{12}{k}。找出 k\cdot d 个数，每 k 个数分一段，一共 d 段。然后找出 \binom{d}{\frac{12}{k}} 个人，每个人从中选出 \frac{12}{k} 段，这样不重不漏地覆盖所有可能的选择情况。

例如当 k=4,d=5 时，找出五个段 [0,3],[4,7],[8,11],[12,15],[16,19]，每个人从中选出 3 段，一共十种选择，对应十个人。

容易证明这种构造满足条件。并且我们可以把多个这样的结构拼在一起——只需要保证它们使用的数互不相同即可。

找出所有可能的构造，使用动态规划把它们组合在一起即可。

#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=100;
int n,C[N][N],f[N],g[N],d[N],x[N],cnt[N],a[N];
void dfs(int A,int B,int k,int dif){
    if (A<B||B<0){
        return;
    }
    if (A==0){
        for (int i=1;i<=(12/k);++i){
            for (int j=0;j<k;++j){
                cout<<dif+a[i]*k+j<<' ';
            }
        }
        cout<<endl;
        return;
    }
    dfs(A-1,B,k,dif);
    a[B]=A-1;
    dfs(A-1,B-1,k,dif);
}
void solve(int n,int dif){
    if (n==0){
        return;
    }
//  cout<<"solve "<<n<<' '<<g[n]<<endl;
    int c=g[n];
    dfs(cnt[c],12/x[c],x[c],dif);
    solve(n-c,dif+d[c]);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    for (int i=0;i<N;++i){
        for (int j=C[i][0]=1;j<=i;++j){
            C[i][j]=min(C[i-1][j]+C[i-1][j-1],N);
        }
    }
    cnt[1]=1;d[1]=12;x[1]=12;
    for (int k=1;k<12;++k){
        if (12%k){
            continue;
        }
        for (int o=12/k+1;o*k<=50;++o){
            int c=C[o][12/k];
            if (c>50){
                break;
            }
            if (d[c]==0||d[c]>o*k){
                d[c]=o*k;x[c]=k;cnt[c]=o;
            }
        }
    }
    for (int i=1;i<=50;++i){
        f[i]=51;
    }
    for (int i=0;i<=50;++i){
//      cout<<f[i]<<endl;
        for (int j=1;i+j<=50;++j){
            if (!d[j]){
                continue;
            }
            if (f[i]+d[j]<f[i+j]){
                f[i+j]=f[i]+d[j];
                g[i+j]=j;
            }
        }
    }
    cin>>n;
    solve(n,0);
    return 0;
}