【CodeForces】--- New Year's Eve(思维)

题目链接：Click Click Here

                    B. New Year's Evetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Since Grisha behaved well last year, at New Year’s Eve he was visited by Ded Moroz who brought an enormous bag of gifts with him! The bag contains n sweet candies from the good ol’ bakery, each labeled from 1 to n corresponding to its tastiness. No two candies have the same tastiness.

The choice of candies has a direct effect on Grisha’s happiness. One can assume that he should take the tastiest ones — but no, the holiday magic turns things upside down. It is the xor-sum of tastinesses that matters, not the ordinary sum!

A xor-sum of a sequence of integers a1, a2, …, am is defined as the bitwise XOR of all its elements: , here denotes the bitwise XOR operation; more about bitwise XOR can be found here.

Ded Moroz warned Grisha he has more houses to visit, so Grisha can take no more than k candies from the bag. Help Grisha determine the largest xor-sum (largest xor-sum means maximum happiness!) he can obtain.

Input
The sole string contains two integers n and k (1 ≤ k ≤ n ≤ 1018).

Output
Output one number — the largest possible xor-sum.

Examples
input
4 3
output
7
input
6 6
output
7
Note
In the first sample case, one optimal answer is 1, 2 and 4, giving the xor-sum of 7.

In the second sample case, one can, for example, take all six candies and obtain the xor-sum of 7.

思路：n和k，从1~n的n个数中，选出最多k个数，使选出的几个数字的异或最大。
分析：k为1，那么最多只选一个数，异或结果最大当然是n。若k不为1，即k大于等于2，则从1到k的k个数中，肯定能找到两个数的异或和，使得，数字n对应的二进制数的最高位‘1’后面的所有二进制位都是‘1’，这样异或的结果最大。那么当k大于等于2时，答案是唯一的。

这里写代码片
#include
typedef long long LL;
int main()
{LL n,k;while(~scanf("%lld%lld",&n,&k)){if(k==1)        //k为1printf("%lld\n",n);else            //k不为1{LL num=1;       //记录最终结果 while(n>>=1)    //n依次右移除以2，循环次数即为n二进制最高位的位数， {num<<=1;//每次循环,num左移乘以2，记录下最高位'1'对应的十进制数， }printf("%lld\n",(num<<1)-1);//num再乘以2减1得到对应十进制数哦 }}return 0;} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！