Solution Of P11277 世界沉睡童话

Solution

好神秘的题。

我们不妨设 a_1 \le a_2 \le a_3 \le \dots \le a_n，这样题面所述条件可以转化为恰好存在 k 对 (i, j)，使得 i < j,a_i\text{\textbar} a_j。

我们先看到 k=0，令 a_1 = n, a_2 = n + 1, \dots, a_n = 2n - 1 秒了。

我们又看到这个 k < n - 1 的部分分，注意到如果把 k < n - 1 的情况做出来，那么就做完了。因为对于 k \ge n - 1，我们只要在 a 中加入一个 1，我们就可以产生 n - 1 的贡献，那么我们将 k\leftarrow k - n + 1，n \leftarrow n - 1，然后继续迭代，直到化为 k < n - 1 为止，然后按照这个部分分来构造就好了。

接下来解决部分分。我们注意到 \frac{(3 - 1) \times 3}{2}，这意味着如果存在 i 使得 a_i=a_{i + 1}=a_{i + 2},a_i \neq a_{i-1},a_{i + 2}\neq a_{i + 3}，那么这三个数能产生三个贡献，也就意味着这三个数每个数恰好产生一个贡献。这就很好了，因为这样可以让我们非常方便地去凑出 k，具体地，我们一直用三个相等的数去凑，为了避免交叉产生贡献一开始我们令 p = 2n - 1，然后让连续的三个 a_i=a_{i + 1}=a_{i + 2} = p，p\leftarrow p - 1，k\leftarrow k - 3，一直到 k < 3 为止，剩下的我们就 2 个 2 个地凑，这样 2 个数产生一个贡献，注意到 k < n - 1 因此 n 一定够用。然后就可以了。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
namespace AC {
    void Solve () {
        while (k >= n - 1 && n) k -= (n - 1), n --, cout << 1 << ' ';
        int p = 2 * n - 1, f = 0;
        for (int i = 1; i <= k / 3; i ++, p --)
            for (int j = 1; j <= 3; j ++) cout << p << ' ', f ++;
        for (int i = 1; i <= k % 3; i ++, p --, f += 2) cout << p << ' ' << p << ' ';
        for (int i = f + 1; i <= n; i ++, p --) cout << p << ' ';
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> k;
    AC::Solve ();
    return 0;
}