题意：定义新的排序：先按一个数中二进制中1的个数从小到大排序，如果1的个数相同则按数的大小从小到大排序。问[A,B]之间有第K大的数是哪个。-2^31<=A,B<=2^31(A,B必定同正负，负数的二进制与它相反数的二进制相加=2^32)

题解：

负数可以直接+2^31-1转化为正数。

先确定答案中1的个数：依次统计区间[m,n]内二进制表示中含1的数量为0,1,2,…的数，直到累加的答案超过k，则当前值就是答案含1的个数，假设是ind。

怎么求？就先确定当前位填什么，然后后面还有多少个1可以填，组合数弄一下。

同时，我们也求出了答案是第几个[m,n]中含ind个1的数。因此，只需二分答案，求出[m,ans]中含s个1 的数的个数进行判断即可。

这个二分需要不断往左端点靠，假设答案是ans，ans+1也含有跟ans一样的还有ind个1的数的个数。

 

 

spoj1182（输入是十进制）

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 9 typedef long long LL;10 const int N=50;11 const LL MX=(1LL<<32);12 LL X,Y,K,c[N][N];13 14 void myswap(LL &x,LL &y){LL t;t=x;x=y;y=t;return;}15 16 void find_c()17 {18 memset(c,0,sizeof(c));19 c[0][0]=1;20 for(int i=1;i<=35;i++)21 {22 c[i][0]=1;23 for(int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];24 }25 }26 27 LL find_k(LL x,int ind,int k)//0~x how many numbers has k '1's;28 {29 if(ind==0 && k==0) return 1;30 if(x<0 || ind==0 || k<0) return 0;31 LL t=1LL<<(ind-1);32 if(x&t) return c[ind-1][k]+find_k(x,ind-1,k-1);33 else return find_k(x,ind-1,k);34 }35 36 int main()37 {38 freopen("a.in","r",stdin);39 // freopen("me.out","w",stdout);40 int T;41 scanf("%d",&T);42 find_c();43 while(T--)44 {45 scanf("%lld%lld%lld",&X,&Y,&K);46 if(X<0) X=MX+X;47 if(Y<0) Y=MX+Y;48 if(X>Y) myswap(X,Y);49 50 LL sum=0,ind=0,now,k;51 for(int i=0;i<=31;i++)52 {53 now=find_k(Y,32,i)-find_k(X-1,32,i);54 if(sum+now
          
         
        
       
      
     

 

 

 

 

usaco （usaco上输入输出都是二进制形式）

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 9 typedef long long LL;10 const int N=50;11 const LL MX=(1LL<<32);12 LL X,Y,K,c[N][N],d[N],bit[N];13 char s[20];14 15 void myswap(LL &x,LL &y){LL t;t=x;x=y;y=t;return;}16 17 void find_c()18 {19 memset(c,0,sizeof(c));20 c[0][0]=1;21 for(int i=1;i<=35;i++)22 {23 c[i][0]=1;24 for(int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];25 }26 }27 28 LL find_k(LL x,int ind,int k)//0~x how many numbers has k '1's;29 {30 if(ind==0 && k==0) return 1;31 if(x<0 || ind==0 || k<0) return 0;32 LL t=1LL<<(ind-1);33 if(x&t) return c[ind-1][k]+find_k(x,ind-1,k-1);34 else return find_k(x,ind-1,k);35 }36 37 LL read()38 {39 scanf("%s",s);40 LL x=0;int l=strlen(s);41 for(int i=l-1;i>=0;i--)42 {43 if(s[i]=='1') x+=bit[l-i-1];44 }45 return x;46 }47 48 int main()49 {50 // freopen("a.in","r",stdin);51 freopen("cowq.in","r",stdin);52 freopen("cowq.out","w",stdout);53 find_c();54 bit[0]=1;55 for(int i=1;i<=31;i++) bit[i]=bit[i-1]*2;56 57 X=read();58 Y=read();59 scanf("%lld",&K);60 // printf("X = %lld Y = %lld\n",X,Y);61 // scanf("%lld",&X,&Y,&K);62 if(X<0) X=MX+X;63 if(Y<0) Y=MX+Y;64 if(X>Y) myswap(X,Y);65 66 LL sum=0,ind=0,now,k;67 for(int i=0;i<=31;i++)68 {69 now=find_k(Y,32,i)-find_k(X-1,32,i);70 if(sum+now
           
            =k) r=mid;83 }84 // printf("%d\n",l);85 int x=0;86 while(l)87 {88 d[++x]=l%2;89 l/=2;90 }91 for(int i=x;i>=1;i--) printf("%d",d[i]);printf("\n");92 return 0;93 }