P13786 题解

· · 题解

Problem Link

首先假设 p=[1,\dots,n]，则 a=\mathrm{LIS}(q),b=\mathrm{LIS}(r)。

通过 a=1,c=n 的部分分可以猜测合法条件为 abc\ge n,a+b\le c+n 及其轮换形式。

首先 a+b\le c+n 较显然，因为长度为 a,b 的 \mathrm{LIS} 至少有长为 a+b-n 的 \mathrm{LCS}。

然后考虑 abc<n 时的情况，首先 \mathrm{LDS}(q)\ge \dfrac na\ge bc+1，考虑 \mathrm{LDS}(q) 中元素在 r 中出现的顺序 t， \mathrm{LIS}(t)\le \mathrm{LCS}(q,r)=c，其次 \mathrm{LDS}(t)\le \mathrm{LIS}(r)=b，那么 \mathrm{LIS}(t)\times\mathrm{LDS }(t)< |t|，这显然是不可能的。

考虑 n=abc 时的构造，考虑在 \mathrm{LIS},\mathrm{LDS} 一定时 n 尽可能大的经典构造：若干值域递减的上升序列和若干值域递增的下降序列。

那么直接运用之，q 为 bc 个长度为 a 的上升序列，r 为 b 个长度为 ac 的下降序列，则 r\circ q^{-1} 为 c 个值域递增的长度为 b 的下降序列值域递减地重复 a 次，此时 \mathrm{LCS}(q,r)=a 合法。

注意到我们只要取出三个排列中值为 [1,2,\dots,a],[1,ac+1,2ac+1,\dots,(b-1)ac+1],[1,a+1,2a+1,\dots,(c-1)a+1] 的元素构成的子序列（即 p,q,r 之间的 \mathrm{LCS} 中元素），此时得到 a+b+c-1 个元素的排列，如果 n>a+b+c-1，随便选一些剩下的元素放进去即可。

那么只要考虑 n\le a+b+c-2 的情况，如果 (a-1)(b-1)(c-1)\ge n-1，则求 (n-1,a-1,b-1,c-1) 的解然后在末尾插入 n 即可。

否则 (a-1)(b-1)(c-1)<n-1，容易发现此时必有 a-1=b-1=1，即 a=b=2,c=n-1，在 q,r=[n,n-1,\dots,1] 的基础上交换 (q_1,q_2),(r_1,r_3) 即可。

那么我们就给出了所有 (n,a,b,c) 的构造方法。

时间复杂度 \mathcal O(n\log n)。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
void solve() {
    ll n,a,b,c,ty,m;
    cin>>n>>a>>b>>c>>ty,m=n;
    if(a*b*c<n||a+b>c+n||a+c>b+n||b+c>a+n) return cout<<"No\n",void();
    cout<<"Yes\n";
    if(!ty) return ;
    int k=0;
    for(;n&&(a-1)*(b-1)*(c-1)>=n-1;++k,--a,--b,--c,--n);
    basic_string <int> B,C;
    if(!n);
    else if(a+b+c-2>n) {
        for(int i=n-1;~i;--i) B+=i,C+=i;
        swap(B[0],B[1]),swap(C[1],C[2]);
    } else {
        map <ll,int> X;
        vector <array<ll,2>> Y,Z;
        auto ins=[&](ll x) { X[x]=0,Y.push_back({-(x/a),x}),Z.push_back({x/a/c,-x}); };
        ins(0);
        for(int i=1;i<a;++i) ins(i);
        for(int i=1;i<b;++i) ins(a*c*i);
        for(int i=1;i<c;++i) ins(a*i);
        for(int i=0;i<n&&(int)X.size()<n;++i) if(!X.count(i)) ins(i);
        sort(Y.begin(),Y.end()),sort(Z.begin(),Z.end());
        int t=0;
        for(auto &o:X) o.second=t++;
        for(auto o:Y) B+=X[o[1]];
        for(auto o:Z) C+=X[-o[1]];
    }
    for(int i=n;i<m;++i) B+=i,C+=i;
    for(int i=0;i<m;++i) cout<<i+1<<" \n"[i==m-1];
    for(int i=0;i<m;++i) cout<<B[i]+1<<" \n"[i==m-1];
    for(int i=0;i<m;++i) cout<<C[i]+1<<" \n"[i==m-1];
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int _; cin>>_;
    while(_--) solve();
    return 0;
}