题解：CF234G Practice

原题链接

• 洛谷 CF234G Practice

解题思路

设 $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;
}