NC20374. [SDOI2015]排序
描述
输入描述
第一行,一个整数N
第二行,2^N个整数,A[1..2^N]
输出描述
一个整数表示答案
示例1
输入:
3 7 8 5 6 1 2 4 3
输出:
6
C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 480K, 提交时间: 2022-12-30 10:18:33
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int num[5010],fac[20],ans=0;
int n;
bool check(int s,int pos)
{
s=((s-1)<<pos)+1;
int last=num[s];
for(int i=2;i<=(1<<pos);i++)
{
if (num[s+i-1]!=last+1) return 0;
else last=num[s+i-1];
}
return 1;
}
void Swap(int s1,int s2,int pos)
{
for(int i=1;i<=(1<<pos);i++)
swap(num[s1+i-1],num[s2+i-1]);
}
void dfs(int pos,int k)
{
if (pos==n+1) {ans+=fac[k];return;}
int p1=0,p2=0;
for(int i=1;i<=(1<<(n-pos));i++)
{
if (!check(i,pos))
{
if (!p1) p1=i;
else if (!p2) p2=i;
else return;
}
}
if (!p1&&!p2) dfs(pos+1,k);
else if (p1&&!p2)
{
Swap(((p1-1)<<pos)+1,((p1-1)<<pos)+(1<<(pos-1))+1,pos-1);
if (check(p1,pos)) dfs(pos+1,k+1);
Swap(((p1-1)<<pos)+1,((p1-1)<<pos)+(1<<(pos-1))+1,pos-1);
}
else
{
for(int a=0;a<=1;a++)
for(int b=0;b<=1;b++)
{
int s1,s2;
if (!a) s1=((p1-1)<<pos)+1;
else s1=((p1-1)<<pos)+(1<<(pos-1))+1;
if (!b) s2=((p2-1)<<pos)+1;
else s2=((p2-1)<<pos)+(1<<(pos-1))+1;
Swap(s1,s2,pos-1);
if (check(p1,pos)&&check(p2,pos))
dfs(pos+1,k+1);
Swap(s1,s2,pos-1);
}
}
}
int main()
{
scanf("%d",&n);
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i;
for(int i=1;i<=(1<<n);i++)
scanf("%d",&num[i]);
dfs(1,0);
printf("%d",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2019-03-09 14:39:19
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int num[5010],fac[20],ans=0;
int n;
bool check(int s,int pos)
{
s=((s-1)<<pos)+1;
int last=num[s];
for(int i=2;i<=(1<<pos);i++)
{
if (num[s+i-1]!=last+1) return 0;
else last=num[s+i-1];
}
return 1;
}
void Swap(int s1,int s2,int pos)
{
for(int i=1;i<=(1<<pos);i++)
swap(num[s1+i-1],num[s2+i-1]);
}
void dfs(int pos,int k)
{
if (pos==n+1) {ans+=fac[k];return;}
int p1=0,p2=0;
for(int i=1;i<=(1<<(n-pos));i++)
{
if (!check(i,pos))
{
if (!p1) p1=i;
else if (!p2) p2=i;
else return;
}
}
if (!p1&&!p2) dfs(pos+1,k);
else if (p1&&!p2)
{
Swap(((p1-1)<<pos)+1,((p1-1)<<pos)+(1<<(pos-1))+1,pos-1);
if (check(p1,pos)) dfs(pos+1,k+1);
Swap(((p1-1)<<pos)+1,((p1-1)<<pos)+(1<<(pos-1))+1,pos-1);
}
else
{
for(int a=0;a<=1;a++)
for(int b=0;b<=1;b++)
{
int s1,s2;
if (!a) s1=((p1-1)<<pos)+1;
else s1=((p1-1)<<pos)+(1<<(pos-1))+1;
if (!b) s2=((p2-1)<<pos)+1;
else s2=((p2-1)<<pos)+(1<<(pos-1))+1;
Swap(s1,s2,pos-1);
if (check(p1,pos)&&check(p2,pos))
dfs(pos+1,k+1);
Swap(s1,s2,pos-1);
}
}
}
int main()
{
scanf("%d",&n);
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i;
for(int i=1;i<=(1<<n);i++)
scanf("%d",&num[i]);
dfs(1,0);
printf("%d",ans);
return 0;
}