Codeforces 912A/B

A. Tricky Alchemy

传送门：http://codeforces.com/contest/912/problem/A

参考程序如下：

#include <stdio.h>

#include <stdint.h>

int main(void)

{

    int64_t a, b, x, y, z;

    scanf("%I64d%I64d%I64d%I64d%I64d", &a, &b, &x, &y, &z);

    int64_t addA = 2LL * x + y - a > ? 2LL * x + y - a: ;

    int64_t addB = 3LL * z + y - b > ? 3LL * z + y - b: ;

    printf("%I64d\n", addA + addB);

    return ;

}

B. New Year's Eve

给定两个整数n、k：在1~n中选择至多k个整数，使得其异或和最大。求解这个最大值。

显然，当k=1时，只选择一个整数n，于是答案为n；

当k>1时，可以考虑异或和可能达到的最大值：将n的所有可改变的二进制位（即最高的‘1’位以下的二进制位）均变为‘1’，这个值就是异或和可能达到的最大值。

设S=2^b-1，则对于任意自然数a，若a<S，则一定有aÅ(S-a)=S。由于S的二进制位，0~b-1位均为‘1’，于是根据位运算的基本规则，等式显然成立。

于是，当k>1时，设n的最高‘1’位为b-1位，S=2^b-1，则可选择两个整数：n和S-n（注意，这里n≥2^b-¹，于是S-n<2^b-¹≤n）；特别地，当n=S时，只选择一个整数n。于是答案为S。

参考程序如下：

#include <stdio.h>

#include <stdint.h>

int main(void)

{

    int64_t n, k;

    scanf("%I64d%I64d", &n, &k);

    if (k == ) {

        printf("%I64d\n", n);

        return ;

    }

    int bit = ;

    for (; n >> bit; bit++);

    printf("%I64d\n", (1LL << bit) - );

    return ;

}

巴特西

Codeforces 912A/B

最新文章

热门文章