UVA 10718 Bit Mask 贪心+位运算

题意:给出一个数N,下限L上限U,在[L,U]里面找一个整数,使得N|M最大,且让M最小。

很明显用贪心,用位运算搞了半天,样例过了后还是WA,没考虑清楚。。。

然后网上翻到了一个人家位运算一句话解决了 = =....ORZ...

人家的分析:(by天然呆大神)

儘量讓 N 中為 0 的位元,M 為 1;N 為 1 的位元, M 為 0。
因此從高位往低位檢查,
如果 N 為 1(M 儘量為 0),若 M 不能為 0,則必是因為 M 為 1 仍小於 L;
如果 N 為 0(M 儘量為 1),若 M 不能為 1,則必是因為 M 為 0 仍大於 U(此時不可能),
換句話說,M 為 1 時,M 需不大於 U。

注意:如果是long long的位运算操作,最好在数后面加个LL,不如会溢出的。

代码:

 /*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: uva10718.cpp
* Lauguage: C/C++
* Create Date: 2013-09-04 09:26:39
* Descripton: UVA 10718 Bit Mask, bitmap, greed
*/
#include <cstdio>
#include <cmath>
#define repd(i, a, b) for (int i = (a); i >= (b); i--) const int MAXN = 100; int main() {
long long n, l, u, m, t;
while (scanf("%lld%lld%lld", &n, &l, &u) != EOF) {
int len = ceil(log(u) / log(2));
m = 0;
repd(i, len, 1) {
t = m | (1LL << (i - 1)); //1
if (n >> (i - 1) & 1) {
if (t <= l) m = t;
}
else {
if (t <= u) m = t;
}
}
printf("%lld\n", m);
}
return 0;
}
上一篇:python爬虫爬取全球机场信息


下一篇:HDU 4752 Polygon(抛物线长度积分)