构造题

正如题目所说，这是一道构造题。

不算是很好想（主要是我太蒟了）

接下来说说我是怎么一步一步想到的吧。

首先先简述一下题意：构造一个长度为 $nn$ 的数组，下标从 $00$ 到 $n-1n-1$ , $a_{i}a\_i$ 代表 $ii$ 在数组中出现次数

首先，一共有 $nn$ 个数，所以 $a_0+a_1+\dots =na\_0+a\_1+\dots \; =\; n$ 。

其次，这个数组中必定有 0 ，如果没有 0 ，$a_0=0a\_0\; =\; 0$， 这就矛盾了。

还能发现性质： 最后一个数必定是 0， 如果不为零，说明剩下的都是 $n-1n-1$ 这就坏事了。

接下来还有什么能做的？ 我实在是不知道怎么搞了，那就举例子， 这是构造题，我们要找规律

先看4：

$a_i:a\_i:$1 2 1 0

$a_{i}a\_i$ 最后一个肯定是 0， 那么 $a_0\ge 1a\_0\ge 1$ 咱们先填上 1， 那么 $a_{1}a\_1$ 我们不得不填2， 紧接着 $a_{2}a\_2$ 填1（这样恰好耦合，先暂时不要考虑其他情况，反正他就叫我们构造正确的解法就行嘛）

再看5：

$a_i:a\_i:$2 1 2 0 0

好家伙，不是很熟悉的样子啊

再看6：

这个构造不出来

有自闭吗？ 但是放弃就算输。

再看7：

$a_i:a\_i:$? ? ? ? ? ? 0

先把最后一个填上 0，考虑第一个，假设我们填上 1

$a_i:a\_i:$1 ? ? ? ? ? 0

紧接着第二位、第三位就能确定下来了

$a_i:a\_i:$1 2 1 ? ? ? 0

剩下的三个问号有点难搞。因为前三位数已经稳定下来了，两个1一个2

等等， 只要是两个1一个2 那么数组的第2、3位就好安排，至于开头的 1 ，移动到哪里"无关紧要"（不要移动到最后一个）

那么， 到底移到哪里合适呢？ 那我们就得看 $a_{0}a\_0$ 的定义了：0 在这个数组中出现的次数。 现在我们有了两个1一个2， 开头第一位（不为0）， 那么我们能不能让剩下的都为0呢

即 $a_0=n-4a\_0=n-4$, $a_1=2a\_1\; =\; 2$, $a_2=1a\_2=1$, 由于$a_0=n-4a\_0=n-4$，那么另外那个 1 理所当然就放在第 $n-3n-3$ 位，剩下的全部是 0

把这些数字加起来刚刚好等于 $nn$， 这是必然的，因为0的数量是 $n-4n-4$ 而剩下的相加恰好是4。

而且这么安排我们既把第2、3位照顾好了，还把剩下的归零了省去了后续的麻烦。

同时，这也说明了当 $n\ge 7n\ge 7$ 时按照我们的构造方法，一定有解。

那么特判掉 1 2 3 4 5 6，剩下的就好说了。

上代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    if(n<4) cout << -1;
    else if(n==4) cout << "1 2 1 0";
    else if(n==5) cout << "2 1 2 0 0";
    else if(n==6) cout << -1;
    else
    {
        cout << n-4 <<" 2 1 ";
        for(int i=1;i<=n-7;i++) cout << "0 ";
        cout << "1 0 0 0";
    }
    return 0;
}