BZOJ 3990 排序

【题目描述】：

小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]。

【输入格式】

第一行，一个整数N。

第二行，2^N个整数，A[1]、A[2]…A[2^N]。

【输出格式】

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

【样例输入】

7 8 5 6 1 2 4 3

【样例输出】

【数据规模和约定】

对于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%算法：

上面我们已经知道了这条性质，那么下面的问题就是如何找到这样的一组操作

我们从短的区间2ⁱ枚举，如果有一段长度为2ⁱ⁺¹的序列并不是公差为1的递增区间，我们就记录一下，

如果这样的区间大于两段，直接return就好。

如果没有。。。你啥都做不了，接着搜下一段长度的区间

如果只有一段，段内直接交换即可

如果有两段，那么需要判断4种情况进行dfs

这四种情况是：前一段的前一段和后一段的前一段，前一段的后一段和后一段的前一段，前一段的前一段和后一段的后一段，前一段的后一段和后一段的前一段。

感谢barca友情提供

废话不说，上代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define ll long long

 using namespace std;

 ll n,a[<<],js[],m,ans=;

 bool judge(ll l,ll r){

     for(ll i=l;i<r;i++)

         if(a[i+]!=a[i]+)

             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=,temp[],p=<<x+;

     for(ll i=;i<=m;i+=p){

         if(judge(i,i+p-)) continue;

         temp[++sum]=i;

         if(sum==) return ;

     }

     if(sum>) return ;

     if(!sum){

         dfs(x+,y);

         return ;

     }

     if(sum==){

         change(temp[sum],temp[sum]+(<<x),<<x);

         if(judge(temp[sum],temp[sum]+p-)) dfs(x+,y+);

         change(temp[sum],temp[sum]+(<<x),<<x);

         return ;

     }

     if(sum==){

         change(temp[sum-],temp[sum],<<x);

         if(judge(temp[sum-],temp[sum-]+p-)&&judge(temp[sum],temp[sum]+p-))

             dfs(x+,y+);

         change(temp[sum-],temp[sum],<<x);

         change(temp[sum-],temp[sum]+(<<x),<<x);

         if(judge(temp[sum-],temp[sum-]+p-)&&judge(temp[sum],temp[sum]+p-))

         dfs(x+,y+);

         change(temp[sum-],temp[sum]+(<<x),<<x);

         change(temp[sum-]+(<<x),temp[sum],<<x);

         if(judge(temp[sum-],temp[sum-]+p-)&&judge(temp[sum],temp[sum]+p-))

             dfs(x+,y+);

         change(temp[sum-]+(<<x),temp[sum],<<x);

         change(temp[sum-]+(<<x),temp[sum]+(<<x),<<x);

         if(judge(temp[sum-],temp[sum-]+p-)&&judge(temp[sum],temp[sum]+p-))

             dfs(x+,y+);

         change(temp[sum-]+(<<x),temp[sum]+(<<x),<<x);

     }

 }

 int main(){

     scanf("%lld",&n);

     js[]=,m=<<n;

     for(ll i=;i<=n;i++)

         js[i]=js[i-]*i;

     for(ll i=;i<=m;i++)

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

     dfs(,);

     printf("%lld\n",ans);

     return ;

 }

巴特西

BZOJ 3990 排序

最新文章

热门文章