uva 10718 Bit Mask
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 integerN. You have to find a mask M such that L ≤ M ≤ U and N OR M is maximum. For example, ifN is 100 and L = 50, U = 60 thenM 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 ofM.
InputEach input starts with 3 unsigned integers N, L, U where L ≤U. Input is terminated by EOF.
OutputFor each input, print in a line the minimum value of M, which makesN OR M maximum.
Look, a brute force solution may not end within the time limit.
Sample Input
Output for Sample Input
100 50 60100 50 50100 0 1001 0 10015 1 15
5950271001
题目大意：每组数据包含三个有效数据：1）N； 2）L ； 3）U 要在L～U之间找出M和N做或运算得出的值最大的，，并且本身值最小的数。
解题思路：一开始，直接用或运算+暴力，毫不犹豫的超时了。然后用了另一种方法，先将N转化为二进制存在一个数组中，然后从高位开始往下遍历，构造M，若当前位为0，则在不超过上限的情况下，M的该位为1；若当前位为1，则在达不到下限的情况下，将M的该位赋为1。
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>#define M 32typedef long long ll;using namespace std;ll N, L, U, B[M + 1];int A[M + 1];int change(int *T, ll a) {for (int i = 0; i < M; i++) {T[i] = a % 2;a /= 2;}}int main() {B[0] = 1;for (int i = 1; i < M; i++) {B[i] = B[i – 1] * 2;}while (scanf("%lld %lld %lld", &N, &L, &U) == 3) {ll ans = 0, temp;change(A, N);for (int i = M – 1; i >= 0; i–) {if (!A[i]) {temp = ans + B[i];if (temp <= U) { //当N的该位为0，则在不超过上限的情况下，选1ans += B[i];}}else {temp = ans + B[i] – 1;if (temp < L) { //如果该位选1，达不到下限，则选1，若可以达到下限，为了保持ans最小，就选0ans += B[i];}}}printf("%lld\n", ans);}return 0;}
人若勇敢就是自己最好的朋友
