自动搬运

查看原文

来自洛谷，原作者为

	Little_x_starTYJ 愿时光能缓，愿故人不散！ || 众所周知，如果把灯泡放在嘴里，即使你自己一个人也取得出来灯泡。

搬运于2025-08-24 23:12:13，当前版本为作者最后更新于2025-06-29 11:54:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

把此题放到 T4 然后模拟考最为期末成绩，目前感觉快 AFO 了。最后 $20 + 100 + 20 + 10 = 150pts$。想要考试的四道原题的家人们可以私信我要题号。

解题思路

防止读者在阅读时忘记 $\text{popcount}(x)$ 时什么意思，所以就放在这里了。

$\text{popcount}(x)$ 表示整数 $x$ 的二进制表示中 $1$ 的位数。例如，$\text{popcount}(11) = 3$，$\text{popcount}(16) = 1$。

乍眼一看似乎很不可做的样子，实则因人而异。

赛时看到异或，首先想到 01trie，然后想了一阵发现不会，于是就没想了。

赛后瞅一眼题解，发现了一条重要性质：$\text{popcount}(1) = \text{popcount}(2)$。我赛时怎么没想到！

相信大家看到题目可能会先想着去构造序列 $a$，使得其满足 $a_1 + a_2 + \cdots + a_N = M$ 吧，但是这样很难再进行构造使得 $\text{popcount}(a_1) \oplus \text{popcount}(a_2) \oplus \cdots \oplus \text{popcount}(a_N) = K$，所以我们可以先使得其满足条件 $3$，再来想办法让其满足条件 $2$。

我们先构造一个满足条件的序列 $a$，使此序列的和最小（不是异或和）。其实我们并不需要考虑类似 $x\oplus x = 0, x \oplus x \oplus x = x$ 的情况，我们要求和最小就是为了避免初步构造时出现上述复杂情况（因为如果这些数的某一位上重复出现很多次 $1$，那么它们的总和一定不是最小的，我们可以使得这一位只出现 $0$ 次或 $1$ 次 $1$ 来达到同样的效果），即我们需要一步一步来，不能做到一步到位。

怎么构造和最小且满足条件 $3$ 的序列呢？想到异或与二进制有关，因此可以考虑对于 $K$ 进行二进制分解。这一步可能有点绕且难以描述，所以我们以第二组数据进行模拟再进行解释。

$M = 33, K = 5$，首先二进制分解 $K$ 得到 $(101)_2$，向答案数组里面添加 $2^4 - 1, 1$，因为第一个 $1$ 代表 $2^2 = 4$，所以得到 $2^4 - 1$。

为什么要这么做？别忘了 $K$ 代表的是所有数在二进制下 $1$ 的个数的和，那么将其二进制拆分则代表第 $1$ 个数的 $1$ 的个数为 $4$，那么最小的数即 $(1111)_2 = 2^4 - 1$。

那么我们选出来的这些数即我们的初始元素。将 $M$ 减去这些数的和，记为 $M_2$。

• 如果 $M_2 < 0$，显然无解。
• 否则如果 $M_2 = 0$，那么我们构造的 $a$ 已经同时满足条件 $1,2$ 了，直接输出即可。
• 否则如果 $M_2 = 1$，则我们还差 $1$ 才能同时满足条件 $1,2$。
• • 如果已构造出来的序列中有 $1$，由于 $\text{popcount}(1) = \text{popcount}(2)$，所以我们可以将序列中的 $1$ 变成 $2$ 来达到条件。
• • 如果已构造出来的序列中没有 $1$，那么一定无解，因为不存在某个数与序列中的所有数同时满足为 $2^i,2^j$ 且 $|2^i - 2^j| = 1$。
• 否则如果 $M_2$ 为偶数，直接往答案序列中加入两个 $\frac{M_2}{2}$ 即可（两个相同的数异或后值为 $0$，不影响条件 $3$）。
• 否则即 $M_2$ 为奇数，由于 $\text{popcount}(1) = \text{popcount}(2)$ 且 $M_2 \geq 3$（$M_2 = 1$ 的情况处理过了），因此我们可以从 $M_2$ 中取出来一个 $1$ 和 $2$ 就可以将 $M_2$ 转化为偶数的情况。（因为取出来一个 $2$ 虽然可能会导致 $M_2$ 的二进制排列差异过大，但是取出来一个 $1$ 和 $2$ 过后，后面两个数都为 $\frac{(m - 3)}{2}$，异或后为 $0$，前面只有 $1,2$ 且 $\text{popcount}(1) \oplus \text{popcount}(2) = 0$，所以 $0 \oplus 0 = 0$，$1 + 2 + \frac{(m - 3)}{2} \times 2 = M_2$，所以此方案可行。）

对于条件 $1$ 就懒得说了，大家可以看看代码，满打满算 $5 + 1 + 4 = 10 < 100$。

如果本题解有什么写错的地方可以在评论区踹我一脚，我好修改，没看懂的也可以踹我一脚，我好写得更详细。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> v;
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int m, k, sum = 0;
		cin >> m >> k;
		bool flag1 = false;
		v.clear();
		for (int i = 5; i >= 1; i--) {
			int p = (1 << i);
			if (k >= p) {
				k -= p;
				v.emplace_back((1 << p) - 1);
       //emplace_back = push_back，据说跑得要快点而已。
				sum += (1 << p) - 1;
			}
		}
		if (k) {
			flag1 = true;
			v.emplace_back(1);
			sum++;
		}
		if (sum > m) {
			cout << "-1\n";
			continue;
		}
		m -= sum;
		if (m == 1) {
			if (flag1) {
				v.pop_back();
				v.emplace_back(2);
			} else {
				cout << "-1\n";
				continue;
			}
		} else if (m) {
			if (m & 1) {
				v.emplace_back(1);
				v.emplace_back(2);
				if (m > 3) {
					v.emplace_back((m - 3) / 2);
					v.emplace_back((m - 3) / 2);
				}
			} else {
				v.emplace_back(m / 2);
				v.emplace_back(m / 2);
			}
		}
		cout << v.size() << "\n";
		for (auto u : v) {
			cout << u << ' ';
		}
		cout << "\n";
	}
	return 0;
}