题解：P16952 「LAOI-18」口約束

GreenMelon · 2026-10-22 15:02:48 · 题解

水绿，我这种菜瓜都能做出来。

首先 n\bmod 3\not= 2 时必定无解，这个不难想到。

然后考虑不同的情况，对于所有长度为 3 的区间：

• 区间 \text{mex} 值为 1 时，要使相邻三个元素都是 0；
• 区间 \text{mex} 值为 0 时，要使相邻三个元素都是 1；
• 区间 \text{mex} 值为 2 时，要使相邻三个元素中至少有一个是 1。

这些也不难想到。

第一种情况直接输出 \cfrac{n-2}{3}+2 个 0。第二种情况直接输出 \cfrac{n-2}{3}+2 个 1，第三种情况较为复杂。因为前面有 2 个长度为 3 的区间 0 和 1 同时存在，所以要输出 \cfrac{n-2}{3} 个 0 或 1。因为当前后面的位置也会和前面的 1 重叠，所以为了 1 尽可能少，最开始输出的两个数为 0，接着是 1，那么就是 0,0,1 地输出。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    if (n % 3 != 2 || n < 8) {
        cout << -1 << '\n';
        return ;
    }
    else {
        for (int i = 1; i <= n / 3 + 2; i ++) cout << "0 ";
        for (int i = 1; i <= n / 3 + 2; i ++) cout << "1 ";
        for (int i = 3; i <= n / 3; i ++) {
            if (i % 3 == 2) cout << "1 ";
            else cout << "0 ";
        }
        cout << '\n';
    }
}

int main() {
    int T;
    cin >> T;
    while (T --) solve();
}