P12025 [USACO25OPEN] Sequence Construction S 题解

前言

把此题放到 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：

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;
}

P12025 [USACO25OPEN] Sequence Construction S 题解

文章操作

前言

解题思路

相关推荐

评论

P12025 [USACO25OPEN] Sequence Construction S 题解