“蔚来杯“2022牛客暑期多校训练营2 G.[Link with Monotonic Subsequence] 分块构造

G. Link with Monotonic Subsequence 构造

题目分析

要求构造一个长度为$n$的序列，使得序列的$\max (\text{lis}(p),\text{lds}(p))$尽可能的小。

狄尔沃斯定理：对偏序集$<A，\le >$，设A中最长链的长度是$n$，则将$A$中元素分成不相交的反链，反链个数至少是$n$。

那么有$\text{lds}(p)=cnt(\text{lis(p)})$，那么显然$\max (\text{lis}(p),\text{lds}(p))\ge \max (k,\frac{k}{n})\ge \sqrt{n}$ 。因此直接构造$\sqrt{n}$个块即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;


inline void solve(){
    
    int n = 0; cin >> n;
    int b = ceil(sqrt(n));
    while(n > 0){
    
        for(int i = max(1ll, n - b + 1); i <= n; i++) cout << i << " ";
        n -= b;
    }
    cout << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}