A. 排序

题目描述

输入格式

输出格式

一行，一个整数，表示可以将数组A从小到大排序的不同的操作序列的个数。

样例

样例输入

3

7 8 5 6 1 2 4 3

样例输出

数据范围与提示

对于30%的数据，1<=N<=4；对于全部的数据，1<=N<=12。

一个伪装成计数题的大搜索…

首先要知道一个结论：对于一个操作序列，如果他是合法的，那么他的全排列都是合法的，所以从小到大搜索，同时记录操作数k。

对于第x次操作，把序列分成2^x-1段，暴力搜索有几段不满足a[i]=a[i-1]+1(注意这里并不只是要求满足递增)，如果大于两段，显然无解;

如果没有，则第x操作无需进行（即对答案无贡献），直接向下递归即可，因为如果此时进行第x次操作，会将顺序打乱，之后的操作并不能使之还原。

如果有1段，则将这一段从中间断开，暴力交换，如果仍不满足则无解，满足则继续向下递归，k++;

如果有2端，则有四种情况，暴力交换向下递归即可，注意回溯时要还原。

结束条件：a[i]=i，答案为k！（即A（k，k））;

不过这题看起来复杂度好高啊，居然能跑的这么快…

#include<iostream>

#include<cstdio>

#include<cmath>

#define LL long long

using namespace std;

int n,m=1;

int a[5010];

LL jc[15];

bool end()

{

	for(int i=1;i<=m;i++)if(a[i]!=i)return 0;return 1;

}

void swapp(int l1,int r1,int l2,int r2)

{

	for(int i=l1,j=0;i<=r1;i++,j++)

		swap(a[i],a[l2+j]);

}

LL dfs(int x,int k)

{

	if(end())return jc[k];

	int len=pow(2,x),num=pow(2,n-x),te=0;

	int pd=0,d1=0,d2=0;

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

		for(int j=(i-1)*len+2;j<=i*len;j++)

			if(a[j]!=a[j-1]+1) pd++,d1?d2=i:d1=i;

	if(pd>2)return 0;

	if(!pd)return dfs(x+1,k);

	if(pd==1)

	{

		int l=(d1-1)*len+1,r=(d1)*len;bool pp=0;LL res=0;

		swapp(l,(l+r)>>1,(l+r)/2+1,r);

		for(int i=l+1;i<=r;i++)

			if(a[i]<a[i-1]){pp=1;break;}

		if(!pp)res=dfs(x+1,k+1);

		swapp(l,(l+r)>>1,(l+r)/2+1,r);

		return res;

	}

	if(pd==2)

	{

		int l1=(d1-1)*len+1,r1=(d1)*len,l2=(d2-1)*len+1,r2=(d2)*len;

		int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1;

		LL res=0;

		swapp(l1,mid1,l2,mid2);

		{

			int pp=0;

			for(int i=l1+1;i<=r1;i++)

				if(a[i]<a[i-1]){pp=1;break;}

			for(int i=l2+1;i<=r2;i++)

				if(a[i]<a[i-1]||pp){pp=1;break;}

			if(!pp) res+=dfs(x+1,k+1);

		}

		swapp(l1,mid1,l2,mid2);

		swapp(l1,mid1,mid2+1,r2);

		{

			int pp=0;

			for(int i=l1+1;i<=r1;i++)

				if(a[i]<a[i-1]){pp=1;break;}

			for(int i=l2+1;i<=r2;i++)

				if(a[i]<a[i-1]||pp){pp=1;break;}

			if(!pp) res+=dfs(x+1,k+1);

		}

		swapp(l1,mid1,mid2+1,r2);

		swapp(mid1+1,r1,l2,mid2);

		{

			int pp=0;

			for(int i=l1+1;i<=r1;i++)

				if(a[i]<a[i-1]){pp=1;break;}

			for(int i=l2+1;i<=r2;i++)

				if(a[i]<a[i-1]||pp){pp=1;break;}

			if(!pp) res+=dfs(x+1,k+1);

		}

		swapp(mid1+1,r1,l2,mid2);

		swapp(mid1+1,r1,mid2+1,r2);

		{

			int pp=0;

			for(int i=l1+1;i<=r1;i++)

				if(a[i]<a[i-1]){pp=1;break;}

			for(int i=l2+1;i<=r2;i++)

				if(a[i]<a[i-1]||pp){pp=1;break;}

			if(!pp) res+=dfs(x+1,k+1);

		}

		swapp(mid1+1,r1,mid2+1,r2);

		return res;

	}

}

inline int read()

{

	int s=0;char a=getchar();

	while(a<'0'||a>'9')a=getchar();

	while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}

	return s;

}

signed main()

{

//	freopen("in.txt","r",stdin);

	n=read();for(int i=1;i<=n;i++)m*=2;

	for(int i=1;i<=m;i++)a[i]=read();

	jc[0]=1;for(int i=1;i<=12;i++)jc[i]=jc[i-1]*i;

	printf("%lld\n",dfs(0,0));

}

巴特西

【SDOI2015】bzoj3990 排序