P12025 [USACO25OPEN] Sequence Construction S 题解
Snowflake_Fairy
·
·
题解
前言
把此题放到 T4 然后模拟考最为期末成绩，目前感觉快 AFO 了。最后 20 + 100 + 20 + 10 = 150pts。想要考试的四道原题的家人们可以私信我要题号。
解题思路
防止读者在阅读时忘记 \text{popcount}(x) 时什么意思，所以就放在这里了。
乍眼一看似乎很不可做的样子，实则因人而异。
赛时看到异或，首先想到 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：
```cpp
#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;
}
```