专栏文章

题解：CF234G Practice

MMrkn_chenyx12
CF234G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqu0h7a
此快照首次捕获于
2025/12/04 10:43
3 个月前
此快照最后确认于
2025/12/04 10:43
3 个月前
查看原文

解题思路

如果我们把一个人的分队情况看作一个二进制串，每次分队看作一个二进制位，那么显然一组合法的解就是使得不存在两个人的分队情况是同一个二进制串。
那么，显然地，最小的比赛次数就是 ⌈log⁡2n⌉\lceil\log_2n\rceil。而一种简单且可行的做法，对于每个人，直接以这个人的编号的二进制的后 ⌈log⁡2n⌉\lceil\log_2n\rceil 位作为这个二进制串，可以得知它们一定两两不同。

参考代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...