首页 > 代码库 > BZOJ3990 SDOI2015 排序 DFS

BZOJ3990 SDOI2015 排序 DFS

2024-09-08 04:48:01   218人阅读

题意：给定一个长度为2^N的序列和N个操作，每个操作i为将2^N分为2^(N-i+1)段，然后任意交换其中两段，求有多少种不同的交换方案使得序列升序

题解：

由于一个合法的方案中，交换操作的先后顺序，方案依然合法，所以我们只需要确定使用哪些操作。

按i的大小从小到大枚举每一个操作i，然后将序列分为2^(N-i)段，看有多少段不是递增的。如果有两段以上显然无解，如果有一段那么直接折半交换，如果有两段则枚举四种情况看是否合法。

技术分享
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int P[]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600};const int MAXN=(1<<12)+2;int N,a[MAXN];long long ans;bool Check(int p,int x){    for(int i=p+1;i<=p-1+(1<<x);i++)        if(a[i]-a[i-1]!=1) return 0;    return 1;}void Swap(int p1,int p2,int x){    for(int i=p1,j=p2;i<=p1-1+(1<<x);i++,j++) swap(a[i],a[j]);}void DFS(int x,int c){    if(x==N){        if(Check(1,N)) ans+=P[c];        return;    }    int p1=0,p2=0;    for(int i=1;i<=1<<N;i+=1<<(x+1))        if(!Check(i,x+1)){            if(!p1) p1=i;            else if(!p2) p2=i;            else return;        }    if(!p1) DFS(x+1,c);    else if(!p2) Swap(p1,p1+(1<<x),x),DFS(x+1,c+1),Swap(p1,p1+(1<<x),x);    else{        Swap(p1,p2,x),DFS(x+1,c+1),Swap(p1,p2,x);        Swap(p1,p2+(1<<x),x),DFS(x+1,c+1),Swap(p1,p2+(1<<x),x);        Swap(p1+(1<<x),p2,x),DFS(x+1,c+1),Swap(p1+(1<<x),p2,x);        Swap(p1+(1<<x),p2+(1<<x),x),DFS(x+1,c+1),Swap(p1+(1<<x),p2+(1<<x),x);    }}int main(){    cin >> N;    for(int i=1;i<=1<<N;i++) scanf("%d",a+i);    DFS(0,0);    cout << ans << endl;    return 0;}
View Code

 

BZOJ3990 SDOI2015 排序 DFS


联系
我们