UESTC 548 Cow IDs [二进制排列]

点击打开题目链接

题意:给牛编二进制号,每个编号有k个1,求第N小的二进制数。

分析:编号种有m个0时,有C(k-1+m, k-1)个,这样可以递推组合数求出第N个数种有几个0,然后利用STL的next_permutation函数求出排列来即可,总耗时才26MS,不算是爆吧,哈哈。

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

const int maxn = 1e7 + 7;
char res[maxn];

int main() {
    int n, k; scanf("%d%d", &n, &k);
    int cur = 1, cnt0 = 0;
    while(n > cur) {
        n -= cur;
        ++cnt0;
        cur = cur*(cnt0+k-1)/cnt0;
    }
    res[0] = '1';
    for(int i = 1; i <= cnt0 + k - 1; ++i) {
        if(i < 1 + cnt0) res[i] = '0';
        else res[i] = '1';
    }
    res[cnt0+k] = 0;
    do {
        n--;
    } while(n && next_permutation(res + 1, res + cnt0 + k));
    puts(res);
    return 0;
}

欢迎留言