題目：將區間內的數，按照二進制中1的個數升序排列，個數相同的按大小升序排列。求區間內第K個數。
http://www.spoj.pl/problems/SORTBIT/
關於數位統計類問題可以看論文 《淺談數位類統計問題》
首先可以根據前一道題所學的，枚舉1的個數，然後找到區間內含有若干個1的數量，最終得到第K個數包含幾個1。
這樣就確定出了答案中包含了Len個1。
然後在區間[l,r]內二分答案，查找[l,mid]中包含Len個1的個數，由些二分。
麻煩的時候題目中還有負數，負數是按照其補碼計算。
不過題目說了同正同負，那麼對於同正的沒有問題，對於同負的。
最高位都為1，我們先把最高位的1去掉，就轉化成了正數，然後再進行統計，最後輸出的時候把最高位加上即可。
不過注意0的情況，特判！！！
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 30
#define inf 1<<29
#define MOD 2007
#define LL long long
using namespace std;
int c[35][35]={0};
//統計[0,n]中包含k個1的數量
int slove(int n,int k){
int sum=0,tot=0;
for(int i=31;i;i--){
if(n&(1<<i)){
tot++;
if(tot>k)
break;
n^=(1<<i);
}
if((1<<(i-1))<=n)
sum+=c[i-1][k-tot];
}
if(tot+n==k) sum++;
return sum;
}
int calc(int l,int r,int k){
int len=1;
for(int i=1;i<=31;i++){
int now=slove(r,i)-slove(l-1,i);
if(k<=now) break;
k-=now;
len=i+1;
}
int low=l,high=r,mid;
while(low<high){
//二分答案，然後查找[l,mid]中包含len個1的數量
mid=(int)(((LL)low+(LL)high)/2);
int now=slove(mid,len)-slove(l-1,len);
if(now<k)
low=mid+1;
else
high=mid;
}
return low;
}
int main(){
int t,l,r,k;
for(int i=0;i<=32;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&l,&r,&k);
if(l==0&&r==0){
printf("0\n");
continue;
}
if(l>=0&&r>=0){
if(l==0){
k--;
l=1;
}
if(k==0){
printf("0\n");
continue;
}
printf("%d\n",calc(l,r,k));
}
else{
if(r==0){
k--;
r=-1;
}
//去掉最高位
l&=(~(1<<31));
r&=(~(1<<31));
cout<<l<<" "<<r<<endl;
printf("%d\n",(1<<31)|calc(l,r,k));
}
}
return 0;
}
作者：ACM_cxlove
