本题是求从 1~n 个数中取小于或等于 k 个数(比如 n = 4, k = 3 表示从 1~4 中取 1 个数或 2 个数或 3 个数),对这些数进行异或求和,求最大的异或求和值.
Problem
codeforces.com/contest/912/problem/B
Analysis
You can choose k or less than k integers from 1~n, calculate maximum xor result
(1) k = 1, You can only choose one integer, so you choose n and get the maximum xor result n
(2) k > 1, whatever k is, such as k = 2, or k = 3, ......, or k = n,
if n has x bits as binary code, the maximum xor result must be 2 ^ x - 1
(1)k = 1 时,即从 1~n 个数中 1 个数,那么最大的数自然是 n.结果为 n
(2)k > 1 时,假如 n 以二进制表示是 x 位数,则结果必为 2 ^ x - 1
可以取 4 和 3 这两个数,最大异或结果 = 4 xor 3 = 7 = 2 ^ 3 - 1
Example 1 n = 4,
k = 2 choose 4 and 3,
maximum = 4 xor 3 = 7
可以取 4 和 3 这两个数,也可以取 4,1,2 这三个数.
Example 2
n = 4, k = 3
Choose two numbers, 4 and 3. Or choose three numbers, 4, 1 and 2.
maximum = 4 xor 3 = 4 xor 1 xor 2 = 7 = 2 ^ 3 - 1
最大异或结果 = 4 xor 3 = 4 xor 1 xor 2 = 7 = 2 ^ 3 - 1
可以取 4 和 3,也可以取 4,1,2.最大异或结果为 7.
Example 3
n = 4, k = 4
Choose two numbers, 4 and 3. Or choose three numbers, 4, 1 and 2.
maximum = 7 = 2 ^ 3 - 1
You can not choose all for numbers, because 4 xor 1 xor 2 xor 3 xor 4 = 3, which is not the maximum result.
但不能取 4,1,2,3.因为 4 xor 1 xor 2 xor 3 xor 4 = 3,不是最大的结果.
只要在 1~6 中取 6 和 1 两个数就行了,6 xor 1 = 7 = 2 ^ 3 - 1
Example 4 n = 6,
k = 6 Just choose 1 and 6,
maximum = 6 xor 1 = 7 = 2 ^ 3 - 1
Code
Python2
import sys
n, k = map(int, raw_input().split())
if 1 == k:
print n
sys.exit(0)
res = 1
while res < n:
res = res * 2 + 1
print res
C Language
#include <stdio.h>
#include <stdint.h>
int main(void)
{
int64_t n, k;
scanf("%I64d %I64d", &n, &k);
if (1 == k)
{
printf("%I64d\n", n);
return 0;
}
int bit = 0;
for (; n >> bit; bit++);
printf("%d", n);
printf("%d", bit);
printf("%I64d\n", (1LL << bit) - 1);
return 0;
}
来源: http://www.jianshu.com/p/91bdbabdde0f