SPOJ 1182. Sorted bit squence (数位统计+二分)
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：将区间内的数，按照二进制中1的个数升序排列，个数相同的按大小升序排列。求区间内第K个数。
http://www.spoj.pl/problems/SORTBIT/
关于数位统计类问题可以看论文 《浅谈数位类统计问题》
首先可以根据前一道题所学的，枚举1的个数，然后找到区间内含有若干个1的数量，最终得到第K个数包含几个1。
这样就确定出了答案中包含了Len个1。
然后在区间[l,r]内二分答案，查找[l,mid]中包含Len个1的个数，由些二分。
麻烦的时候题目中还有负数，负数是按照其补码计算。
不过题目说了同正同负，那么对于同正的没有问题，对于同负的。
最高位都为1，我们先把最高位的1去掉，就转化成了正数，然后再进行统计，最后输出的时候把最高位加上即可。
不过注意0的情况，特判！！！
#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 longusing 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;}