AFO

题解 P5419 【[CTSC2016]单调上升序列】

2020-11-17 22:29:06


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

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

这 $n-1$ 组匹配可以把下面这个图旋转 $n-1$ 次得到(图是蒯的 mrsrz 的,侵删)

图片是蒯的 mrsrz 的

// ====================================
//   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;
}