序列(seq)

序列(seq)

题目描述

给定 N,A,BN,A,B，构造一个长度为 NN 的排列，使得：

排列长度为 N；

最长上升子序列长度为 A；

最长下降子序列长度为 B。

我们有 SPJ，有解任意给出一组，否则说明无解。

输入

第一行一个整数 TT (1≤T≤101≤T≤10), 表示数据组数.

接下来 T 行，每行三个正整数 N、A、B。

输出

对每组数据：

如果有解， 输出两行 ，第一行一个字符串 Yes，接下来一行 N 个整数，表示排列。

否则， 输出一行一个字符串 No。

样例输入

3

4 2 2

4 4 1

4 3 3

样例输出

Yes

3 4 1 2

Yes

1 2 3 4

 No

提示

数据范围和子任务

对于全部的测试数据，保证 T≤10,N≤105,∑N≤2×105T≤10,N≤105,∑N≤2×105

子任务 1（20 分）：N≤5N≤5 .

子任务 2（30 分）：每组数据均满足 N=A×BN=A×B .

子任务 3（20 分）：B≤2B≤2 .

子任务 4（30 分）：无特殊限制

---

solution

先考虑a*b=n的情况怎么做：连续构造a段下降的b

比如 n=6 a=3 b=2

->      2 1 4 3 6 5

那么如果a>n/b 呢

就把某些段改成升序的

由于每一段之间互不影响，所以这不会改变b的答案

那么n！=a*b 也只是多了一段小段的而已

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 100005

using namespace std;

int T,n,a,b,ans[maxn],num[maxn];

void init(){

    for(int i=1;i<=n;i++)ans[i]=num[i]=0;

}

int main()

{

    freopen("seq.in","r",stdin);

    freopen("seq.out","w",stdout);

    cin>>T;

    while(T--){

        scanf("%d%d%d",&n,&a,&b);init();

        if(a+b>n+1){puts("No");continue;}

        for(int i=1;i<=n;i+=b){

            int top=i+b-1;top=min(top,n);num[i]=top-i+1;

            for(int j=top,x=0;j>=i;j--,x++)ans[j]=i+x;

        }

        int tmp=n/b;if(n%b)tmp++;

        if(tmp>a){puts("No");continue;}

        int tp=a-tmp,i=b+1;

        while(tp){

            if(tp>=num[i]-1){

                for(int j=i;j<=i+num[i]-1;j++)ans[j]=j;

                tp-=num[i]-1;i=i+b;

            }

            else {

                for(int j=i;j<=i+tp-1;j++)ans[j]=j;

                for(int j=i+num[i]-1,x=tp;j>=i+tp;j--,x++)ans[j]=i+x;

                tp=0;

            }

        }

        puts("Yes");

        for(int i=1;i<=n;i++)cout<<ans[i]<<' ';cout<<endl;

    }

    return 0;

}