题目大意
在 \([l,r]\) 中选不超过 \(k\) 个相异的数使得异或和最小，输出方案。
思路分析
分类讨论：
- 当 \(k=1\) 时：
显然选 \(l\) 是最优的。
- 当 \(r-l+1\le 10\) 时：
直接 \(O(n2^n)\) 暴力枚举每个数选或不选即可。
（判了这个之后后面的很多讨论会简单很多。）
- 当 \(k=2\) 时：
我们发现两个不同的数的异或和最小为 \(1\)，因为当且仅当两个数相同时异或和为 \(0\)。
所以我们可以在 \([l,r]\) 内任找一个偶数 \(x\)，那么方案就是 \(x\) 和 \(x+1\)。
（因为 \(r-l+1>10\) 所以一定能找到）
- 当 \(k\ge 4\) 时：
容易发现对于任意 \(k\in N\)，均有 \(4k\oplus(4k+1)\oplus(4k+2)\oplus (4k+3)=0\)，所以我们只需要任取一个 \(k\) 就行了。
（因为 \(r-l+1>10\) 所以一定能找到）
- 当 \(k=3\) 时：
首先，我们可以按照 \(k=2\) 的方法得到异或和为 \(1\) 的答案，我们只需要考虑是否存在异或和为 \(0\) 的方案即可。
我们枚举 \(i,j\,(i>j)\)，构造 \(A=2^i+2^j,B=2^i+2^j-1,C=2^{j+1}-1\)，容易发现 \(A\oplus B\oplus C=0,A>B>C\)，考虑证明这样构造的合法性：
证明：
我们只需要证明如果存在异或和为 \(0\) 的选法，一定存在一种选法满足以上的形式即可。
将 \(A,B,C\) 的二进制形式列出：
当 \(A\) 固定时，\(C\) 不可能更大，因为当 \(C\) 增大时，\({\color{red}2}\) 部分会多出若干 \(1\)，那么 \(B\) 就必须也在 \(2\) 部分增加若干 \(1\)，那么 \(B\) 就大于 \(A\) 了，不符合题设。
若 \(A\) 的二进制表示中 \(1\) 的个数大于 \(2\)，那么 \({\color{red}3}\) 部分会多出若干 \(1\)，\(B,C\) 中必要有一个在对应的位置去掉若干个 \(1\) 来满足异或和为 \(0\) 的条件，故要么 \(B\) 变小要么 \(C\) 变小，如果这时的 \(A,C\) 在 \([l,r]\) 的范围内，那么之前的 \(A,C\) 也一定在 \([l,r]\) 的范围内。
若 \(A\) 的二进制表示中只有一个 \(1\)，那么不存在满足条件的 \(B,C\)。
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 200200, V = 40;
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
int l, r, k;
vector <int> ans;
void add(int x){
ans.push_back(x);
}
template <typename types, typename... Args> void add(types x, Args... args){
add(x), add(args...);
}
signed main(){
cin >> l >> r >> k;
if (k == 1) add(l);
else if (r - l + 1 <= 10) {
int len = r - l + 1, minans = inf, way = 0;
for (int i = 1; i < (1ll << len); i ++) {
int ans = 0, cnt = 0;
for (int j = 0; j < len; j ++)
if (i >> j & 1) {
ans ^= (l + j);
cnt ++;
}
if (cnt <= k && ans < minans) {
minans = ans;
way = i;
}
}
for (int i = 0; i < len; i ++)
if (way >> i & 1) add(l + i);
}
else if (k == 2) {
if (l & 1) l ++;
add(l, l + 1);
}
else if (k == 3) {
int flag = 0;
for (int i = 0; i <= V && !flag; i ++)
for (int j = i + 1; j <= V; j ++) {
int x = (1ll << i) | (1ll << j), y = x - 1, z = (x ^ y);
if (x <= r && z >= l) {add(x, y, z); flag = 1; break;}
}
if (!flag) {
if (l & 1) l ++;
add(l, l + 1);
}
}
else if (k >= 4) {
for (int i = l; i <= l + 4; i ++)
if (i % 4 == 0) {
add(i, i + 1, i + 2, i + 3); break;
}
}
int res = 0;
for (auto it : ans) res ^= it;
cout << res << '\n';
cout << ans.size() << '\n';
for (auto it : ans) cout << it << ' ';
return 0;
}