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.
5 3 19
A single line containing the integer that represents the Ith element from the order set, as described.
10011
这道题显然是数学题，只需要判断最前面的1在什么位置，每找到一个1，就把总个数减一。假设当前1的位置为i（默认最右边为编号一）,剩下最多可选1的个数为j，那么当前位置的大小为c(i-1,0)+c(i-1，1)+……+c(i-1,j)+1.如果当前的位置比I还要大，那么这个点一定是1，剩下选择的个数就减一。然后从头继续枚举。
核心代码：
while(k!=0){//k是剩下的大小
for(int i=1;i<=n+1;i++){
long long getans=get(i,last)+1;//getans是当前点的大小
if(k<getans){
dp[i-1]=1;//当前点定为1
k-=get(i-1,last);//若比他大则减去，此处减去的并不是getans，
last--;
break;
}else if(k==getans){
dp[i]=1;
k-=getans;
break;
}
}
}
全部代码：
/*
USER: yi zeng [yizeng21] TASK: kimbits LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [0.000 secs, 5436 KB] Test 2: TEST OK [0.000 secs, 5436 KB] Test 3: TEST OK [0.000 secs, 5436 KB] Test 4: TEST OK [0.000 secs, 5436 KB] Test 5: TEST OK [0.000 secs, 5436 KB] Test 6: TEST OK [0.000 secs, 5436 KB] Test 7: TEST OK [0.000 secs, 5436 KB] Test 8: TEST OK [0.000 secs, 5436 KB] Test 9: TEST OK [0.000 secs, 5436 KB] Test 10: TEST OK [0.000 secs, 5436 KB] Test 11: TEST OK [0.000 secs, 5436 KB] Test 12: TEST OK [0.000 secs, 5436 KB] Test 13: TEST OK [0.000 secs, 5436 KB] All tests OK.
*/
/* ID: yizeng21 PROB: kimbits LANG: C++ */ #include<stdio.h> #include<string.h> #include<iostream> using namespace std; long long q[400][400]; int time1[400]; void add(int s){ int t=2; while(s!=1){ if(s%t==0){ time1[t]++; s/=t; }else t++; } return; } void shan(int s){ int t=2; while(s!=1){ if(s%t==0){ time1[t]--; s/=t; }else t++; } return; } long long c(int p,int q){ if(p<q)return 0; long long ans=1; memset(time1,0,sizeof(time1)); for(int i=1;i<=p;i++)add(i); for(int i=1;i<=q;i++)shan(i); for(int i=1;i<=(p-q);i++)shan(i); for(int i=1;i<=p;i++){ for(int j=1;j<=time1[i];j++){ ans*=i; } } return ans; } long long get(int pos,int len){ long long ans=0; for(int i=1;i<=len;i++){ ans+=q[pos-1][i]; } return ans+1; } void wait(){ for(int i=1;i<=32;i++){ for(int j=i;j>=0;j--){ q[i][j]=c(i,j); } } } int dp[1000]; int main(){ freopen("kimbits.in","r",stdin); freopen("kimbits.out","w",stdout); int n,l; long long k; wait(); scanf("%d%d",&n,&l); cin>>k; int last=l; while(k!=0){//k是剩下的大小 for(int i=1;i<=n+1;i++){ long long getans=get(i,last)+1;//getans是当前点的大小 if(k<getans){ dp[i-1]=1;//当前点定为1 k-=get(i-1,last);//若比他大则减去，此处减去的并不是getans， last--; break; }else if(k==getans){ dp[i]=1; k-=getans; break; } } } for(int i=n;i>=1;i--) printf("%d",dp[i]); printf("\n"); }
usaco-Section 3.2-Stringsobits
原文：http://www.cnblogs.com/buffms/p/5156058.html