【2023NOI模拟赛08】排序 做题记录

罗曼诺夫发明了一种新的排序方法，所以决定用它来出道题。给定一个排列，这个排序算法会执行以下步骤：

1. 从排列的开头开始，判断每一对相邻的数是否大小关系正确；
2. 如果存在相邻的一对数大小关系不正确：
   1. 把较小的那个数丢到排列开头；
   2. 回到步骤一；
3. 排列有序了，结束；

比如一个排序过程是

$4,1,3,2\to1,4,3,2\to3,1,4,2\to1,3,4,2\to2,1,3,4\to1,2,3,4$

$4,1,3,2\to1,4,3,2\to3,1,4,2\to1,3,4,2\to2,1,3,4\to1,2,3,4$

对于排列 $p$ ，设 $F(p)$ 表示把 $p$ 排序会需要进行多少次步骤二。比如 $F(\{4,1,3,2\})=5$。

类似字符串，可以定义两个排列（允许长度不同）的字典序比较。

给定 $K$ ，求字典序最小的排列 $p$，使得 $F(p)=K$ 。可以证明解必定存在。

$1\le K\le 10^{18}$。

不难发现排序的过程是从前往后依次把每一个前缀排序，那么每个前缀都可以归纳为这样的形式：

1 2 3 4 5 6 7 ... n+1 n

设这样的序列的操作次数为 $f(n)$，那么有：

$\begin{cases} f(1)=1\\ f(n)=1+\sum\limits_{i=2}^{n-1}f(i-1) \end{cases}$

易得 $f(n)=2^{n-1}$。

接下来开个栈构造即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=1005,BS=62;

int ta,tb,a[S],b[S];

int main()
{
	freopen("sorting.in","r",stdin);
	freopen("sorting.out","w",stdout);
	long long n;
	scanf("%lld",&n);
	int id=0;
	long long m=n;
	for(int i=0;m>0;i++)
	{
		if(n>>i&1)
		{
			b[++tb]=++id;
			a[++ta]=++id;
			m-=1ll<<i;
		}
		else
		{
			while(tb>0&&ta<=i) a[++ta]=b[tb--];
			if(tb==0&&ta<=i) a[++ta]=++id;
		}
	}
	for(int i=1;i<=ta;i++) printf("%d ",a[i]);
	for(int i=tb;i>=1;i--) printf("%d ",b[i]);
	printf("\n");
	return 0;
}