codeforces Good Bye 2015 B. New Year and Old Property

时间:2023-03-08 23:28:25
codeforces  Good Bye 2015  B. New Year and Old Property

题目链接:http://codeforces.com/problemset/problem/611/B

题目意思:就是在 [a, b] 这个范围内(1 ≤ a ≤ b ≤ 10^18)统计出符合二进制数表示只有 1 个 0 的数量是多少。

  ***********************

  首先贴出一段绝对会超时的代码,连提交的勇气都木有呢~因为第四组数据已经接近龟速了,所以。。。(大家可忽略)

  

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; typedef __int64 ll;
ll a, b;
ll ans; int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE while (scanf("%I64d%I64d", &a, &b) != EOF) {
__int64 i;
ans = ; for (i = a; i <= b; i++) {
__int64 l = i;
int c = ;
while (l && c <= ) {
c += ((l & ) == ? : );
l >>= ;
}
if (c == )
ans++; }
printf("%I64d\n", ans);
}
return ;
}

  ***********************

  

  讲讲正确的解题思路 —— 就是暴力枚举啦.......当然不是将十进制数先化成二进制数再慢慢比对啦,我上面的代码就类似这个思想了,讲多都是泪,呜呜呜~~~

  是模拟二进制数,在 [1, 10^18] 范围内,统计出只出现二进制表示0只出现1次的数

  我还是第一次知道原来可以这样算= =、、、 慢慢积累经验吧~~~

  另外讲一讲数的范围, 2^61 已经比 10^18要大了,所以枚举的时候,举例到61次就行,代码有详尽的注释,大家慢慢欣赏 ^_^

  

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; typedef __int64 ll;
const int bit = ; // 2^61 = 1,152,921,504,606,846,976 int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE ll a, b;
while (scanf("%I64d%I64d", &a, &b) != EOF) {
int ans = ; for (int i = ; i <= bit; i++) {
ll mea = (1ll << i) - ; // 1, 11, 111, 1111, ... for (int j = ; j < i-; j++) {
ll t = mea - (1ll << j); // (1ll<<j): 1, 10, 100, 1000, ...
ans += (t >= a && t <= b);
}
}
printf("%d\n", ans);
}
return ;
}