#P18607. Most Annoying Constructive Problem
Most Annoying Constructive Problem
Most Annoying Constructive Problem
一个整数序列的逆序对,是满足i<j且ai>aj的下标对。如果逆序对个数为奇数,称这个序列为奇序列,否则称为偶序列。
给出n和k,请构造1到n的一个排列,使它恰好有k个奇序列子数组;不存在时说明无解。子数组必须是连续区间,不能任意删除中间元素;长度为1的子数组逆序对为0,不属于奇序列。
输入格式
第一行测试用例数t,1<=t<=10000。
每组一行,给出n、k,1<=n<=1000,0<=k<=n(n-1)/2。所有用例的n²之和不超过4000000。
输出格式
每组无解时输出NO。有解时输出YES,下一行输出n个整数,构成1到n的排列,且奇序列子数组数量恰为k。存在多个合法排列时可以输出任意一个。
样例输入 1
4
1 0
3 3
4 1
6 15
样例输出 1
YES
1
YES
3 2 1
YES
1 3 4 2
NO
样例说明
第一组排列(1)没有奇子数组。第二组(3,2,1)的两个长度2区间和整个长度3区间均为奇,共3个。第三组(1,3,4,2)只有(4,2)是奇子数组。第四组可以证明无解。