手机资讯类网站模板,我市强化属地网站建设,wordpress腾讯分析,成交型网站建设方案题意#xff1a; 给出一个范围[m,n]#xff0c;按照二进制表示中的1的个数从小到大排序#xff0c;若1的个数相同#xff0c;则按照十进制大小排序。求排序后的第k个数。注意#xff1a;m*n0。 思路#xff1a; 也是看论文的。一开始也能想到是这种解法#xff0c;枚… 题意 给出一个范围[m,n]按照二进制表示中的1的个数从小到大排序若1的个数相同则按照十进制大小排序。求排序后的第k个数。注意m*n0。 思路 也是看论文的。一开始也能想到是这种解法枚举0~31个1逐步缩小第k个数的范围其实就是找到第k个数应该有几个1然后二分答案直到找到第k个数。 我只是在找第k个数时不是二分答案而是想直接从最高位往低位走判断左子树中满足条件的数的数量然后控制往下一位应该是0还是1即往树的哪一个孩子方向走直到根。其实也是二分思想。 这题明显只有两个范围:[-INF,0]或者[0,INF]要特别注意n0或者m0的情况有可能第k个数就是0否则是不是0就没有什么影响了。 1 //#include bits/stdc.h2 #include iostream3 #include cstdio4 #include cstring5 #include cmath6 #include map7 #include algorithm8 #include vector9 #include iostream10 #define pii pairint,int11 #define INF 0x7f3f3f3f12 #define LL long long13 using namespace std;14 const double PI acos(-1.0);15 const int N35; //注意大小16 17 int f[N][N], bit[N], m, n, k;;18 void pre_cal() //预处理组合数19 {20 f[0][0]1;21 for(int i1; iN; i) //位数22 {23 f[i][0]f[i][i]1;24 for(int j1; ji; j) //多少个125 {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 len0, cnt0, ans0;35 while(n) //转成b进制36 {37 bit[len]n%b;38 n/b;39 }40 for(int ilen; i0; i--)41 {42 if( bit[i]1 )43 {44 ansf[i-1][k-cnt]; //统计左边的45 if(cntk) break; //已超46 }47 }48 if(cntk) ans;49 return ans;50 }51 52 53 int get_ans(int m,int n,int k)54 {55 int i, num;56 for(i0; i31; i) //枚举位数57 {58 numcal(n,i,2)-cal(m-1,i,2);59 if(k-num0) break;60 else k-num;61 }62 int Lm,Rn;63 while( LR ) //二分答案64 {65 int midR-(R-L1)/2;66 numcal(mid,i,2)-cal(m-1,i,2);67 if( numk ) Lmid1;68 else Rmid; //如果等于也是继续缩小范围的69 }70 return R;71 }72 73 74 int main()75 {76 //freopen(input.txt,r,stdin);77 pre_cal();78 int t;cint;79 while(t--)80 {81 scanf(%d%d%d,m,n,k);82 if(m0)83 {84 m^(131); //改为正85 if(n0) //上界为086 {87 n--;88 n^(131);89 if(get_ans(m,n,k-1)n) printf(0\n);90 else cout(get_ans(m,n,k)^(131))endl;91 }92 else93 {94 n^(131);95 cout(get_ans(m,n,k)^(131))endl; //恢复负值96 }97 }98 else99 {
100 if(m0k1) {printf(0\n);continue;}
101 else if(m0) m,k--;
102 coutget_ans(m,n,k)endl;
103 }
104 }
105 return 0;
106 } AC代码 转载于:https://www.cnblogs.com/xcw0754/p/4852036.html
