Codeforces Round 949 D. Turtle and Multiplication 【欧拉路径】

题意

要求构造一个长度为 $n$ 的序列 $a$，使得：

• $\forall i\in [1,n],1\le a_i\le 3\cdot 10^5$
• $\forall 1\le i<j\le n-1,a_i\cdot a_{i+1}\ne a_j\cdot a_{j+1}$
  要求最终序列中数字的种类最少

思路

不难发现，所有的数字选用质数一定最优，因为这样可以保证：$a_i\cdot a_{i+1}=a_j\cdot a_{j+1}\iff (a_i,a_{i+1})=(a_j,a_{j+1})$

那么我们只需要保证每一对无序对 $(a_i,a_{i+1})$ 均不同即可。

这里可以建模成一张图：以每一个值为顶点，边表示无序对（即相邻的数），每一个点还有一个自环（表示 $(a_i,a_i)$这样的无序对）

那么问题就转化为了，我们要选择最少的顶点数量，使得 无向完全图 中存在一条长度至少为 $n-1$，且不经过重复边的路径。

如果图上点数已经确定，考虑如何计算最长欧拉路径的长度：

1. 如果 $n$ 是奇数，那么每个点的度数是 $n-1+2=n+1$ 为偶数，存在欧拉回路，因此最长欧拉路径的长度即为：$C_n^2+n=\frac{(n+1)\cdot n}{2}$
2. 如果 $n$ 是偶数，那么每个点的度数就是奇数了，我们要考虑如何删去最少的边，使得图上恰好剩余 $2$ 个奇度顶点，这样子就存在最长的欧拉路径；观察发现：删去一条边最多可以影响 $2$ 个点的度数，因此保留两个奇度顶点最少需要删除：$\frac{n-2}{2}$ 条边。我们可以删除 $(2,3),(4,5),...,(n-2,n-1)$ 这些边，这样子 $1$ 号点就是奇度顶点，我们可以直接从 $1$ 开始 $dfs$

最后我们只需要二分找到边数足够的 $n$，在上面跑一个欧拉路径即可

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

std::vector<int> minp;
std::vector<int> primes;

void sieve(int n){
    minp.assign(n + 5, 0);
    primes.clear();

    fore(i, 2, n + 1){
        if(!minp[i]){
            minp[i] = i;
            primes.push_back(i);
        }
        for(auto p : primes){
            if(p * i > n) break;
            minp[i * p] = p;
            if(minp[i] == p) break;
        }
    }
}

const int N = 2000005;

std::vector<int> stk;
bool vis[N];
std::vector<std::pair<int, int>> g[10005];

void dfs(int u){
    for(auto [v, id] : g[u])
        if(!vis[id]){
            vis[id] = true;
            dfs(v);
        }
    stk.push_back(primes[u]);
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    sieve(N);

    int t;
    std::cin >> t;
    while(t--){
        int n;
        std::cin >> n;

        auto check = [](int x, int n) -> bool {
            if(x & 1) return x * (x - 1) / 2 + x >= n - 1;
            return x * (x - 1) / 2 - (x - 2) / 2 + x >= n - 1;
        };

        int num = 0;
        int l = 1, r = 10000;
        while(l <= r){
            int mid = l + r >> 1;
            if(check(mid, n)){
                num = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }

        fore(u, 0, num) g[u].clear();

        int tot = 0;
        fore(i, 0, num)
            fore(j, i, num){
                if(num % 2 == 0 && (i & 1) && j == i + 1) continue; //偶数个点时，去掉一些边构造欧拉路径
                g[i].push_back({j, ++tot});
                g[j].push_back({i, tot});
            }
        
        fore(i, 0, tot + 1) vis[i] = false;
        stk.clear();
        dfs(0);
        std::reverse(ALL(stk));

        fore(i, 0, n) std::cout << stk[i] << " \n"[i == n -1];
    }

    return 0;
}
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98