?
?
?
題意：
給出一個范圍[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就沒有什么影響了。
?
?
?
?
?
1 //#include <bits/stdc++.h> 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <map> 7 #include <algorithm> 8 #include <vector> 9 #include <iostream> 10 #define pii pair<int,int> 11 #define INF 0x7f3f3f3f 12 #define LL long long 13 using namespace std; 14 const double PI = acos(-1.0); 15 const int N=35; //注意大小 16 17 int f[N][N], bit[N], m, n, k;; 18 void pre_cal() //預處理組合數 19 { 20 f[0][0]=1; 21 for(int i=1; i<N; i++) //位數 22 { 23 f[i][0]=f[i][i]=1; 24 for(int j=1; j<i; j++) //多少個1 25 { 26 f[i][j]=f[i-1][j]+f[i-1][j-1]; 27 } 28 } 29 } 30 31 int cal(int n,int k,int b) 32 { 33 memset(bit, 0, sizeof(bit)); 34 int len=0, cnt=0, ans=0; 35 while(n) //轉成b進制 36 { 37 bit[++len]=n%b; 38 n/=b; 39 } 40 for(int i=len; i>0; i--) 41 { 42 if( bit[i]==1 ) 43 { 44 ans+=f[i-1][k-cnt]; //統計左邊的 45 if(++cnt>k) break; //已超 46 } 47 } 48 if(cnt==k) ans++; 49 return ans; 50 } 51 52 53 int get_ans(int m,int n,int k) 54 { 55 int i, num; 56 for(i=0; i<=31; i++) //枚舉位數 57 { 58 num=cal(n,i,2)-cal(m-1,i,2); 59 if(k-num<=0) break; 60 else k-=num; 61 } 62 int L=m,R=n; 63 while( L<R ) //二分答案 64 { 65 int mid=R-(R-L+1)/2; 66 num=cal(mid,i,2)-cal(m-1,i,2); 67 if( num<k ) L=mid+1; 68 else R=mid; //如果等于，也是繼續縮小范圍的 69 } 70 return R; 71 } 72 73 74 int main() 75 { 76 //freopen("input.txt","r",stdin); 77 pre_cal(); 78 int t;cin>>t; 79 while(t--) 80 { 81 scanf("%d%d%d",&m,&n,&k); 82 if(m<0) 83 { 84 m^=(1<<31); //改為正 85 if(n==0) //上界為0 86 { 87 n--; 88 n^=(1<<31); 89 if(get_ans(m,n,k-1)==n) printf("0\n"); 90 else cout<<(get_ans(m,n,k)^(1<<31))<<endl; 91 } 92 else 93 { 94 n^=(1<<31); 95 cout<<(get_ans(m,n,k)^(1<<31))<<endl; //恢復負值 96 } 97 } 98 else 99 { 100 if(m==0&&k==1) {printf("0\n");continue;} 101 else if(m==0) m++,k--; 102 cout<<get_ans(m,n,k)<<endl; 103 } 104 } 105 return 0; 106 }
?
