c语言编辑龟兔赛跑预测,6G.区间或和（C++）
赞
踩
区间或和(C++)
题目描述
求a|(a+1)|(a+2)|…|(b-1)|b。
其中|表示按位或。
输入描述:
多组输入，每行两个数表示a和b
输出描述:
对于每组输入，输出一个数a|(a+1)|(a+2)|…|(b-1)|b。
示例1
输入
99 109
68 77
55 66
34 43
1111234 1114321
输出
111
79
127
47
1179647
备注:
输入不超过10000行，0≤a,b≤1018，a≤b0≤a,b≤10^{18}，a≤b0≤a,b≤1018，a≤b
题目思路1：
优化的暴力求解，即按照题意直接做。
超时代码：
#include
int main()
{
long long a,b,result;
while( scanf( "%lld%lld",&a,&b ) != EOF )
{
result = a;
for(int i=a;i
{
result |= (i+1);
}
printf("%lld\n",result);
}
}
考虑到超时肯定是循环次数太多，再仔细理解题目，发现代码可以优化：
先用示例1的第一组数据来举例说明：
十进制
二进制
a
99
1100011
a+1
100
1100100
a+2
101
1100101
a+3
102
1100110
a+4
103
1100111
a+5
104
1101000
b-4
105
1101001
b-3
106
1101010
b-2
107
1101011
b-1
108
1101100
b
109
1101101
考虑a和b的二进制表示从高到低第一个不同的位i(即这个例子中的第4位)，必定b的第i位=1，a的第i位=0(因为a
那么可以断定，对于答案的二进制表示，
(1) 比第i位更高的那些位一定跟a相同。
(2) 第i位及比第i位更低的那些位一定为1。(是由于把a中比第i位更低的那些位都置为1得到的数一定在区间[a,b]中)
所以，我们没有必要从a | (a+1) | (a+2) | …… | (b-1) | b 这样一个一个按位或。我们可以越阶。
因为你可以发现：
1次循环：99 | 100 = 103
2次循环：103 | 101 = 103
3次循环：103 | 102 = 103
4次循环：103 | 103 =103
5次循环：103 | 104 = 111
6次循环：111 | 105 = 111
7次循环：111 | 106 = 111
8次循环：111 | 107 = 111
9次循环：111 | 108 = 111
10次循环：111 | 109 = 111
这样可以说大多数逐一循环都是在做无用功。只有第1吃循环和第5次循环才是有效的。
得到启发，那么下一步可以改写代码：
解题代码1(C语言)：
#include
int main()
{
long long a,b;
while( scanf( "%lld%lld",&a,&b ) != EOF )
{
while( a
printf("%lld\n",a);
}
}
解题代码1(C++语言)：
#include
using namespace std;
int main()
{
ios::sync_with_stdio(0);//加速
long long a, b;
while( cin>>a>>b )
{
while( a
cout << a << endl;
}
}
题目思路2：
按位或：0|1=1；1|0=1；1|1=1；0|0=0; 即二进制有1则1。
那么其实根据思路1的推断，我们就把比第i个位高的数位全部保留，把比第i个位低的数位全部改为1(即相同部分相同，其他部分都是1)，然后再把这个二进制转换为十进制输出即可。
解题代码：
#include
using namespace std;
int main()
{
ios::sync_with_stdio(false);//加速
long long a,b;
while( cin >> a >> b )
{
long long cnt = 0; //统计从高位数起，a,b有多少位不一样
//统计不同的个数，当a，b相同时退出循环，
//此时a，b的值都为与b相同的部分
while(a != b)
{
cnt++;
a >>= 1;
b >>= 1;
}
//将截掉不同部分的b左移cnt位，
//同时每左移一次，再b右边加个1(二进制)，
//这样就变成，相同部分相同，其他部分都是1
while(cnt--) b = (b<<1)^1;
cout << b << endl;
}
}