自动搬运

查看原文

来自洛谷，原作者为

	s4CRIF1CbUbbL3AtIAly 僕だって空を飛べる / 雲になっていく / 風になっていく / いつかはみんな / 星になっていく

搬运于2025-08-24 22:56:45，当前版本为作者最后更新于2023-12-23 15:54:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意：$\Omega(S)$ 为集合 $S$ 的所有非空子集的元素和所组成的集合，构造使得 $|\Omega(S)|$ 最小的 $S$。

观察样例并不能得到什么很好的结果，因此开始手动构造。

简单构造一会发现对于大小为 $n$ 的集合，最优的情况大概就是 $-\frac n2\sim\frac n2$ 所有整数。当然这里可以统一缩放。

众所周知想要证明一个东西的最小值就是先找到一个下界满足所有可能值都不会小于它，之后给出一个值为下界的构造。现在我们猜测这个情况就是下界，考虑证明。

首先我们注意到 $0$ 非常厉害，它可以使集合增加一个元素并且不影响答案。于是接下来的证明分成两部分。

1. 如果集合中不含 $0$

假设这个集合中的元素为 $a_1<a_2<\dots<a_k<0<a_{k+1}<a_{k+2}<\dots<a_n$。

于是，我们发现下面这个巨大的式子：

$$\begin{aligned} 0>&a_k>a_{k-1}>\dots>a_1\\ >&a_1+a_k>a_1+a_{k-1}>\dots>a_1+a_2\\ >&a_1+a_2+a_k>a_1+a_2+a_{k-1}>\dots>a_1+a_2+a_3\\ \vdots\\ >&a_1+a_2+\dots+a_k \end{aligned} $$

其中，第一行有 $k$ 个数（不包括 $0$），第二行有 $k-1$ 个数，最后一行有 $1$ 个数。

因此，至少有 $k+(k-1)+\dots+1=\frac{k(k+1)}2$ 种不同的负结果。

同理，至少有 $\frac{(n-k)(n-k+1)}2$ 种不同的正结果。

因此答案至少为 $\frac{k(k+1)+(n-k)(n-k+1)}2=\frac{2k^2+n^2-2nk+n}2$。

容易发现在 $k$ 取 $\lfloor \frac n2\rfloor$ 或 $\lceil\frac n2\rceil$ 时答案最小。

2. 如果集合中含 $0$

假设这个集合中元素为 $a_1<a_2<\dots<a_{k-1}<a_k=0<a_{k+1}<a_{k+2}<\dots<a_n$。

类似于上面的情况，至少有 $\frac{k(k-1)}2$ 种负结果和 $\frac{(n-k)(n-k+1)}2$ 种正结果，以及 $0$。

于是答案为 $\frac{k(k-1)+(n-k)(n-k+1)}2+1=\frac{2k^2-2k+n^2-2nk+n}2+1$。

此时 $k=\lfloor\frac{n+1}2\rfloor$ 或 $\lceil\frac{n+1}2\rceil$ 时答案最小。

比较上下两个式子，容易发现不含 $0$ 比含 $0$ 大了 $k-1$，而根据题目条件以及最小取值 $k$ 至少为 $1$，因此含 $0$ 比不含 $0$ 要更不劣。

这样我们不仅证明完了含 $0$ 更不劣，也顺便证明出了理论的最小值。

构造上面已经说过了，证明时也说明了取最小值的情况。

int n;
cin>>n;
for(int i=1;i<=n;i++)cout<<(i&1?-i/2:i/2)<<" ";
cout<<"\n";