Wannafly Camp 2020 Day 2H 叁佰爱抠的序列

转化为完全图的欧拉遍历

如果 n 是奇数，则欧拉遍历长度为 \(n(n-1)/2\) 条边

如果 n 是偶数，则欧拉遍历长度为 \(n*n/2-1\) 条边

（即将(n-1)/2对点配对，剩下的一对当起点终点）

点数则 +1

答案是单调的所以二分

至于输出，暴力跑欧拉回路即可

眼瞎不开ll

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,m;

const int N = 4005;

vector <pair<int,int> > g[N];

int vis[N*N],ind;

vector <int> sta;

void make(int p,int q,int r) {

    g[p].push_back(make_pair(q,r));

    g[q].push_back(make_pair(p,r));

}

void dfs(int p) {

    for(pair<int,int> pr:g[p]) {

        int q=pr.first, w=pr.second;

        if(!vis[w]) {

            vis[w]=1;

            dfs(q);

        }

    }

    sta.push_back(p);

}

signed main() {

    cin>>n;

    int l=1,r=3ll*sqrt(n)+1; //!!!

    while(l<r) {

        int mid=(l+r)/2,tmp=0;

        if(mid&1) tmp=mid*(mid-1)/2+1;

        else tmp=mid*mid/2;

        if(tmp>n) r=mid;

        else l=mid+1;

    }

    m=l-1;

    printf("%lld\n",m);

    if(n>2000000) return 0;

    for(int i=1;i<=m;i++) {

        for(int j=1;j<i;j++) {

            make(i,j,++ind);

        }

    }

    if(m%2==0) {

        for(int i=3;i<=m;i+=2) {

            make(i,i+1,++ind);

        }

    }

    dfs(1);

    for(int i=0;i<sta.size();i++) {

        printf("%lld%s",sta[i],i==n-1?"":" ");

    }

    for(int i=sta.size();i<n;i++) printf("1%s",i==n-1?"":" ");

    puts("");

}

巴特西

Wannafly Camp 2020 Day 2H 叁佰爱抠的序列 - 欧拉遍历

最新文章

热门文章