首页 > 代码库 > 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-简单模拟