首页 > 代码库 > Gym611B-New Year and Old Property-简单模拟
Gym611B-New Year and Old Property-简单模拟
【题目大意】给出两个数a,b.求出在[a,b]区间中二进制形式只包含一个0的数字个数。
【解题思路】对于满足整数域中满足上面要求的数字都是可以按序求出的,例如10,101,110,1011,1101,1110…并且当二进制的长度(不为零的最高位)确定,该长度的满足要求数字个数是确定的。并且可以根据规律求出。
因此,可以求得≥a且最小的 满足要求的数A(用(l1,z1)表示。L:二进制长度,Z:唯一一个0的位置)同理也有≤b的最大的数B(l2,z2),进而可以根据A和B得出ans。
代码如下
1 #include "iostream" 2 using namespace std; 3 int Slong(long long s) //求出数字长度 4 { 5 int i = 0; 6 while (s) 7 { 8 s = s / 2; 9 i++;10 }11 return i;12 }13 long long getnz(int n, int z)//根据数字长度(二进制)和0的位置==>十进制数字14 {15 long long i = 1;16 long long k = 0;17 for (int j = 1 ; j <= n ; j++)18 {19 if ( j != z ) k += i;20 i *= 2;21 }22 return k;23 }24 int main()25 {26 long long a, b;27 int n1 = 0, n2 = 0, z1 = 0, z2 = 0;28 cin >> a >> b;29 int l = Slong(a);30 if (a > getnz(l, 1))31 // 边界:如果a比该长度下最大的满足要求数字还大,32 // A的为(L+1,L)33 // 长度比a长1第二高位为034 // (例:10111111111111111……)35 {36 n1 = l + 1;37 z1 = l;38 }39 else40 for ( int i = l - 1 ; i >= 1 ; i-- ) //从小到大枚举该长度下的数字,求A41 {42 if (getnz(l, i) >= a)43 {44 n1 = l;45 z1 = i;46 break;47 }48 }49 l = Slong(b);50 if (b < getnz(l, l - 1))51 // 边界:如果b比该长度下最小的满足要求数字还小,52 // A的为(L-1,1)53 // 长度比a小1第一位为054 // (例:11111……1110 )55 {56 n2 = l - 1;57 z2 = 1;58 }59 else60 for ( int i = 1 ; i < l ; i++ )// 从大到小枚举该长度下数,求得B61 {62 if (getnz(l, i) <= b)63 {64 n2 = l;65 z2 = i;66 break;67 }68 }69 //n1,n2表示A,B长度 z1,z2 表示A,B中0的位置70 int ans;71 if (n1 > n2) ans = 0; //ans = 0的情况72 else if (n1 == n2) ans = (z1 - z2) + 1;73 else ans = (n1 + n2 - 2) * (n2 - n1 - 1) / 2 + z1 + n2 - z2;74 // 求得长度[n1+1,n2-1]中数字个数【 (n1 + n2 - 2) * (n2 - n1 - 1) / 2】75 // 长度n1中数字个数 【z1】76 // 长度n2中数字个数 【n2 - z2】77 cout << ans << endl;78 }
Gym611B-New Year and Old Property-简单模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。