BZOJ 3990 排序

发表于 | 更新于

Link

唉，还是too young。

Solution

操作序列的顺序不影响最终的结果。 于是就枚举操作序列，最终乘上步数的阶乘。 及时排除掉不可能排好的情况。

从小到大DFS，有点归并的感觉。

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
62
63
64
65
66
67
68
69
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
using std::swap;
const int N=12,MAXN=20,MAXL=1<<13;
LL fac[MAXN];int a[MAXL],n;
void swap_n(int *x,int n,int *y)
{
	for(int i=1;i<=n;i++)
		swap(*x++,*y++);
}
bool check(int d)
{
	for(int i=1;i+d<=(1<<n);i+=d*2)
		if(a[i]+d!=a[i+d]) return 0;
	return 1;
}
LL DFS(int cur,int cnt)//进行完cnt，要进行cur
{
	if(cur==n) return fac[cnt];
	int stack[5],top=0;
	int d=(1<<cur);
	for(int i=1;i+d<=(1<<n);i+=d*2)
	{
		if(a[i]+d!=a[i+d])
		{
			if(top==4) return 0;
			stack[++top]=i;
			stack[++top]=i+d;
		}
	}
	if(top==0) return DFS(cur+1,cnt);
	LL res=0;
	if(top==2)
	{
		swap_n(a+stack[1],d,a+stack[2]);
		res=DFS(cur+1,cnt+1);
		swap_n(a+stack[1],d,a+stack[2]);
	}
	else
	{
		for(int i=1;i<=top-1;i++)
			for(int j=i+1;j<=top;j++)
			{
				swap_n(a+stack[i],d,a+stack[j]);
				if(check(d))
					res+=DFS(cur+1,cnt+1);
				swap_n(a+stack[i],d,a+stack[j]);
			}
	}
	return res;
}
int main()
{
	fac[0]=1;for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i;
//	freopen("input","r",stdin);
	get(n);
	for(int i=1;i<=(1<<n);i++) get(a[i]);
	printf("%lld\n",DFS(0,0));
	return 0;
}
/* AC Record(Bugs)
 * WA
 * 看题解没研究清楚 实现不同
 */