ARC091E

Angraecum · 2024-03-09 16:51:35 · 题解

模拟赛的时候考了这个题，但是脑子是糊的，挂了五个点……

分享一个很暴力的想法，很适合我这种没有思维没有智慧的人，还有感性理解这个做法会容易一些。

我们就看 5 3 2 这组样例，能很自然地构造出这样一个序列：3 4 5 1 2。从这个序列的形态入手，我们可以把它分成 3 4 5 和 1 2，相当于是把序列分成前面一个连续的上升子段，后面一个上升子段。

也许这样不太明显，再来一组样例 8 3 3，按照上面的思路可以构造出序列 6 7 8,3 4 5,1 2（逗号是我加的），相当于将三个上升子段拼起来，并且这三个上升子段的值是逐渐下降的，也满足了下降子序列长度的限制。当然也可以反过来这样：3 2 1 6 5 4 8 7。

那么我们珂以取 a,b 中的较大值来将序列分段，令 a 为较大者，并且先忽略最后一段（还有很多注意的点），那么可以分出 \lfloor \frac{(n-1)}{a}\rfloor 段，记为前 k 段，每一段都是值逐渐减小的上升子段。

然后我们发现，很多情况下最后一段为上升子段时都不能满足下降子序列长度的限制。我们可以这样构造最后一段：设最后一段长度为 len，len=n-k\times a。现在我们需要最后一段对前 k 段中的最长下降子序列的贡献为 b-k，如果 b-k\le len，那么直接将最后一段分成对最长下降子序列长度的贡献为 k 的前一段和对最长下降子序列长度没有贡献的后一段。具体而言，对于样例 8 4 3，可以构造出序列 5 6 7 8,2 1 3 4，最后一段中 1 2 使得最长下降子序列长度变为 3，3 4 则无贡献。可以理解为是将 1 2 3 4 改成了 2 1 3 4。

但是 b-k>len 时只改变最后一段是不够满足长度需求的，我们再去考虑修改倒数第二段。以 11 5 4 为例，正确的构造方案应是 7 8 9 10 11 3 2 4 5 6 1，就直接把最后一段的构造方法搬到倒数第二段来了，而且最多也只会修改到倒数第二段。

无解情况就是 a+b>n+1 或 a\times b<n 其他题解有详细讲解，不再赘述。

由于是赛时脑子一团糊写的代码，所以非常复杂，对 a,b 还分类讨论了，甚至可能还有点纰漏，建议看看就好。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2*114514,M=1919810;
ll n,a,b;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>a>>b;
    if(a*b<n||a+b>=n+2){
        cout<<-1;
        return 0;
    }
    ll mx=max(a,b),mn=min(a,b);
    ll k=(n-1)/mx;
    if(a>b){
        if(b==1){
            if(a==n){
                for(int i=1;i<=n;++i) cout<<i<<" ";
                return 0;
            }
            else cout<<-1;
            return 0;
        }
        ll lim=n-k*a;
        if(lim<b-k){
            for(int j=1;j<k;++j)
                for(int i=n-j*a+1;i<=n-(j-1)*a;++i)
                    cout<<i<<" ";
            for(int i=n-k*a+1;i<=n-(k-1)*a-(b-1-lim);++i) cout<<i<<" ";
            for(int i=n-(k-1)*a;i>=n-(k-1)*a-(b-1-lim)+1;--i) cout<<i<<" ";
            for(int i=lim;i>=1;--i) cout<<i<<" ";
            return 0;
        }
        for(int j=1;j<=k;++j)
            for(int i=n-j*a+1;i<=n-(j-1)*a;++i)
                cout<<i<<" ";
        for(int i=b-k;i>=1;--i) cout<<i<<" ";
        for(int i=b-k+1;i<=n-k*a;++i) cout<<i<<" ";
    }
    else{
        if(a==1){
            if(b==n){
                for(int i=n;i>=1;--i) cout<<i<<" ";
                return 0;
            }
            else cout<<-1;
            return 0;
        }
        ll lim=n-k*b;
        if(lim<a-k){
            for(int j=1;j<k;++j)
                for(int i=b*j;i>=(j-1)*b+1;--i)
                    cout<<i<<" ";
            for(int i=b*k-(a-k-lim);i<=b*k;++i) cout<<i<<" ";
            for(int i=b*k-(a-k-lim)-1;i>=b*(k-1)+1;--i) cout<<i<<" ";
            for(int i=n-lim+1;i<=n;++i) cout<<i<<" ";
            return 0;
        }
        for(int j=1;j<=k;++j)
            for(int i=b*j;i>=(j-1)*b+1;--i)
                cout<<i<<" ";
        for(int i=b*k+1;i<=b*k+(a-k)-1;++i) cout<<i<<" ";
        for(int i=n;i>b*k+(a-k)-1;--i) cout<<i<<" ";
    }
    return 0;
}//99163 1000 1000