「有趣的构造」 [Codeforces 1017C] The Phone Number

· · 题解

感觉这题就是十分的牛。

给定一个数 n 。求构造一个长度为 n 的排列，使之 \rm LIS+LDS 最小。

一开始读题读成了最大值。然后随便画了画发现答案就是 n+1 emmm

然后读完了随便写了个奇怪的东西被轻松叉了，之后发现原来是个比较强的题。大概就是考虑 dilworth 定理，最长上升/下降子序列长度等于其反链的最多序列数。那么考虑如果是要算 LIS+LDS 之和的话，对于一个 LIS 的定长 L ，根据 dilworth 定理必然会存在 L 个反链，也就是 L 个 DS 。于是可以知道最后有

{\rm LIS+LDS}=\left\lceil \frac{n}{L}\right\rceil+L

即为了使 L 个 DS 的最大长度最小，所以要尽量分的平均一点。那么可以知道这个 L 应该取 \sqrt n 。

那么之后就变成了如何构造一个 LIS 为 \sqrt n，LDS 为 \left\lceil\dfrac{n}{\sqrt n}\right\rceil 的串。不难知道可以分段构造。

#include <cmath>
#include <cstdio>
#include <algorithm>

const int N = 300010 ;

int n, m ;
int ans[N] ;

int main(){
    scanf("%d", &n) ;
    m = std :: ceil(std :: sqrt(n)) ;
    /*
    if (n & 1){
        ans[(n >> 1) + 1] = n ;
        for (int i = 1 ; i <= n >> 1 ; ++ i) ans[i] = i ;
        for (int i = (n >> 1) + 2 ; i <= n ; ++ i) ans[i] = n - i + ((n >> 1) + 1) ;
    }
    else {
        for (int i = 1 ; i <= (n >> 1) ; ++ i) ans[i] = i ;
        for (int i = (n >> 1) + 1 ; i <= n ; ++ i) ans[i] = n - i + ((n >> 1) + 1) ;
    }
    for (int i = 1 ; i <= n >> 1 ; ++ i) res[i] = ans[i + (n >> 1)] ;
    for (int i = (n >> 1) + 1 ; i <= n ; ++ i) res[i] = ans[i - (n >> 1)] ;*/
    int p = 0, q, k = n ;
    for (int i = 1 ; i <= std :: ceil(1.0 * n / m) ; ++ i){
        q = p ; for (int j = 1 ; j <= m && p < n ; ++ j) ans[++ p] = k -- ;
        std :: reverse(ans + q + 1, ans + p + 1) ; // printf("%d %d %d\n", i, q + 1, p) ;
    }
    for (int i = 1 ; i <= n ; ++ i)
        printf("%d ", ans[i]) ; return 0 ;
}