CF1981D 题解
EuphoricStar
·
·
题解
如果我们把 $(a_i, a_{i + 1})$ 看成一条边，那么问题变成找到点数最少的无向完全图（每个点还有一个自环），使得这个完全图存在一条经过 $n - 1$ 条边且不经过重复边的路径。
考虑若完全图点数确定，我们如何计算这个完全图的最长不经过重复边的路径长度。
设完全图点数为 $m$，若 $m$ 是奇数那么每个点的度数都是偶数，所以这个图存在欧拉路径，路径长度即为边数，其等于 $\frac{m(m + 1)}{2}$。
若 $m$ 是偶数那么每个点的度数都是奇数，我们需要删除一些边使得这个图存在欧拉路径。容易发现一条边最多使奇度数点的数量减少 $2$，所以我们至少需要删除 $\frac{m}{2} - 1$ 条边，删除 $(2, 3), (4, 5), \ldots, (m - 2, m - 1)$ 这些边即可，路径长度为 $\frac{m(m - 1)}{2} - \frac{m}{2} + 1 + m = \frac{m^2}{2} + 1$。
当 $n = 10^6$ 时最小的 $m$ 是 $1415$，第 $1415$ 小的质数是 $11807$，符合 $a_i \le 3 \cdot 10^5$。
我们可以二分求出最小的 $m$，使用 Hierholzer 算法求出一个无向图的欧拉路径。
时间复杂度：每个测试用例 $O(n)$。
```cpp
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 4000100;
const int N = 1000000;
int n, a[maxn], pr[maxn], tot, stk[maxn], top;
bool vis[maxn];
inline void init() {
for (int i = 2; i <= N; ++i) {
if (!vis[i]) {
pr[++tot] = i;
}
for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {
vis[i * pr[j]] = 1;
if (i % pr[j] == 0) {
break;
}
}
}
mems(vis, 0);
}
inline bool check(int x) {
if (x & 1) {
return x + 1 + x * (x - 1) / 2 >= n;
} else {
return x * (x - 1) / 2 - x / 2 + 2 + x >= n;
}
}
vector<pii> G[10000];
void dfs(int u) {
while (G[u].size()) {
pii p = G[u].back();
G[u].pop_back();
if (vis[p.scd]) {
continue;
}
vis[p.scd] = 1;
dfs(p.fst);
}
stk[++top] = pr[u];
}
void solve() {
scanf("%d", &n);
int l = 1, r = 10000, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
for (int i = 1; i <= ans; ++i) {
vector<pii>().swap(G[i]);
}
int tot = 0;
for (int i = 1; i <= ans; ++i) {
for (int j = i; j <= ans; ++j) {
if (ans % 2 == 0 && i % 2 == 0 && i + 1 == j) {
continue;
}
G[i].pb(j, ++tot);
G[j].pb(i, tot);
}
}
for (int i = 1; i <= tot; ++i) {
vis[i] = 0;
}
top = 0;
dfs(1);
reverse(stk + 1, stk + top + 1);
for (int i = 1; i <= n; ++i) {
printf("%d%c", stk[i], " \n"[i == n]);
}
}
int main() {
init();
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
```