Luogu

分析

根据题目里提供的证明，不难得到答案的下界是 $n-1$。下面我们来考虑如何构造出这个下界。

考虑拿出 $n-1$ 组匹配，满足两两无交，这样子每组匹配中的边只会有一条被经过，组内直接赋连续权值即可。

这 $n-1$ 组匹配可以把下面这个图旋转 $n-1$ 次得到

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10;

int n,p[N],G[N][N];

int main() {
    n=read();
    for (int i=1;i<=n;++i) p[i]=n-i+1;
    for (int c=2,w=0;c<=n;++c) {
        for (int i=1;i<=n;++i)
            if (!G[i][p[i]]) G[i][p[i]]=G[p[i]][i]=++w;
        for (int i=1;i<=n;++i) {
            if (i==c) { p[i]=n; continue; }
            if (i==n) { p[i]=c; continue; }
            if (p[i]==n) p[i]=(i+1)%(n-1)+1;
            else p[i]=(p[i]+1)%(n-1)+1;
        }
    }
    for (int i=1;i<n;++i)
        for (int j=i+1;j<=n;++j)
            printf("%d%c",G[i][j]," \n"[j==n]);
    return 0;
}