这是一道签到题
s4CRIF1CbUbbL3AtIAly
·
·
题解
题意：\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";