BZOJ3990 排序

浏览数：25 / 时间：2015年06月08日

题目：www.lydsy.com/JudgeOnline/problem.php?id=3990

这题很不错。

刚开始时无从下手，想了好多$O((2^n)log(2^n))$ 的idea，但是都不行。

后来去看题解发现操作序列是满足交换率的，然后竟然是搜索。

因为swap是swap的逆运算（歪歪的）

然后只要从小到大枚举操作序列就可以了。

这样类似分治下去，当你在计算长度为$2^i$的序列时已经保证了所有长度为$2^{i-1}$的序列的「连续且递增」。

注意是「连续且递增」，开始W了好多发，然后推掉重写（开抄）呜呜。

好像可以证明是$O(n \cdot 2^{2n})$ ？

以后见到这种操作数很小的题目要想想搜索，就算是暴力也可以多拿分。

#include <cstdio>
#include <cstring>
#include <vector>

#define LL long long
#define N 13

using namespace std;

int n;
LL fact[21],ans;

void change(vector<int> &x,int l1,int l2,int len){
    for(int i=0;i<len;i++)
        swap(x[l1+i],x[l2+i]);
}

bool check(vector<int> x,int l,int len){
    for(int i=1;i<len;i++)
        if(x[l+i]!=x[l+i-1]+1) return 0;
    return 1;
}

void dfs(vector<int> x,int t,int now){
    if(t==n){
        ans+=fact[now];
        return;
    }
    int tot=0,a[5];
    for(int i=0;i<(1<<n);i+=(1<<(t+1)))
        if(!check(x,i,1<<(t+1))){
            if(tot==4) return;
            a[++tot]=i; a[++tot]=i+(1<<t);
        }
    vector<int> b;
    if(!tot) dfs(x,t+1,now);
    if(tot==2){
        if(x[a[2]]+(1<<t)==x[a[1]]){
            b=x;
            change(b,a[1],a[2],1<<t);
            dfs(b,t+1,now+1);
        }
    }
    if(tot==4){
        if(x[a[1]]+(1<<t)==x[a[3]] && x[a[2]]+(1<<t)==x[a[4]]){
            b=x;
            change(b,a[2],a[3],1<<t);
            dfs(b,t+1,now+1);
        }
        if(x[a[1]]+(1<<t)==x[a[4]] && x[a[3]]+(1<<t)==x[a[2]]){
            b=x;
            change(b,a[2],a[4],1<<t);
            dfs(b,t+1,now+1);
        }
        if(x[a[3]]+(1<<t)==x[a[2]] && x[a[1]]+(1<<t)==x[a[4]]){
            b=x;
            change(b,a[1],a[3],1<<t);
            dfs(b,t+1,now+1);
        }
        if(x[a[4]]+(1<<t)==x[a[2]] && x[a[3]]+(1<<t)==x[a[1]]){
            b=x;
            change(b,a[1],a[4],1<<t);
            dfs(b,t+1,now+1);
        }
    }
}

vector<int> a;

int main(){
    scanf("%d",&n);
    a.resize(1<<n);
    for(int i=0;i<(1<<n);i++) scanf("%d",&a[i]);
    fact[0]=1;
    for(int i=1;i<=18;i++) fact[i]=fact[i-1]*(LL)i;
    dfs(a,0,0);
    printf("%lld\n",ans);
    return 0;
}