题解：P12025 [USACO25OPEN] Sequence Construction S
CommandSR
·
·
题解
题意简述
构造序列使得：
若无解输出 -1。
基本思路
因为 k 是一堆东西的异或和，不难想到对 k 进行二进制分解。
以 k=5 为例，(5)_{10} = (101)_{2}。
对于第一位 1，它由一个 x 满足 \text{popcount}(x) = 4 贡献而来，这个 x 最小为 2^4-1 = 15，故我们将 15 加入序列，同样的对于最后一位 1，将 2^1-1=1 加入序列。
该样例对应的 m=33，减去 15 和 1 后还剩下 17。
我们需要之后的元素 1 的个数异或和为 0。
对于一个偶数，直接取两个 $n \div 2$ 则满足条件。
考虑无解情况，若 $m$ 在某一步小于了 $0$，则无解。
若剩余的 $m$ 为 $1$，如果当前序列有一个 $1$，改为 $2$ 可以凑出一组解，否则无解。
## AC Code
```cpp
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = a; i <= b; ++i)
#define _F(i, a, b) for (int i = a; i >= b; --i)
#define ll long long
using namespace std;
ll rd() {
ll p = 0, f = 1; char ch = getchar();
while (ch>'9' || ch<'0') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch>='0' && ch<='9') p = p*10+ch-'0', ch = getchar();
return p * f;
}
ll m, k, a[110], tot = 0;
void Solve() {
tot = 0;
m = rd(), k = rd();
_F(i, 5, 0) {
if (k & (1<<i)) {
ll cur = (1<<(1<<i))-1;
m -= cur, a[++tot] = cur;
if (m < 0) {
cout << -1 << '\n';
return ;
}
}
}
if (m == 1) {
if (a[tot] != 1) {
cout << -1 << '\n';
return ;
}
++a[tot];
} else if (m % 2 == 0) {
a[++tot] = m/2, a[++tot] = m/2;
} else {
a[++tot] = 1, a[++tot] = 2, a[++tot] = (m-3)/2, a[++tot] = (m-3)/2;
}
cout << tot << '\n';
F(i, 1, tot) cout << a[i] << ' ';
cout << '\n';
}
int main() {
ll T = rd(); while (T--) Solve();
return 0;
}
```