题解：CF234G Practice

lailai0916 · 2024-12-09 20:09:24 · 题解

解题思路

设 k 人需要 p_k 次比赛，下一场比赛将分成 i 人和 k-i 人。

显然这 i 人和 k-i 人相互独立，不需要额外的比赛，所以 p_k=\max(p_i,p_{k-i})+1。显然当 i=k-i=\frac{n}{2}，即两队人数均匀时，获得最优解。

每次比赛都最多让两半人相互独立，因此以至少需要 k=\left\lceil\log_2 n\right\rceil=\left\lfloor\log_2 (n-1)\right\rfloor+1 场比赛。

注意到，任意两个不同的非负整数，至少有一位二进制不同，所以不妨根据第 j 位二进制进行分组。（0\le j<k）

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int a[N];
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int k=__lg(n-1)+1;
    cout<<k<<'\n';
    for(int j=0;j<k;j++)
    {
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(!(i>>j&1))ans++;
        }
        cout<<ans<<' ';
        for(int i=0;i<n;i++)
        {
            if(!(i>>j&1))cout<<i+1<<' ';
        }
        cout<<'\n';
    }
    return 0;
}