给定 \(n\) 个数 \([1, 2, 3, \cdots, n]\) 和两个正整数 \(k\) 和 \(x\)。
将这些数分成恰好 \(k\) 组使得每组的异或和都是 \(x\)。
(\(1 \le k \le n \le 2 \cdot 10^5, 1 \le x \le 10^9\))。
首先,我们知道,如果我们无法从 \(n\) 个数中提取出 \(k\) 个异或和为 \(x\) 的集合,那么一定无解。所以我们想要尽量多的取提取集合,让每一个集合里的数尽量少。所以我们可以将所以异或和为 \(x\) 的集合写成 \([a \oplus x, a]\)(\(a\) 为正整数)这种形式。
证明如下:
假设我们现在已经无法提取出 \([a \oplus x, a]\) 这种形式的集合。
我们令 \(p\) 为 \(x\) 在二进制下的最高位,且 \(1 \sim n\) 中有 \(q\) 个数第 \(p\) 位为 \(1\)。
我们可以得到,对于 \([a \oplus x, a]\) 这个形式的集合,\(a \oplus x\) 与 \(a\) 中只有一个数第 \(p\) 位为 \(1\)。如果在没有选择的数中,仍有数第 \(p\) 位为 \(1\),那么它与 \(x\) 的异或和也一定没有选择,并且它们可以组成 \([a \oplus x, a]\) 这个形式的集合。因为 \(a \oplus x\) 一定比 \(a\) 小,并且 \(a\) 与 \(a \oplus x\) 一一对应,不会有其他数选中 \(a \oplus x\)。
有了上面的结论,我们就可以先去枚举 \(a\),尝试提取出 \(k\) 个形式为 \([a \oplus x, a]\) 或 \([x]\) 的集合。如果 \(a\) 已经从一枚举到了 \(n\),但仍未提出来 \(k\) 组集合,那么显然无解。如果能够提出来,去考虑剩下的数的异或和是否等于零。如果等于零,可以放在任意一个集合中,不影响这个集合最终的异或和。如果不为零,那么一定无解,因为我们想要满足条件就一定无法选中所有的数。实现就很简单了。
#include <bits/stdc++.h>
#define M 200005
using namespace std;
int T, n, k, x, cnt, tot;
bool vis[M];
pair<int, int> pa[M];
int main() {
ios::sync_with_stdio(0);
cin >> T;
for(int t = 1; t <= T; ++ t) {
cnt = 0;
tot = 0;
for(int i = 0; i <= n; ++ i)
vis[i] = 0;
cin >> n >> k >> x;
for(int i = 0; i <= n; ++ i) {
if(vis[i])
continue;
if((i ^ x) <= n) {
vis[i] = 1;
vis[x ^ i] = 1;
tot += (i == 0 ? 1 : 2);
pa[++ cnt] = {x ^ i, i};
if(cnt == k)
break;
}
}
if(cnt != k)
cout << "NO\n";
else {
int sum = 0;
for(int i = 0; i <= n; ++ i)
if(!vis[i])
sum ^= i;
if(sum == 0) {
cout << "YES\n";
for(int i = 1; i < k; ++ i) {
if(pa[i].second != 0)
cout << '2' << ' ' << pa[i].first << " " << pa[i].second << '\n';
else
cout << '1' << ' ' << pa[i].first << '\n';
}
int pos1 = pa[k].first, pos2 = pa[k].second;
cout << n - tot + (pos2 == 0 ? 1 : 2) << ' ';
for(int i = 1; i <= n; ++ i)
if(!vis[i] || i == pos1 || i == pos2)
cout << i << ' ';
cout << '\n';
}
else
cout << "NO\n";
}
}
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章