[BZOJ3990][SDOI2015][LOJ#2181]-排序

说实话，这个题真好（？）

<BZOJ题面>

<LOJ题面>

看到这个题，一时没有思路

但是

我想到了一个错解：归并

这个题真的有一点把我们的思路往归并上引

于是WA10

诶？我归并写错了

以下是正解

DFS

我们会发现，这个题的

每一种操作，只能有一个

好办了

因为大的交换区间（我们暂且这么叫它）无法处理更小区间上的错位

而且，大的区间交换会改变小的交换的位置，这样如果我们找到一种可行方案（含$N$个操作）

这个方案解的全排列都可行，对答案的贡献就是$N!$

（有序：依次+1，如{1,2,3}，其余情况无序）

所以DFS应从小往大进行，并且一边处理一边检测更小一段是否有序

处理完的区间必须有序，且每一次处理都不能超过一次

那么下面是处理的具体情况

发现在当前的区段，无序的有$k$个

$k=0$时，不需要交换（如果您非要交换那只能WA了）

$k=1$时，将无序区段整理有序

$k=2$时，将两段无序的区间进行整理，有四种情况，见下

$k \ge 3$时，当前操作无论如何也无法处理，返回

在此之下是过于仔细的讲解了，只看题解的可以停了~（下面约为源码）

将$k=2$时的情况讨论：

用几个式子举例

1.两个外侧交换

　　第一块的第一个子块与第二个的第一个子块相差$2^n$

　　7 8 3 4 5 6 1 2 可以交换

　　5 6 3 4 7 8 1 2 不行

2.两个内侧交换

　　第一块的第一个子块与第二个的第二个子块相差$2^n$

　　1 2 5 6 3 4 7 8 可以

　　1 2 7 8 3 4 5 6 不行

3.一内一外交换

　　第一块的第一个子块与第二个的第一个子块相差$2^n$

　　第4种情况归在这里面，同样的判断条件即

　　[1][3]交换[2][4]交换

　　1 2 5 6 3 4 7 8 可以

　　1 2 7 8 3 4 5 6 不行

总之记得把换过的判一下

源码：

其实以上判断用for循环都可以搞定，蒟蒻调出了if-else的正解

#include <iostream>

#include <cstring>

#include <cstdio>

//#include "debug.h"

#define LL long long

#define N (1<<12)+10

using namespace std;

int arr[N],dat[N];

int pown[15],fac[15];

int n;

LL ans=0;

LL jc(int n){

    LL j=1;

    for(int i=2;i<=n;i++){

        j*=i;

    }

    return j;

}

void sswap(int f1,int f2,int l){

    //cout<<f1<<"<->"<<f2<<" len:"<<l<<endl;

    for(int i=0;i<l;i++){

        dat[f1+i]=arr[f1+i];

        dat[f2+i]=arr[f2+i];

        arr[f1+i]=dat[f2+i];

        arr[f2+i]=dat[f1+i];

    }

}

bool is_ok(){

    for(int i=1;i<=pown[n];i++)

        if(arr[i]!=i)return 0;

    return 1;

}

void dfs(int k,int cn){//2^k

    //cout<<"DFS"<<k<<"change number:"<<cn<<endl;

    //debug<<"Now the array has been:"<<endl;

    //pour(arr,1,pown[n],3,"Array");

    if(is_ok()){

        if(cn!=0)ans+=fac[cn];

        return;

    }

    if(k>n)return ;

    int ln=0;

    for(int i=1;i<=pown[n];i+=pown[k]){

        if(arr[i+pown[k-1]]!=arr[i]+pown[k-1]){

            ln++;//cout<<"Find a Unordered part "<<i<<" Total: "<<ln<<endl;

        }

    }

    if(ln==0){

        dfs(k+1,cn);

    }

    else if(ln==1){

        for(int i=1;i<=pown[n];i+=pown[k]){

            if(arr[i+pown[k-1]]!=arr[i]+pown[k-1]){

                sswap(i,i+pown[k-1],pown[k-1]);

                dfs(k+1,cn+1);

                sswap(i,i+pown[k-1],pown[k-1]);

                break;

            }

        }

    }

    else if(ln==2){

        int wz[2];

        for(int i=1,j=0;i<=pown[n];i+=pown[k]){

            if(arr[i+pown[k-1]]!=arr[i]+pown[k-1]){

                wz[j]=i;

                j++;

                if(j==2)break;

            }

        }

        //debug<<"wz1 "<<wz[0]<<" wz2 "<<wz[1]<<" pown" <<pown[k-1]<<endl;

        //debug<<"init:"<<arr[wz[0]]<<" "<<arr[wz[1]]<<NL;

        if(arr[wz[0]]+pown[k-1] == arr[wz[1]]){//换中间的

            if(arr[wz[0]+pown[k-1]]+pown[k-1] != arr[wz[1]+pown[k-1]])//换后的后面

                return;

            sswap(wz[0]+pown[k-1],wz[1],pown[k-1]);

            dfs(k+1,cn+1);

            sswap(wz[0]+pown[k-1],wz[1],pown[k-1]);

        }

        else if(arr[wz[1]+pown[k-1]] + pown[k-1] == arr[wz[0]+pown[k-1]]){//换两边的

            if(arr[wz[1]]+pown[k-1] != arr[wz[0]])//换后的后面

                return ;

            sswap(wz[0],wz[1]+pown[k-1],pown[k-1]);

            dfs(k+1,cn+1);

            sswap(wz[0],wz[1]+pown[k-1],pown[k-1]);

        }

        else if(arr[wz[0]]+pown[k-1] == arr[wz[1]+pown[k-1]]){

            if(arr[wz[0]+pown[k-1]] != arr[wz[1]]+pown[k-1])//换后如果不成立

                return;

            sswap(wz[0]+pown[k-1],wz[1]+pown[k-1],pown[k-1]);//换后面的两个

            dfs(k+1,cn+1);

            sswap(wz[0]+pown[k-1],wz[1]+pown[k-1],pown[k-1]);

            sswap(wz[0],wz[1],pown[k-1]);//换前面的两个

            dfs(k+1,cn+1);

            sswap(wz[0],wz[1],pown[k-1]);

        }

        else return ;

    }

    else return;

}

int prerun(){

    pown[0]=1;fac[0]=1;

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

        pown[i]=pown[i-1]*2;

        fac[i]=fac[i-1]*i;

    }

    //pour(pown,1,14,5,"Pow");

    //pour(fac ,1,14,5,"fac");

}

int main(){

    prerun();

    scanf("%d",&n);

    for(int i=1;i<=pown[n];i++)

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

    dfs(1,0);

    cout<<ans<<endl;

}

巴特西

[BZOJ3990][SDOI2015][LOJ#2181]-排序

最新文章

热门文章