Codeforces Round #456 (Div. 2) B. New Year’s Eve 贪心、构造、位运算、异或和

My Solution

题意：给出1~n这n个数，最多选k个数，要求，选出的数的异或和最大，求这个异或和。

贪心、构造、位运算、异或和

首先对于n的二进制有b位，n ^ ((1<<b) - 1)的值必定小于n。

所以如果k为1，则只能选ans = n；

否则选n和n ^ ((1<<b) - 1)这2个数，当n和 ((1<<b) - 1)相等时依然选n，即 ans = (1<<b) - 1。

#include 
#include 

using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 8;


int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("b.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL n, k, ans = 0;
    cin >> n >> k;
    if(k == 1) cout << n << endl;
    else{
        while(n){
            ans <<= 1ll; ans |= 1ll; n >>= 1ll;
        }
        cout << ans << endl;

    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

Thank you!

                                                                                                                                             ------from ProLightsfx