传送门:https://vjudge.net/problem/UVA-10718
Preview:
bitstream:a flow of data in binary form.
in bit-wise expression:用位表示。
Her face was a cold blank mask. 她装出一副冰冷冷毫无表情的样子。
perform a bit-wise AND operation.
In bit-wise expression, mask is a common term.
输入3个数 n,l,u,问你能否找出一个数m,在满足 l <= m <= u的情况下。使得m|n最大,如果有多个数都能使得m|n最大,那么输出最小的那个数。
分析:
这题用贪心来写。。我们知道或操作。只要有1进行或操作后会变成1。。
所以在进行贪心的时候。我们只要考虑n为1的位置尽量用0去填,n为0的位置尽量用1去填。
不过在这之前要进行一个判断。就是如果当前一位如果填上1,会超过上界r,则只能填0.如果当前一位填上了0,会使得即使后面每位都填上1也到不了下界l,则只能填1.
然后由于n最大为2^32。。本来想用位运算的结果悲剧了。。最后自己写了个快速幂去把一个数拆解成01的二进制数。
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,l,r; int vis[33]; ll num; ll mi(ll a,ll b) //快速幂 { ll ans=1; while(b) { if(b&1) ans=(ans*a); b>>=1; a=(a*a); } return ans; } int main() { while(~scanf("%lld%lld%lld",&n,&l,&r)) { for(int i=31;i>=0;i--) { if(n>=mi(2,i)) { n-=mi(2,i); vis[i]=1; } else vis[i]=0; } num=0; for(int i=31;i>=0;i--) { if(mi(2,i)+num>r) continue; //如果填1超过上界 else if(mi(2,i)-1+num<l) //如果填0到不了下界 num+=mi(2,i); else { if(!vis[i]) //0的位置填1 num+=mi(2,i); } } printf("%lld\n",num); } return 0; }
Resorce:
https://blog.csdn.net/accelerator_/article/details/10031579