题解 P2727 【01串 Stringsobits】

约修亚_RK · 2016-10-27 21:41:12 · 题解

这题真是杀了我好几刀回马枪……

注意点：“第几小的数”用int不够，要用long long int。

我们的目标是找到第i个长为N的，最多含有L个1的二进制数。那么，用F[k, i]来表示在前k位中，恰有i个1的二进制数的数量。Sum(F[k, 0~i])就表示在前k位中，最多有i个1的二进制数的数量。

转移方程很好写，边界条件是F[k, 0] = 1（在前k位中，没有1的二进制数只有一个，每一位都是0）。

F[k, i] = F[k-1, i] + F[k-1, i-1]，分别是第k位是0和第k位是1。

接下来，for k in [0, n]（注意，从0开始循环），求出Sum(F[k, 0~L])。如果这个和大于p，就说明我们要求的这个数字包含在bit[k]=1的情况里。（因为之前的都小于p）。那么我们就可以把p扣除掉bit[k]=0的情况，也就是扣掉Sum(F[k-1, 0~i])【即第k位是0时，至多有i个1的二进制数的数量。】。

确定了bit[k]=1，那么就可以把L和n各扣掉1，继续找下一个为1的位了（重复上面步骤）。

最后倒序输出这个二进制数就完成了。

/* P2727
 * Au: SJoshua
 */
#include <cstdio>
#include <algorithm>

using namespace std;

int dp[33][33];
bool num[33];

void search(int n, int l, long long int p) {
    long long int s, last;
    for (int k = 0; k <= n; k++) {
        last = s;
        s = 0;
        for (int i = 0; i <= l; i++) {
            s += dp[k][i];
            if (s >= p) {
                num[k] = true;
                return search(n-1, l-1, p-last); 
            }
        }
    }
}

int main(void) {
    int n, l;
    long long int p;
    scanf("%d %d %lld", &n, &l, &p);
    for (int k = 0; k <= n; k++) {
        dp[k][0] = 1;
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= k; i++) {
            dp[k][i] = dp[k-1][i] + dp[k-1][i-1];
        }
    }
    search(n, l, p);
    for (int k = n; k >= 1; k--) {
        printf("%d", num[k]);
    }
    return 0;
}