题解：P10306 「Cfz Round 2」How to Prove

szh_AK_all · 2024-04-04 19:49:45 · 题解

分析

既然我们要让 \Omega(S) 中的元素尽可能少，不妨让 S 的所有的非空子集的元素和所组成的可重集合中的相同元素尽可能多。

首先考虑让两个元素之和尽可能重复的构造方案。

很显然，我们将元素两两分组，最多会有 \lfloor n\div 2 \rfloor 组两两元素之和相同。为了方便起见，可以让每组的元素都互为相反数。

那么在这种构造下，多个元素之和重复的数量也是最多的，我们可以将两两分组的元素合并成一个元素，那么合并的这些元素，便都为 0。所以这种构造是最优的。

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            cout << ans << " ";
            if (ans == 0 || ans < 0)
                ans = -ans + 1;
            else
                ans = -ans;
        }
        cout << endl;
    }
}