题意：
给出一个范围[m,n]，按照二进制表示中的1的个数从小到大排序，若1的个数相同，则按照十进制大小排序。求排序后的第k个数。注意：m*n>=0。
思路：
也是看论文的。一开始也能想到是这种解法，枚举0~31个1，逐步缩小第k个数的范围（其实就是找到第k个数应该有几个1），然后二分答案，直到找到第k个数。
我只是在找第k个数时不是二分答案，而是想直接从最高位往低位走，判断左子树中满足条件的数的数量，然后控制往下一位应该是0还是1（即往树的哪一个孩子方向走，直到根）。其实也是二分思想。
这题明显只有两个范围:[-INF,0]或者[0,INF]，要特别注意n=0或者m=0的情况，有可能第k个数就是0，否则，是不是0就没有什么影响了。
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
using namespace std;
const double PI = acos(-1.0);
const int N=; //注意大小 int f[N][N], bit[N], m, n, k;;
void pre_cal() //预处理组合数
{
f[][]=;
for(int i=; i<N; i++) //位数
{
f[i][]=f[i][i]=;
for(int j=; j<i; j++) //多少个1
{
f[i][j]=f[i-][j]+f[i-][j-];
}
}
} int cal(int n,int k,int b)
{
memset(bit, , sizeof(bit));
int len=, cnt=, ans=;
while(n) //转成b进制
{
bit[++len]=n%b;
n/=b;
}
for(int i=len; i>; i--)
{
if( bit[i]== )
{
ans+=f[i-][k-cnt]; //统计左边的
if(++cnt>k) break; //已超
}
}
if(cnt==k) ans++;
return ans;
} int get_ans(int m,int n,int k)
{
int i, num;
for(i=; i<=; i++) //枚举位数
{
num=cal(n,i,)-cal(m-,i,);
if(k-num<=) break;
else k-=num;
}
int L=m,R=n;
while( L<R ) //二分答案
{
int mid=R-(R-L+)/;
num=cal(mid,i,)-cal(m-,i,);
if( num<k ) L=mid+;
else R=mid; //如果等于，也是继续缩小范围的
}
return R;
} int main()
{
//freopen("input.txt","r",stdin);
pre_cal();
int t;cin>>t;
while(t--)
{
scanf("%d%d%d",&m,&n,&k);
if(m<)
{
m^=(<<); //改为正
if(n==) //上界为0
{
n--;
n^=(<<);
if(get_ans(m,n,k-)==n) printf("0\n");
else cout<<(get_ans(m,n,k)^(<<))<<endl;
}
else
{
n^=(<<);
cout<<(get_ans(m,n,k)^(<<))<<endl; //恢复负值
}
}
else
{
if(m==&&k==) {printf("0\n");continue;}
else if(m==) m++,k--;
cout<<get_ans(m,n,k)<<endl;
}
}
return ;
}
AC代码
