题目来源: 2020 CCPC Wannafly 冬令营 Day2: H. 叁佰爱抠的序列

题面

现有一个整数 \(m\), 构造了一个长度为 \(n\) 的序列 \(A\), 满足: 1. \(\forall a \in A,\, a\in[1,m]\cap\mathbb Z\) 2. \(\forall x,y\in[1,m]\cap\mathbb Z,\,x\ne y\), \(\exists p\in[1,n)\cap\mathbb Z\), s.t. \(\{A[p],A[p+1]\}=\{x,y\}\)

其中 \(A[p]\) 表示 \(A\) 中的第 \(p\) 个元素的值.

给定一个 \(n\), 求 \(m\) 可能的最大值. 若 \(n\leq N=2\cdot10^6\), 则再输出 \(m\) 取得最大值时可能的一个序列 \(A\).

数据范围

\[ 1\leq n\leq10^{18} \]

题解

构造一个 \(m\) 个顶点的无向图 \(\boldsymbol G\), \(\forall p\in [1,n)\), 在 \(A[p]\) 和 \(A[p+1]\) 之间连一条边, 记作第一类边. 则 \(A\) 的条件 \((2)\) 就转化成了 \(\boldsymbol G\) 中任意两个不同点都要有边直接连接, 最多有 \(n-1\) 条边. 这样, 我们就得到了 \(n\) 的一个下界: \[ n\geq\frac{1}{2}m(m-1)+1 \tag{3} \] 等号成立当且仅当任意两个不同点之间直接连接的边有且仅有 \(1\) 条.

另一方面, 观察这些连接的边: \[ A[1]\rightarrow A[2]\rightarrow A[3]\rightarrow...\rightarrow A[n] \] 考虑从 \(A[1]\) 号点出发, 按照上述顺序遍历整个图, 发现每条边经过且只经过了一次, 这对应了一个欧拉回路, 于是 \(\boldsymbol G\) 中至多两个点的度数为奇数. 反过来, 如果 \(\boldsymbol G\) 中至多两个点的度数为奇数, 那么可以构造出这样一个欧拉回路以及对应的序列.

考虑以上两个要素: 任意两个不同点之间直接连接的边有且仅有一条时, 每个点的度数是 \(m-1\).

如果 \(m\) 是奇数, 那么每个点的度数全部都是偶数, 故可以构造出一个序列 \(A\). \((3)\) 式等号可以成立.

如果 \(m\) 是偶数, 那么每个点的度数全部都是奇数, \(m>2\) 时不能构造出一个欧拉回路. 这时, 我们可以任取 \(m-2\) 个度数为奇数的点, 配对连边, 记作第二类边. 于是这 \(m-2\) 个点度数均加 \(1\), 变为了偶数. 这样 \(G\) 中只有 \(2\) 个点度数为奇数, 可以构造欧拉回路. 此时有:

\[ n\geq\frac{1}{2}m(m-1)+1+\frac{1}{2}(m-2)=\frac{1}{2}m^2 \] 综上所述, 定义: \[ f(m):=\left\{ \begin{align} \frac{1}{2}m(&m-1)+1 & m\equiv 0\pmod 2\\ \frac{1}{2}&m^2 & m\equiv 1\pmod 2 \end{align}\right. \]

条件便可以总结为: \[ n\geq f(m) \tag4 \]

我们可以从 \(1\) 到 \(n\) 枚举所有可能的 \(m\), 取其中满足 \(n\geq f(m)\) 的最大值. 复杂度为 \(O(n)\), 不能接受.

注意到: \(\forall m\equiv 0\pmod 2\), \(\displaystyle \frac{1}{2}(m-1)(m-2)+1<\frac{1}{2}m^2<\frac{1}{2}m(m+1)+1\). 即: \(\forall m\in\mathbb N_+\), \(f(m)<f(m+1)\). \(f\) 严格单调增, 故可以使用二分查找, 复杂度为 \(O(\log n)\), 可以接受.

也可以分别解不等式: \[ \begin{align} \frac{1}{2}x(x-1)+1&\le n \tag5\\ \frac{1}{2}x^2&\le n \tag6 \end{align} \] 取不等式 \((4)\) 解中最大的奇数和不等式 \((5)\) 解中最大的偶数的较大者, 复杂度为 \(O(1)\). 很好.

现在思考一种 \(\forall m\in\mathbb N_+\) 都能构造欧拉回路以及对应的序列 \(A\) 的方法. 先考虑 \(n=f(m)\) 的情况, 这种情况构造的序列记作 \(A_m\), 此时 \(A=A_m\).

对于 \(m\) 是奇数的情况, 考虑数学归纳法:

一、\(m=1\) 时, 由于没有边, 欧拉环路显然存在, \(A_1=[1]\).

二、设我们构造出了 \(m=k\) 时的图的欧拉环路以及对应的序列 \(A_k\). 显然, 欧拉环路可以从任意一个点出发, 遍历一遍图后回到起点. \(A[1]\) 可以是任意一个数, \(A[n]=A[1]\). 不妨令 \(A[1]=A[n]=1\). 现在我们加入两个点 \(k+1,k+2\). 考虑序列 \(B=[2,3,...,k]\), 在 \(B\) 中所有的奇数前面插入 \(k+1\), 后面插入 \(k+2\), 则 \(B=[2,k+1,3,k+2,...,k+1,k,k+2]\). 令 \(A_{k+2}=[A_k,k+1,k+2,B,1]\). 这样, \(m=k+2\) 时的序列以及对应的欧拉回路就构造好了.

对于 \(m\) 时偶数的情况, 考虑数学归纳法:

一、\(m=2\) 时, 由于只有一条边, 欧拉环路显然存在, \(A_2=[1,2]\).

二、设我们构造出了 \(m=k\) 时的图的欧拉环路以及对应的序列 \(A_k\). 显然, 欧拉环路应该从一个度数为奇数的点出发, 遍历一遍图后回到另一个度数为奇数的点. \(A[1],A[n]\) 可以是任意两个不同的数, 不妨令 \(A[1]=1,A[n]=k\). 现在我们加入两个点 \(k+1,k+2\). 将 \(k,k+1\) 配对连接第二类边. 考虑序列 \(B=[2,3,...,k]\), 在 \(B\) 中所有的奇数前面插入 \(k+1\), 后面插入 \(k+2\), 则 \(B=[2,k+1,3,k+2,...,k+1,k,k+2]\). 令 \(A_{k+2}=[A_k,k+1,k+2,B]\). 这样, \(m=k+2\) 时的序列以及对应的欧拉回路就构造好了.

当然, 这个构造只是一种构造. 其他的任何满足题意的构造均可行.

现在考虑 \(n>f(m)\) 的情况. 很显然, 令 \(A=[A_m,\underbrace{1,1,...,1}_{n-f(m)}]\) 即可.

构造复杂度为 \(O(N)\). 可以接受.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get(ll m)
{
    if (m & 1)
        return (m * (m - 1) >> 1) + 1;
    return m * m >> 1;
}
bool check(ll m, ll n)
{
    return get(m) <= n;
}
ll rget(ll n, ll l, ll r)
{
    if (l + 1 == r)
        return l;
    ll mid = l + r >> 1;
    if (check(mid, n))
        return rget(n, mid, r);
    return rget(n, l, mid);
}
void opt(ll m)
{
    if (m & 1)
    {
        printf("1");
        int o = 1, n = 1;
        for (int i = 2; i < m; i += 2)
        {
            printf(" %d", i);
            n = i;
            do
            {
                o = o % (i - 1) + 1;
                n = n == i ? i + 1 : i;
                printf(" %d %d", n, o);
            } while (o != 1 || n != i + 1);
        }
    }
    else
    {
        printf("1 2");
        int o = 2, n = 1;
        for (int i = 3; i < m; i += 2)
        {
            printf(" %d", i);
            n = i;
            do
            {
                o = o % (i - 1) + 1;
                n = n == i ? i + 1 : i;
                printf(" %d %d", n, o);
            } while (o != i - 1 || n != i);
            printf(" %d", o = i + 1);
        }
    }
}
int main()
{
    ll n;
    scanf("%lld", &n);
    ll m = rget(n, 0, 2e9);
    printf("%lld\n", m);
    if (n <= 2e6)
    {
        opt(m);
        for (int i = get(m); i < n; ++i)
            printf(" 1");
    }
    return 0;
}