题解：P12025 [USACO25OPEN] Sequence Construction S

题意简述

构造序列使得：

$1 \le N \le 100$ 。
$a_1 + a_2 + \dots + a_N = M$ 。
$\text{popcount}(a_1) \oplus \text{ popcount}(a_2) \oplus \dots \oplus \text{ popcount}(a_N) = K$ 。

若无解输出

-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

。

17

是一个奇数，因为

1

和

2

二进制下都只含一个

1

，我们先从中取出一个

1

和一个

2

，再取出两个

(m-3) \div 2

。

对于一个偶数，直接取两个

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

题解：P12025 [USACO25OPEN] Sequence Construction S

文章操作

题意简述

基本思路

AC Code

相关推荐

评论

题解：P12025 [USACO25OPEN] Sequence Construction S