BZOJ 3990 【DFS/回溯/倍增】

SDOI2015 排序

本来没想写…一翻Status发现登上了效率第一,那就贴一贴代码…
就是按大小深搜可能交换的区间,每层最多2个状态,最多12层。

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<algorithm>
using namespace std;

inline int read(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}

typedef long long ll;
const int maxn=12;
const int maxl=1<<maxn;
int n,a[maxl]; ll ans;

inline bool inorder(int w,int x,int y,int z){
return w<x && x<y && y<z;
}
inline void change(int u,int v,int len){
for(int i=0;i<len;i++) swap(a[u+i],a[v+i]);
}
inline ll f(int x){
return x?f(x-1)*x:1;
}

void search(int t,int res){
if(t>n){
ans+=f(res); return; }
int l=1<<t,mid=l>>1,num=0,u,v;
for(int i=0;i<1<<n;i+=l)
if(a[i+mid-1]+1!=a[i+mid])
if(!num++) u=i; else v=i;
if(num>2) return;
else if(num==2){
int w=a[u],x=a[u+mid],y=a[v],z=a[v+mid];
if(inorder(y,x,w,z) || inorder(w,z,y,x)){
change(u,v,mid); search(t+1,res+1); change(u,v,mid);
change(u+mid,v+mid,mid); search(t+1,res+1); change(u+mid,v+mid,mid);
}
else if(inorder(w,y,x,z) || inorder(x,z,w,y)){
change(u+mid,v,mid); search(t+1,res+1); change(u+mid,v,mid);
}
else if(inorder(z,x,y,w) || inorder(y,w,z,x)){
change(u,v+mid,mid); search(t+1,res+1); change(u,v+mid,mid);
}
else return;
}
else if(num==1){ change(u,u+mid,mid); search(t+1,res+1); change(u,u+mid,mid);}
else search(t+1,res);
}

int main(){
n=read();
for(int i=0;i<1<<n;i++) a[i]=read();
search(1,0);
printf("%lld",ans);
return 0;
}