uva 10718 - Bit Mask

点击打开链接uva 10718

题目意思：     给定三个undigned  int 数 N，L，U。要求我们找到一个M，满足L<=M<=U情况下有N|M值最大

解题思路：     1:思路：贪心
                       2:or运算就是|，即相同的为0，不同为1.所以如果要使得N|M的值最大，那么就应该使M的二进制数和N的二进制数对应的位上值相反，这样才能够满足N|M最大，同时也应该满足L<=M<=U.
                       3: 1题目说的暴力是不行的，所以我们必须从二进制考虑
                           2我们可以初始化M为0，就是二进制数上每一位都是0，那么从高位开始往下枚举；
                           3如果N_bit[i] = 0,那么这个时候令M_bit[i] = 1如果这个值小于U，那么符合否则从新令M_bit[i] = 0.  
                           4如果N_bit[i] = 1，那么这个时候是要判断如果令M_bit[i] = 1 后的值是否小于等于L，如果是则令M_bit[i] = 1(注意这里的判断条件if(tmp + pow(2,i) <= L )要有等号，2^i  = （2^0 + 2^1+......2^i-1）+ 1））；那么最后的答案就是最小的这个值了
                       4:注意数据类型是long long或unsigned int

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MAXN 110

long long  n , l , u , pos;
long long  ans , tmp , Max;
int n_bit[MAXN] , m_bit[MAXN];

long long judge(){
    long long sum = 0;
    for(int i = 0 ; i < 32 ; i++)
        sum += pow(2 , i)*m_bit[i];
    return sum;
}

void solve() {
    int i;
    pos = 0 ; Max = 0;
    memset(n_bit , 0 , sizeof(n_bit));
    memset(m_bit , 0 , sizeof(m_bit));
    tmp = n ;//求出N的二进制数
    while(tmp){
        int a = tmp & 1;
        n_bit[pos] = a;
        tmp >>= 1 ; pos++; 
    }
    for(i = 31; i >= 0 ; i--){//高位枚举
        if(!n_bit[i]){
            m_bit[i] = 1;
            tmp = judge();
            if(tmp > u) m_bit[i] = 0; 
        }
        else{
            tmp = judge();
            if(tmp + pow(2,i) <= l) 
                m_bit[i] = 1;
        }
    }
    ans = judge();
    printf("%lld\n" , ans);
}

int main() {
    //freopen("input.txt" , "r" , stdin);
    while(scanf("%lld%lld%lld" , &n ,&l ,&u) != EOF)
        solve();  
    return 0;
}