Codeforces 1097E. Egor and an RPG game 构造

时间：2023-12-12 14:59:26

原文链接https://www.cnblogs.com/zhouzhendong/p/CF1097E.html

题解

首先我们求出 $k = f(n) = \max\{x|\frac{x(x+1)}2\leq n\}$ 。

具体构造方案是：（以 $n = 15$ 为例）

11 12 13 14 15          7 8 9 10        4 5 6        2 3       1

我们考虑如何构造。

求出当前序列的 LIS 长度（假设为 $len$）。如果 $len\geq k$ ，那么直接取出这个LIS，把问题转化成更小规模的问题： $n^\prime = n-len\leq n-k$ 而且 $k^\prime \leq k-1$ 。

否则由dilworth引理得到一定可以把序列分成 $len$ 个递减序列。考虑按照以每一个点为结尾的上升序列长度将所有分组，对于同一组的按顺序连起来，这样得到 $len$ 组就好了。证明的比较简单：如果不是递减的，那么后一个的值至少是前一个+1，他们的就不会被分到同一组。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL read(){

	LL x=0;

	char ch=getchar();

	while (!isdigit(ch))

		ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return x;

}

const int N=100005;

int T,n,m;

int a[N],v[N],p[N],vis[N];

int f(int n){

	int ans=0;

	while (ans*(ans+1)<=n*2)

		ans++;

	return ans-1;

}

int c[N];

void Add(int x,int id){

	for (;x<=n;x+=x&-x)

		c[x]=v[c[x]]<v[id]?id:c[x];

}

int Ask(int x){

	int ans=0;

	for (;x;x-=x&-x)

		ans=v[ans]<v[c[x]]?c[x]:ans;

	return ans;

}

vector <vector <int> > ans;

vector <int> vec_empty;

void Main(){

	ans.clear();

	n=read();

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

		a[i]=read();

	m=n;

	while (m>0){

		int k=f(m);

//		cout<<"k="<<k<<endl;

		for (int i=0;i<=n;i++)

			c[i]=0;

		for (int i=1;i<=m;i++){

			vis[i]=0;

			p[i]=Ask(a[i]);

			v[i]=v[p[i]]+1;

			Add(a[i],i);

		}

		int tail=Ask(n),len=v[tail];

		if (len>k){

			ans.push_back(vec_empty);

			for (int i=tail;i;i=p[i])

				vis[i]=1,ans.back().push_back(a[i]);

			reverse(ans.back().begin(),ans.back().end());

			int _m=0;

			for (int i=1;i<=m;i++)

				if (!vis[i])

					a[++_m]=a[i];

			m=_m;

		}

		else {

			int c=(int)ans.size()-1;

			for (int i=1;i<=len;i++)

				ans.push_back(vec_empty);

			for (int i=1;i<=m;i++)

				ans[c+v[i]].push_back(a[i]);

			break;

		}

	}

	printf("%d\n",(int)ans.size());

	for (auto s : ans){

		printf("%d",(int)s.size());

		for (auto v : s)

			printf(" %d",v);

		puts("");

	}

}

int main(){

	T=read();

	while (T--)

		Main();

	return 0;

}

　　

相关文章