3990: [SDOI2015]排序
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 336 Solved: 164
[Submit][Status][Discuss]
Description
小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].
Input
第一行,一个整数N
第二行,2^N个整数,A[1..2^N]
Output
一个整数表示答案
Sample Input
3
7 8 5 6 1 2 4 3
7 8 5 6 1 2 4 3
Sample Output
6
网上题解都看不懂。。
只能%hzwer代码。
黄学长:
每种交换只能用一次。
我们从小到大DFS，对于第i次操作我们将序列分成2^(n-i)段，每段长度2^i
我们找到序列中不是连续递增的段，如果这样的段超过2个，显然就废了
如果没有这样的段，就不需要执行这个操作
如果有一个这样的段，判断将这个段的前半部分和后半部分交换后是否连续递增，如果是就交换然后继续DFS
如果有两个这样的段，判断四种交换情况然后DFS
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> using namespace std; int a[],n; long long fac[],ans=; void init(){fac[]=;for(int i=;i<=n;i++)fac[i]=fac[i-]*i;} int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x;
} void swap(int x,int y,int nu)
{
for(int i=x,j=y,nn=;nn<nu;nn++)
swap(a[i+nn],a[j+nn]);
} void DFS(int dep,int sco)
{
if(dep==n)
{
ans+=fac[sco];
return;
}
int temp=<<(dep+),stack[]={,,,},top=;
for(int i=;i<(<<n);i+=temp)
{
if(a[i+(temp>>)-]+!=a[i+(temp>>)])stack[++top]=i+(temp>>)-;
if(top>)return;
}
if(top==)
{
DFS(dep+,sco);
return;
}
else if(top==)
{
if(a[stack[]-(temp>>)+]!=a[stack[]+(temp>>)]+)return;
swap(stack[top]-(temp>>)+,stack[top]+,temp>>);
DFS(dep+,sco+);
swap(stack[top]-(temp>>)+,stack[top]+,temp>>);
return;
}
else
{
if(a[stack[]]+==a[stack[]+]&&a[stack[]]+==a[stack[]+])
{
swap(stack[]-(temp>>)+,stack[]-(temp>>)+,temp>>);
DFS(dep+,sco+);
swap(stack[]-(temp>>)+,stack[]-(temp>>)+,temp>>);
swap(stack[]+,stack[]+,temp>>);
DFS(dep+,sco+);
swap(stack[]+,stack[]+,temp>>);
}
else if(a[stack[]]+==a[stack[]-(temp>>)+]&&a[stack[]+(temp>>)]+==a[stack[]+])
{
swap(stack[]+,stack[]-(temp>>)+,temp>>);
DFS(dep+,sco+);
swap(stack[]+,stack[]-(temp>>)+,temp>>);
}
else if(a[stack[]]+==a[stack[]-(temp>>)+]&&a[stack[]+(temp>>)]+==a[stack[]+])
{
swap(stack[]+,stack[]-(temp>>)+,temp>>);
DFS(dep+,sco+);
swap(stack[]+,stack[]-(temp>>)+,temp>>);
}
return;
}
} int main()
{
n=read();
init();
for(int i=;i<=(<<n);i++)
a[i]=read();
DFS(,);
printf("%lld",ans);
return ;
}