【题目描述】：
小A有一个1~2N的排列A[1..2N]，他希望将数组A从小到大排序。小A可以执行的操作有N种，每种操作最多可以执行一次。对于所有的i(1<=i<=N)，第i种操作为：将序列从左到右划分成2N-i+1段，每段恰好包含2i-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]。
【输入格式】
第一行，一个整数N。
第二行，2N个整数，A[1]、A[2]…A[2N]。
【输出格式】
一行，一个整数，表示可以将数组A从小到大排序的不同的操作序列的个数。
【样例输入】
3
7 8 5 6 1 2 4 3
【样例输出】
6
【数据规模和约定】
对于30%的数据，1<=N<=4；
对于全部的数据，1<=N<=12。
题解：
15%算法：输出阶乘。
这个代码就不发了，应该没有人不会打阶乘。
这是一个非常迷的东西，为什么输出阶乘能得分呢？首先我们发现，如果已经找到了一种交换方法，那么我们任意交换其中的操作，这样也能得到最终的序列
证明的话，一下摘自某大佬博客：
假设我现在第一次换a，b ，第二次换c，d 且a比c长
那么cd完全被包含和完全无交集肯定不影响。
现在假设c被a包含，d和b分开
那么可以把操作c~d改为操作 (c在b种对应位置)~d
所以会有一个阶乘。如果你看出来了，这很方便你qj测试点。
当然我们练习时需要打正解，下面是100%算法：
上面我们已经知道了这条性质，那么下面的问题就是如何找到这样的一组操作
我们从短的区间2i枚举，如果有一段长度为2i+1的序列并不是公差为1的递增区间，我们就记录一下，
如果这样的区间大于两段，直接return就好。
如果没有。。。你啥都做不了，接着搜下一段长度的区间
如果只有一段，段内直接交换即可
如果有两段，那么需要判断4种情况进行dfs
这四种情况是：前一段的前一段和后一段的前一段，前一段的后一段和后一段的前一段，前一段的前一段和后一段的后一段，前一段的后一段和后一段的前一段。
感谢barca友情提供
废话不说，上代码：
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; ll n,a[1<<13],js[13],m,ans=0; bool judge(ll l,ll r){ for(ll i=l;i<r;i++) if(a[i+1]!=a[i]+1) return false; return true; } void change(ll x,ll y,ll l){ for(ll i=x,j=y;l;l--,i++,j++) swap(a[i],a[j]); } void dfs(ll x,ll y){ if(x==n){ ans+=js[y]; return ; } ll sum=0,temp[5],p=1<<x+1; for(ll i=1;i<=m;i+=p){ if(judge(i,i+p-1)) continue; temp[++sum]=i; if(sum==3) return ; } if(sum>3) return ; if(!sum){ dfs(x+1,y); return ; } if(sum==1){ change(temp[sum],temp[sum]+(1<<x),1<<x); if(judge(temp[sum],temp[sum]+p-1)) dfs(x+1,y+1); change(temp[sum],temp[sum]+(1<<x),1<<x); return ; } if(sum==2){ change(temp[sum-1],temp[sum],1<<x); if(judge(temp[sum-1],temp[sum-1]+p-1)&&judge(temp[sum],temp[sum]+p-1)) dfs(x+1,y+1); change(temp[sum-1],temp[sum],1<<x); change(temp[sum-1],temp[sum]+(1<<x),1<<x); if(judge(temp[sum-1],temp[sum-1]+p-1)&&judge(temp[sum],temp[sum]+p-1)) dfs(x+1,y+1); change(temp[sum-1],temp[sum]+(1<<x),1<<x); change(temp[sum-1]+(1<<x),temp[sum],1<<x); if(judge(temp[sum-1],temp[sum-1]+p-1)&&judge(temp[sum],temp[sum]+p-1)) dfs(x+1,y+1); change(temp[sum-1]+(1<<x),temp[sum],1<<x); change(temp[sum-1]+(1<<x),temp[sum]+(1<<x),1<<x); if(judge(temp[sum-1],temp[sum-1]+p-1)&&judge(temp[sum],temp[sum]+p-1)) dfs(x+1,y+1); change(temp[sum-1]+(1<<x),temp[sum]+(1<<x),1<<x); } } int main(){ scanf("%lld",&n); js[0]=1,m=1<<n; for(ll i=1;i<=n;i++) js[i]=js[i-1]*i; for(ll i=1;i<=m;i++) scanf("%lld",&a[i]); dfs(0,0); printf("%lld\n",ans); return 0; }
转载于:https://www.cnblogs.com/Juve/p/11158274.html
