Stringsobits(模拟)
描述 Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits,of course,are either 0 or 1. This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1‘. Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1‘. 输入 A single line with three space separated integers: N,L,and I. 输出 A single line containing the integer that represents the Ith element from the order set,as described. 样例输入 5 3 19 样例输出 ?10011 题目大意: 求一个长度为N的有L个1的第I大的二进制数。 #include <bits/stdc++.h> using namespace std; typedef long long ll; int dp[35][35],ans[35]; void f(int n,int l,ll m) { ll s=0,la; for(int i=0;i<=n;i++) { la=s;s=0; for(int j=0;j<=l;j++) { s+=dp[i][j]; if(s>=m) { ans[i]=1; return f(n-1,l-1,m-la); } } } } int main() { int n,l; ll m; scanf("%d%d%I64d",&n,&l,&m); for(int i=0;i<=n;i++) dp[i][0]=1; for(int i=1;i<=n;i++)///i位有j位为1的方案数等价于C(i,j) for(int j=1;j<=i;j++) dp[i][j]=dp[i-1][j]+dp[i-1][j-1]; f(n,l,m); for(int i=n;i>=1;i--) printf("%d",ans[i]); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |