51Nod 1496 最小异或和

Problem

一个集合包含一组相互不同的数字。现在我们要去寻找一个集合，他要满足如下性质：

对于所有 𝑥(𝑥∈𝑆) ，要满足l ≤ x ≤ r;

1 ≤ |S| ≤ k;

设S中第i个元素是 𝑠𝑖 ;那么 𝑓(𝑆)=𝑠1 ⨁ 𝑠2 ⨁ ... ⨁ 𝑠|𝑆| 的值要尽可能小。

Solution

k=1，答案为l。

k=2，如果偶数-奇数存在为1，但有特殊情况，答案为两者异或和和两个数取最小。

k=3，至少有三个连续的数，则必然<=1，只需要找是否为0，两个数异或不可能为0，考虑l的最高位，记为第i位，如果要全消除，则另外两个数第i位必有1个1，1个0，又第i位为0的数不可能比l小，则此数i+1位为1，那么第i位为1的数第i+1位也为1。

即： 1 1 0 0 0 0 0 0 1 0 X X X X X X 1 X X X X X X ——左边界l

k=4，如果可以选择的数大于4个直接为0，否则4个数暴力找。

Code

#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>

typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll l, r, k;
ll a[10];

int main() {
    io_opt;
    cin >> l >> r >> k;
    if (k == 1) {
        cout << l << endl;
    } else if (k == 2) {
        if (r - l + 1 == 2) {
            cout << min(l, min(r, l ^ r));
        } else {
            cout << "1" << endl;
        }
    } else if (k == 3) {
        int cnt = 0;
        while (l) {
            cnt++;
            l >>= 1;
        }
        if ((3LL << (cnt - 1)) <= r) {
            cout << "0" << endl;
        } else {
            cout << "1" << endl;
        }
    } else {
        if (r - l + 1 > 4) {
            cout << "0" << endl;
        } else {
            a[1] = l, a[2] = l + 1, a[3] = l + 2, a[4] = l + 3;
            ll ans = 1;
            ans = min(ans, a[1] ^ a[2] ^ a[3]);
            ans = min(ans, a[1] ^ a[2] ^ a[4]);
            ans = min(ans, a[1] ^ a[3] ^ a[4]);
            ans = min(ans, a[4] ^ a[2] ^ a[3]);
            ans = min(ans, a[1] ^ a[2] ^ a[3] ^ a[4]);
            cout << ans << endl;
        }
    }
    return 0;
}