自动搬运

查看原文

来自洛谷，原作者为

	xh39 **

搬运于2025-08-24 22:32:31，当前版本为作者最后更新于2021-08-18 06:14:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注:文中所有 $/$ 符号表示整除。设 $a$ 表示所求排列。

从简单情况入手，一步步推，找规律。

如何确定 $1$ 的位置?

由于 $1$ 是最小的数，所以任何包含 $1$ 的区间最小值都是 $1$。

因此，在 $S_{(n+1)/2}$ 的集合中出现个数可以作为1的位置。如下图:

如上图第 $n=4$ 的例子，查询长度为 $2$ 的区间。若 $1$ 在位置 $0,3$ 则重复出现 $1$ 次，在位置 $1,2$ 则出现 $2$ 次。

如上图 $n=5$ 的例子，查询长度为 $3$ 的区间。若 $1$ 在位置 $0,1,2,3,4$，则出现次数依次为 $1,2,3,2,1$ 。

如上图 $n=7$ 的例子，查询长度为 $4$ 的区间。若 $1$ 在位置 $0,1,2,3,4$，则出现次数依次为 $1,2,3,3,2,1$ 。

则出现次数为 $b$ ， 那么 $a[b+1]=a[n-b-1]=1$ 。

由与选取 $n-b-1$ 的位置就是选取 $b+1$ 的位置倒过来，所以实质上无影响。本篇题解默认选取 $b+1$ 位置。

如何确定 $2$ 的位置?

此时麻烦一些，因为包含 $2$ 的区间最小值可能是 $1$ 或 $2$ 。

由于出现了 $1$ 的区间最小值只可能是 $1$ 。所以选完 $1$ 以后，$1$ 的左右裂成了两个部分。所以判断到底是在哪个部分。然后就用之前的方法求解。

如何判断区间内是否有解?设区间长度为 $size$，则 $S_{size}$ 中一定出现了 $1$ 次最小值。而 $S_{size+1}$ 中一定没有出现最小值。所以就判断 $S_{size}$ 中 $2$ 的出现次数。

若两部分内都有解，此时两部分长度相等，那么选取任意一部分都是等价的，本题解选取左部分。

确定完部分就与选取 $1$ 时用同样的方法。

如何选取更多的数?(实现)

$2$ 又可以将排列划分，现在有了 $3$ 个部分。那么选取 $3$ 也是一样的操作。但以上步骤不好直接模拟。因为不能快速找到区间。复杂度会超。

假设当前要选取 $i$。考虑用一个链表记录当前已经确定了的数 1~$(i-1)$。同时记录这个数选取的位置 $id$。这样区间就是 [当前.id+1,下一个.id-1]。

这样一来，插入操作，查找操作都方便了很多。就可以在 $O(n^2)$ 的复杂度内出解。

参考代码

#include<iostream>
using namespace std;
struct i_am_aking_ioi{
	int id,next;
}_[1000005]; //链表。
int mark[1005][1005]; //mark[i][j]:长度为i的区间(S[i])内出现了几次j。 
int main(){
	int n,i,j,A,ykb;
	cin>>n;
	for(i=1;i<=n;i++){
		for(j=i;j<=n;j++){
			scanf("%d"，&A);
			mark[i][A]++;
		}
	}
	_[0].next=n+1;
	_[0].id=-1;
	_[n+1].id=n; //初始化不能漏，一开始的区间是[0,n-1]，由于区间是[now.id+1,next.id-1]，所以要一开始要设为-1和n。
	for(i=1;i<=n;i++){ //依次插入1~n 
		for(j=0;j<=n;j=_[j].next){ //在每个区间内查找。  
			ykb=_[_[j].next].id-_[j].id; //区间长度
			if(!mark[ykb][i]&&mark[ykb-1][i]){
				_[i].id=_[j].id+mark[ykb+1>>1][i];//这个区间时从now.id+1开始编号的。所以需要加上_[j].id。同时+1-1抵消。
				_[i].next=_[j].next;
				_[j].next=i;
				break; //已经找到，不需要再找。因为多个可行区间任选一个。
			}
		}
	}
	for(i=_[0].next;i<=n;i=_[i].next){
		cout<<i<<" ";
	}
	return 0;
}

月赛过去了这么久都没有题解。于是就写一篇。