F. 怎么写线性SPJ （2种解法）

打得比较着急，可能有奇怪的 typo

Update 1: 修复了把 4 处 min 打成 max 的 typo

Update 2: 修复了漏打了个 g 的 typo

Update 3: 修正了第 2 个解法的证明部分

本题解中数组 $p_n$ 的下标从 1 开始.

记满足条件的 $p_n$ 的最小"种类数"为 $f\left(n\right)$ . 初值 $f\left(0\right) = 0$ . 下面考虑对于正整数 $n$ 的 $f\left(n\right)$ .

$p_n$ 中一定有一个数只出现一次，设这个数的下标是 $m$ .

则

f\left(n\right) = \min_{1 \leq m \leq n}\left\{1 + \max\left\{f\left(m - 1\right), f\left(n - m\right)\right\}\right\}

记 $g\left(m\right) = 1 + \max\left\{f\left(m - 1\right), f\left(n - m\right)\right\}$ ，这里

g\left(m\right) = \begin{cases} 1 + f\left(n - m\right), m \leq \frac{n + 1}{2} \\ 1 + f\left(m - 1\right), m > \frac{n + 1}{2} \\ \end{cases}

因为 $f\left(n\right)$ 随 $n$ 的增加而单调不减（[不严格]单调增加），所以，如果 $n$ 为奇数，则

f\left(n\right) = \min_{1 \leq m \leq n} \left\{g\left(m\right)\right\} = g\left(\frac{n + 1}{2}\right)

如果 $n$ 为偶数，则

f\left(n\right) = \min_{1 \leq m \leq n} \left\{g\left(m\right)\right\} = \min\left\{g\left(\frac{n}{2}\right), g\left(\frac{n + 2}{2}\right)\right\} = g\left(\frac{n}{2}\right)

（这里 $\displaystyle g\left(\frac{n}{2}\right) = g\left(\frac{n + 2}{2}\right)$ ）

综上，

\begin{aligned} f\left(n\right) &= g\left(\lfloor \frac{n + 1}{2} \rfloor \right) \\ &= 1 + \max\left\{f\left(\lfloor \frac{n + 1}{2} \rfloor - 1\right), f\left(n - \lfloor \frac{n + 1}{2} \rfloor\right)\right\} \\ &= 1 + f\left(n - \lfloor \frac{n + 1}{2} \rfloor\right) \\ &= 1 + f\left(\lfloor \frac{n}{2} \rfloor\right) \\ \end{aligned}

结合 $f\left(0\right) = 0$ 和上面的递推公式，可得：对任意正整数 $n$ ，有 $f\left(n\right) = \lfloor \log_2 n\rfloor + 1 \leq n$ .

因此可以满足题目中 $1 \leq p_n \leq n$ 的要求.

因此我们可以取 $\displaystyle m = \lfloor \frac{n + 1}{2} \rfloor$ ，来构造一个最优解.

那么，我们写一个 DFS，把这个过程模拟出来就可以了.

DFS 构造解法

#include <iostream>
#include <vector>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> p(n + 1, 0);
    int cnt = 0;
    auto dfs = [&](auto& self, int l, int r, int v) -> void {
        if (l > r) {
            return;
        }
        // n = r - l + 1
        // m = l - 1 + floor((n + 1) / 2) = l - 1 + floor((r - l + 2) / 2) = floor((l + r) / 2)
        int m = (l + r) / 2;
        p[m] = v;
        cnt = std::max(cnt, v);
        self(self, l, m - 1, v + 1);
        self(self, m + 1, r, v + 1);
    };
    dfs(dfs, 1, n, 1);
    std::cout << cnt << "\n";
    for (int i = 1; i <= n; ++i) {
        std::cout << p[i] << " \n"[i == n];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

时间复杂度： $\mathcal O\left(n\right)$ .

空间复杂度： $\mathcal{O}\left(n\right)$ .

贪心构造解法

下面的代码来自于贪心构造. 显然它生成出的数组 $p_n$ 的"种类数"为 $\lfloor \log_2 n\rfloor + 1$ ，已经满足最小了，且 $1 \leq p_n \leq n$ ，只需要证明

数组的每一个非空连续子数组都存在至少一个“唯一元素”.

证明：只需要考察 $n = 2^k - 1$ （ $k$ 是正整数）的情况. 这是因为，即使 $n = n_0$ （ $n_0$ 是正整数）且 $n_0$ 无法这样表示，也可以找到正整数 $k$ 使得

n_0 < 2^k - 1

（只需要让 $k$ 足够大即可.）

根据代码的构造逻辑， $n = n_0$ 的数组是 $n = 2^k - 1$ 的数组的一个前缀（这当然是它的一个非空连续子数组），如果 $n = 2^k - 1$ 的情况得证，那么 $n = n_0$ 的情况也得证了.

接下来，使用数学归纳法证明，对任意正整数 $k$ ， $n = 2^k - 1$ 的数组的每一个非空连续子数组都存在至少一个“唯一元素”.

当 $k = 1$ 时， $n = 1$ ，对应的数组是 [1]，它的非空连续子数组只有它本身， $1$ 是这个数组的一个"唯一元素"，因此当 $k = 0$ 时命题成立.

假设当 $k = m$ （ $m$ 是正整数）时命题成立，那么当 $k = m + 1$ 时， $n = 2^{m + 1} - 1$ ，它的数组可以由这 3 部分拼接而成：

第 1 部分： $n = 2^m - 1$ 的数组

第 2 部分：[m + 1]

第 3 部分： $n = 2^m - 1$ 的数组

举个例子

当 $m = 4$ 时， $k = m + 1 = 5$ ， $n = 2^{m + 1} - 1 = 31$ ，对应的数组是
[1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]
它由下面部分组成：

第 1 部分：
[1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]
第 2 部分：
[5]
第 3 部分：
[1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]

因为当 $k = m$ 时命题成立，所以第 1 部分和第 3 部分的非空连续子数组都存在至少一个"唯一元素".

而第 2 部分的非空连续子数组只有它本身，也存在一个"唯一元素" $m + 1$ .

只需要考虑跨越多个部分的非空连续子数组. 而这样的非空连续子数组一定包含 $m + 1$ ，注意， $m + 1$ 的所有下标为

i_a = 2^m + a \cdot 2^{m + 1}

其中 $a$ 是非负整数.

显然 $i_a$ 不可能落在 $\left[0, 2^m - 1\right]$ 上，也不可能落在 $\left[2^m + 1, 2^{m + 1} - 1\right]$ 上，这是因为， $i_0 = 2^m$ 没有前一个下标，而后一个下标是

i_1 = 2^m + 2^{m + 1} > 2^{m+1} - 1

因此 $m + 1$ 是这个数组的一个"唯一元素".

因此当 $k = m + 1$ 时命题成立.

根据数学归纳法，原命题得证.

#include <iostream>
#include <vector>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> p(n + 1, 0);
    int v = 1, pos = 1, d = 2;
    while (pos <= n) {
        for (int k = pos; k <= n; k += d) {
            p[k] = v;
        }
        v = v + 1;
        pos = pos * 2;
        d = d * 2;
    }
    std::cout << (v - 1) << "\n";
    for (int i = 1; i <= n; ++i) {
        std::cout << p[i] << " \n"[i == n];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

时间复杂度： $\mathcal O\left(n\right)$ .

空间复杂度： $\mathcal{O}\left(n\right)$ .

贪心构造解法和 DFS 构造解法得到的数组 $p_n$ 不相同，但都符合题意.

题解 | #F. 怎么写线性SPJ （2种解法）#

F. 怎么写线性SPJ （2种解法）

DFS 构造解法

贪心构造解法