题解：CF234G Practice

Mrkn_chenyx12 · 2024-12-09 19:18:44 · 题解

解题思路

如果我们把一个人的分队情况看作一个二进制串，每次分队看作一个二进制位，那么显然一组合法的解就是使得不存在两个人的分队情况是同一个二进制串。

那么，显然地，最小的比赛次数就是 \lceil\log_2n\rceil。而一种简单且可行的做法，对于每个人，直接以这个人的编号的二进制的后 \lceil\log_2n\rceil 位作为这个二进制串，可以得知它们一定两两不同。

参考代码

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

int n, a[1024];

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    scanf("%d", &n);
    int cnt, k = ceil(log2(n));
    printf("%d\n", k);
    for (int i = 0; i < k; i++) {
        cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (j & (1 << i)) a[++cnt] = j;
        }
        printf("%d ", cnt);
        for (int j = 1; j <= cnt; j++) printf("%d ", a[j]);
        puts("");
    }
    return 0;
}