首页 > 代码库 > uva--10718+贪心
uva--10718+贪心
题意:
输入n,L,U,在L,U之间找一个数M使得n与M按位或的值最大,如果有多个M输出最小的那个。
思路:
将数化成二进制再结合或的性质就可以很容易得到一个贪心的策略:将n化为32位的二进制表示后
对于n中为0的位,使得M对应的二进制位为1.这样显然可以使得n|M值最大,但是同时还要考虑区间的限制;
n中二进制为0时,M对应的二进制位取1的条件是:必须保证后面M的最小值小于U,否则取0;n中二进制为1时,如果
M中对应位取0,则必须保证对应的M最大值要大于L,否则就要取1;
代码:
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> using namespace std; #define LL long long int main() { LL n,L,R,a[100]; int i,j; while(scanf("%lld%lld%lld",&n,&L,&R)!=EOF) { LL sum=0,min1,max1; int k=0; memset(a,0,sizeof(a)); while(n) { a[k++]=n%2; n=n/2; } k=32; for(i=k-1;i>=0;i--) { if(!a[i]&&sum+pow(2,i)<=R) sum+=pow(2,i); else { max1=sum+pow(2,i)-1; if(max1<L) sum+=pow(2,i); } } printf("%lld\n",sum); } return 0; }
uva--10718+贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。