洛谷P2727 01串 Stringsobits

Shun

P2727 01串Stringsobits

•  
  
• 24通过
  
• 55提交
  
• 题目提供者该用户不存在
  
• 标签USACO
  
• 难度普及+/提高
  

 提交  讨论  题解  

最新讨论

• 这题的思路是啥啊！！！跪求…
  

题目背景

考虑排好序的N(N<=31)位二进制数。

题目描述

他们是排列好的，而且包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。

你的任务是输出第i（1<=i<=长度为N的二进制数的个数）小的（注：题目这里表述不清，实际是，从最小的往大的数，数到第i个符合条件的，这个意思），长度为N，且1的位数的个数小于等于L的那个二进制数。

（例：100101中，N=6，含有位数为1的个数为3）。

输入输出格式

输入格式：

共一行，用空格分开的三个整数N，L，i。

输出格式：

共一行，输出满足条件的第i小的二进制数。

输入输出样例

输入样例#1：

5 3 19

输出样例#1：

10011

说明

题目翻译来自NOCOW。

USACO Training Section 3.2

之前写的没保存，被删了......

分析：如果直接枚举，N可能高达32，TLE.换个思路，每位只能填0或1，有点类似动态规划的思想，其实可以这么做.考虑从右往左第i位填的数字，如果填1，那么得到的数必然要比要求的I小，关键是怎么计算这个数是第几大呢？设f[a]为填a个数最多只能填b个1的方案数，可以知道如果第i位填1，那么大小是f[i-1][l] + 1,这个很好证明.f数组该怎么推呢？第i位要么填1，要么填0，f[j] = f[i-1][j-1] + f[i-1][j].f[0] = f[o] = 1.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
long long n, l, I, f[55][55];
int main()
{
  scanf("%lld%lld%lld", &n, &l, &I);
  for (int i = 1; i <= n; i++)
    f[i][0] = 1;
  for (int i = 0; i <= l; i++)
    f[0][i] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= l; j++)
      if (j <= i)
        f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
      else
        f[i][j] = f[i][i];
  for (int i = n; i >= 1; i--)
    if (I && f[i - 1][l] < I)
    {
    printf("1");
    I -= f[i - 1][l];
    l--;
    }
    else
      printf("0");
  //while (1);
  return 0;
}