UVa 10718：Bit Mask

UVa 10718：Bit Mask2014-10-31 csdn shuangde800【链接】

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1659

【原题】

In bit-wise expression, mask is a common term. You can get a certain bit-pattern using mask. For example, if you want to make first 4 bits of a 32-bit number zero, you can use 0xFFFFFFF0 as mask and perform a bit-wise AND operation. Here you have to find such a bit-mask.

Consider you are given a 32-bit unsigned integer N. You have to find a mask M such that L ≤ M ≤ U and N OR M is maximum. For example, if N is 100 and L = 50, U = 60 then M will be 59 and N OR M will be 127 which is maximum. If several value of M satisfies the same criteria then you have to print the minimum value of M.

Input
Each input starts with 3 unsigned integers N, L, U where L ≤ U. Input is terminated by EOF.

Output
For each input, print in a line the minimum value of M, which makes N OR M maximum.

Look, a brute force solution may not end within the time limit.

样例输入：

100 50 60
100 50 50
100 0 100
1 0 100
15 1 15样例输出：

59
50
27
100
1【题目大意】

给三个32位unsignedint数字N,L,U, 找出到一个数字M， L ≤ M ≤ U ,使得N | M（或）的结果最大，并且M最小。

【分析与总结】

由于L和U可能会相差非常大，比如L=1，U=2137384647，直接暴力枚举的话肯定会超时的。所以需要换个方法，用贪心的思路。

为了使得N|M最大，就要使得这个结果的二进制高位尽可能的是1，所以可以用数组来模拟二进制计算。这个二进制数组的初始值等于L。

然后从高位往低位枚举，

对于第k位，如果N[k]==0,那么为了使得N的值尽量变大，就要让N[k]变为1，为了使N[k]变为1，就要让M[k]=1（使N[k]|M[k]==1）,但是还要考虑M[k]变为1之后，M的新值是否>U,如果大于U的话就不能让M[k]变为1了。

本栏目更多精彩内容：http://www.bianceng.cn/Programming/sjjg/

如果N[k]已经等于1了，那么就没有必要让M[k]也是1了（因为1|0==1）。那么M[k]如果是0就不管继续枚举下去，如果M[k]是1，就尝试是否可以把M[k]变为0，如果变为0之后还满足M二进制数组的值>=L的话，就可以变为0（因为使得M尽量地小）.

最终得到的M数组表示的值就是答案了。

【代码】

/** UVa:10718 - Bit Mask* Type:Greedy* Result: Accept* Time: 0.012s * Author: D_Double**/#include<iostream>#include<cstdio>#include<cstring>using namespace std;long long N,L,U;bool bit[32], tmp[32]; inline long long getValue（）{long long ans=0, U=1;for（int i=31; i>=0; --i）if（bit[i]）{ans += U<<（31-i）;}return ans;} long long solve（）{memset（bit, 0, sizeof（bit））; for（int i=0; i<32; ++i）bit[i] = L>>（31-i）&1; for（int i=31; i>=0; --i）{if（（N >> i & 1）==0 && bit[31-i]==false）{bit[31-i]=true; memcpy（tmp, bit, sizeof（bit））; int j=31-i+1; bool flag=false;while（j<=32）{if（getValue（）<=U）{flag=true; break;}while（bit[j]==false && j<32）++j;if（j==32）break;bit[j] = false;}if（！flag）{memcpy（bit, tmp, sizeof（tmp））;bit[31-i] = false;}}else if（（N>>i&1）==1&&bit[31-i]==true）{bit[31-i] = false;if（getValue（） < L）bit[31-i] = true;}}return getValue（）;} int main（）{while（scanf（"%lld%lld%lld",&N,&L,&U）！=EOF）{long long ans=solve（）;printf（"%lld
", ans）;}return 0;}