目录
LOJ2181 排序题意题解Code:
LOJ2181 排序
题目传送门
题意
小 A 有一个\(1 \sim 2^n\)的排列\(A[1 \dots 2^n]\)，他希望将\(A\)数组从小到大排序，小 \(A\) 可以执行的操作有 \(n\) 种，每种操作最多可以执行一次，对于所有的 \(i（1 \leq i \leq n）\)，第 \(i\) 种操作为将序列从左到右划分为 \(2^{n-i+ 1}\)段，每段恰好包括2^{i-1}个数，然后整体交换其中两段。小\(A\)想知道可以将数组 \(A\) 从小到大排序的不同的操作序列有多少个，小\(A\)认为两个操作序列不同，当且仅当操作个数不同，或者至少一个操作不同（种类不同或者操作位置不同）。\((1 \leq n \leq 12)\)
题解
很妙的一个爆搜，由于规定了每一种长度的整体交换只能使用一次，所以我们从小的操作往大的操作做，那么如果能够满足条件，则到达该操作\(i\)的时候，序列分成的长为\(2^{i-1}\)的段一定是递增的，否则就是不符合答案的。然后我们考虑如何处理当前这一层的交换。我们分四种情况: 如果长度为\(2^i\)的段没有非递增的，那么就说明不用交换。 如果只有一段长度为\(2^i\)的段非递增，那么就说明我们就只需要将这一段的前一半和后一半交换即可（因为这两半都是一定保证递增的）。 如果有两段长度为\(2^i\)的段非递增，那么就有四种交换的可能，我们都直接搜下去就行可。 如果有大于两段的\(2^i\)的段非递增，那么说明当前段无法通过一次交换完成，直接return就行了。 由于我们在每一层最多只会做出四次的决策，那么复杂度就是\(O(4^{n})\)。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int N=1e4+50;
int n,len;
ll ans;
int a[N],block[N];
ll fac[N];
/*==================Define Area================*/
int Judge(int l,int k) {
for(int i=1;i<block[k];i++) {
if(a[l+i-1]+1!=a[l+i]) return 0;
}
return 1;
}
void Swap(int l,int r,int k) {
for(int i=0;i<block[k];i++)
swap(a[l+i],a[r+i]);
}
void Dfs(int k,int nw) {
if(k==n+1) {
ans+=fac[nw];
return ;
}
int pos1=0,pos2=0;
for(int i=1;i<=len;i+=block[k]) {
if(!Judge(i,k)) {
if(!pos1) pos1=i;
else if(!pos2) pos2=i;
else return ;
}
}
if(!pos1&&!pos2) Dfs(k+1,nw);
else if(pos1&&!pos2) {
Swap(pos1,pos1+block[k-1],k-1);
Dfs(k+1,nw+1);
Swap(pos1,pos1+block[k-1],k-1);
}
else {
for(int i=0;i<2;i++) {
for(int j=0;j<2;j++) {
Swap(pos1+i*block[k-1],pos2+j*block[k-1],k-1);
if(Judge(pos1,k)&&Judge(pos2,k)) {
Dfs(k+1,nw+1);
Swap(pos1+i*block[k-1],pos2+j*block[k-1],k-1);
break;
}
Swap(pos1+i*block[k-1],pos2+j*block[k-1],k-1);
}
}
}
return ;
}
int main() {
read(n);
block[0]=1,fac[0]=1;
for(int i=1;i<=n;i++) block[i]=block[i-1]<<1,fac[i]=fac[i-1]*i;
len=1<<n;
for(int i=1;i<=len;i++) read(a[i]);
Dfs(1,0);
printf("%lld\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10224871.html
