「有趣的构造」 [Codeforces 1017C] The Phone Number
皎月半洒花
2020-06-16 21:28:28
感觉这题就是十分的牛。
> 给定一个数 $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$ 的串。不难知道可以分段构造。
```cpp
#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 ;
}
```
#