题目连接
叁佰爱抠的序列
题解
在2e6范围内，需要输出答案，大于2e6的时候则不用，因为答案单调，所以考虑二分答案。
为奇数时，奇数点的完全图的度全为偶数，则存在欧拉路径所以$res=mid(mid-1)/2 + 1$加1是因为序列第一位和最后一位不算相邻。
为偶数的时候不难发现为$res=midmid/2$
二分出m之后，打印答案也需要考虑，如果完全图不能够画出欧拉路径，那么考虑加边，一开始考虑剪边，如果这样的话会导致一些情况下需要的序列长度增加，考虑加边的情况，在中间选取相邻的两个点加边，头和尾不用加，例如1,2,3,4,5,6那么就选择(2,3)(4,5)这样之后，1，6的度就为奇数，其他的为偶数，存在欧拉路径。然后跑欧拉路径即可
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e3+10;
int cnt;
int ip;
struct edge{
int to,next,id;
}grp[N*N];
bool vis[N*N];
int head[N*N];
vector<int>S;
ll getm(ll n){
ll l=1,r=2e9+10;
while(l<r){
ll mid = (l+r)>>1;
ll res = mid&1? mid*(mid-1)/2+1:mid*mid/2;
if(n<res)r=mid;
else l=mid+1;
}
return l-1;
}
void add(int u,int v,int id){
grp[cnt].to=v;
grp[cnt].next=head[u];
grp[cnt].id=id;
head[u]=cnt++;
grp[cnt].to=u;
grp[cnt].next=head[v];
grp[cnt].id=id;
head[v]=cnt++;
}
void dfs(int u){
for(int i=head[u];~i;i=head[u]){
head[u]=grp[i].next;
if(vis[grp[i].id])continue;
vis[grp[i].id]=1;
dfs(grp[i].to);
}
S.push_back(u);
}
int main(){
memset(head,-1,sizeof(head));
ll n;
scanf("%lld",&n);
if(n>2e6){
printf("%lld\n",getm(n));
}
else{
ll x = getm(n);
for(int i=1;i<=x;i++){
for(int j=i+1;j<=x;j++){
add(i,j,++ip);
}
}
printf("%lld\n",x);
if(x%2==0){
for(int i=2;i+1<=x-1;i+=2){
add(i,i+1,++ip);
}
}
dfs(1);
for(int i=0;i<S.size();i++){
cout<<S[i];
if(i!=n-1)cout<<" ";
}
for(int i = S.size(); i < n; i++)
printf(" 1");
puts("");
}
}
|