[BZOJ3990]:[SDOI2015]排序（搜索）

题目传送门

题目描述

小A有一个1-${2}^{N}$的排列A[1..${2}^{N}$],他希望将A数组从小到大排序,小A可以执行的操作有N种,每种操作最多可以执行一次,对于所有的i(1≤i≤N),第i中操作为将序列从左到右划分为${2}^{N-i+1}$段,每段恰好包括${2}^{i-1}$个数,然后整体交换其中两段.小A想知道可以将数组A从小到大排序的不同的操作序列有多少个,小A认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同).
下面是一个操作事例:
N=3,A[1..8]=[3,6,1,2,7,8,5,4].
第一次操作,执行第3种操作,交换A[1..4]和A[5..8],交换后的A[1..8]为[7,8,5,4,3,6,1,2].
第二次操作,执行第1种操作,交换A[3]和A[5],交换后的A[1..8]为[7,8,3,4,5,6,1,2].
第三次操作,执行第2中操作,交换A[1..2]和A[7..8],交换后的A[1..8]为[1,2,3,4,5,6,7,8].

有关题目描述的说明

说实话，一开始真没看懂题。

其实，大致意思就是说，每次把序列分成${2}^{N-i+1}$个长度为${2}^{i-1}$的块，每次可以选择其中两块交换。

需要注意的两点就是：

　　1.每种操作只能使用一次。

　　2.不是说所有长度为2^(i-1)的都行，举个例子：假设长度为2，那么每一块就是{1,2},{3,4},{5,6},……，而{2,3},{4,5}则不是。

输入格式

第一行，一个整数N

第二行，${2}^{N}$个整数，A[1..${2}^{N}$]

输出格式

一个整数表示答案

样例

样例输入：

7 8 5 6 1 2 4 3

样例输出：

数据范围与提示

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

题解

这道题居然是搜索，简直难以置信，没办法，那就搜吧。

数据范围1≤N≤12，算一算发现是4096->5000，下意识${N}^{2}$。

首先，我们来考虑这样一个问题，如果我们执行的操作是3，1，2能完成排序，那么1，2，3也一定能，那么就是说，如果我们找到了一种操作数为x的方案，那么它对答案的贡献就是x！。

然后，再来考虑，因为每一种操作只能执行一次，所以这时候分以下四种情况：

　　1.没有长度为2^(i-1)的不符合顺序的序列对，那么直接尝试下一种操作。例：每一块的长度为4，序列为{1,3,2,4,5,6,7,8}，{3,2}虽然不符合顺序，当前操作不能对它进行操作，那么我们执行下一个操作。

　　2.存在一个这样的序列对，那么我们尝试进行内部交换。

　　3.存在两个这样的序列对，例如：每一块的长度为2，序列为{1,2,7,8,5,6,3,4}，那么我们需要枚举四种情况，分别是{1,2}与{5,6}换，{1,2}与{3,4}换，{7,8}与{5,6}换，{7,8}与{3,4}换。

　　4.如果存在多于两个这样的序列对，那么这种方案一定行不通，赶快return就好了。

交换的时候暴力swap即可。

最后，大家可能还是毫无头绪，那么我再来解释一个问题。

我们在进行搜索的时候要从小往大搜索，因为这样，我们在交换两个长度更长的序列的时候已经保证了它里面是有序的，然后如果往后的操作可以将当前可以完成当前操作也可以完成的排序，那么就交给以后处理，例：当前每一块的为1，序列为{7,8,5,6,1,2,4,3}，我们发现{7,8}和{5,6}在以后的操作中可以完成交换，那么我们现在就只尝试交换{4,3}。

统计答案时，将每一种方案的答案累加即可。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,sum,miao;

int jc[13];

int ans;

int a[4097];

void change(int x,int y,int w){do swap(a[x+w],a[y+w]);while(w--);}//暴力swap

void dfs(int x,int w)

{

	if(x==miao)//所有操作都已经尝试过了

	{

		ans+=jc[w];//记着加的是阶乘

		return;

	}

    int cnt=0;

    int flag[2]={0,0};//一定要是局部变量，100->25

    int wzc=1<<x;//记算长度

	for(int i=1;i<=n;i+=(wzc<<1))//统计位置，(wzc<<1)即为自动越过下一种操作可以处理掉的情况

	{

		if(a[i+wzc-1]+1!=a[i+wzc])

		{

			if(cnt==2)return;//如果两个以上就return

			flag[cnt++]=i;

		}

	}

	switch(cnt)

	{

		case 0://不存在

		{

			dfs(x+1,w);

			return;

		}

		case 1://存在一对

		{

			change(flag[0],flag[0]+wzc,wzc-1);

			dfs(x+1,w+1);

			change(flag[0],flag[0]+wzc,wzc-1);

			return;

		}

		case 2://存在两对，再分四种情况

		{

			if(a[flag[0]+wzc-1]+1==a[flag[1]+wzc]&&a[flag[0]+wzc]==a[flag[1]+wzc-1]+1)//先看看交换之后符不符合

			{

				change(flag[0],flag[1],wzc-1);

				dfs(x+1,w+1);

				change(flag[0],flag[1],wzc-1);

				change(flag[0]+wzc,flag[1]+wzc,wzc-1);

				dfs(x+1,w+1);

				change(flag[0]+wzc,flag[1]+wzc,wzc-1);

			}

			if(a[flag[0]+wzc]-1==a[flag[1]+wzc*2-1]&&a[flag[0]]==a[flag[1]+wzc-1]+1)

			{

				change(flag[0],flag[1]+wzc,wzc-1);

				dfs(x+1,w+1);

				change(flag[0],flag[1]+wzc,wzc-1);

			}

			if(a[flag[1]+wzc]-1==a[flag[0]+wzc*2-1]&&a[flag[1]]==a[flag[0]+wzc-1]+1)

			{

				change(flag[0]+wzc,flag[1],wzc-1);

				dfs(x+1,w+1);

				change(flag[0]+wzc,flag[1],wzc-1);

			}

			return;

		}

	}

}

int main()

{

	scanf("%d",&n);

	miao=n;

	jc[0]=1;

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

		jc[i]=jc[i-1]*i;//预处理阶乘

	n=1<<n;//现在n变为了序列长度了

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

		scanf("%d",&a[i]);

	dfs(0,0);//开搜

	cout<<ans<<endl;

	return 0;

}

rp++

巴特西