数位DP + 二分

 

1 #include 
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int n,m,k,f[33][33]; 6 void init() 7 { 8     f[0][0]=1; 9     for(int i=1;i<=32;i++)10     {11         f[i][0]=f[i-1][0];12         for(int j=1;j<=i;j++) f[i][j]=f[i-1][j-1]+f[i-1][j];13     }14 }15 int cal(int x,int k)16 {17     int sum=0,tot=0,pos=0;18     int bit[33];19     memset(bit,0,sizeof(bit));20     while(x)21     {22         bit[++pos]=x%2;23         x/=2;24     }25     for(int i=pos;i>=1;i--)26     {27         if(!bit[i]) continue;28         sum+=f[i-1][k-tot];29         tot++;30         if(tot>=k) break;31     }32     if(tot==k) sum++;33     return sum;34 }35 int fnd(int l,int r,int k)36 {37     int i,num;38     for(i=1;i<=31;i++)39     {40         num=cal(r,i)-cal(l-1,i);41         if(num>=k) break;42         else k-=num;43     }44     int tmp=l;45     while(l<=r)46     {47         int mid=l+(r-l)/2;48         num=cal(mid,i)-cal(tmp-1,i);49         if(num>=k) r=mid-1;50         else l=mid+1;51     }52     return l;53 }54 int main()55 {56    // freopen("cin.txt","r",stdin);57     int t;58     init();59     scanf("%d",&t);60     while(t--)61     {62         scanf("%d%d%d",&m,&n,&k);63         if(m<0)64         {65             m&=~(1<<31);66             if(n==0)67             {68                 n--;69                 k--;70             }71             n&=~(1<<31);72            // printf("m=%d n=%d\n",m,n);73             printf("%d\n",(1<<31)|fnd(m,n,k));74         }75         else76         {77             if(m==0) k--,m++;78             printf("%d\n",fnd(m,n,k));79         }80     }81     return 0;82 }