标签：代码量 $2 name 分类 需要 表示 状压 dfs EDA
Description
小A有一个1-2^N的排列A[1..2^N],他希望将A数组从小到大排序,小A可以执行的操作有N种,每种操作最多可以执行一次,对于所有的i(1
下面是一个操作事例:
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
Output
Sample Input
3
7 8 5 6 1 2 4 3
Sample Output
6
正解居然是搜索，考场上看这板儿B是个神仙状压就skip掉了
后悔啊……把猛肝某APIO2016T1的时间放这题上怎么还没30分啊……
手%几组数据可以发现，操作序列的合法性与顺序无瓜
所以只需确定序列中有没有第i种操作，最后将统计结果的阶乘输出即为序列数
枚举操作种数i，+1什么的太麻烦就直接分成$2^{N-i}$段，每段$2^i$个数
然后要交换的话就需要找非严格递增序列($a_{x+1}!=a_x+1$)
超过两个显然不可行，直接return
接下来分类讨论：
如果没有这样的序列，继续dfs
如果有一个，尝试内部一分为二后交换使之满足严格递增
如果有两个，两段分成四段尝试交换
(感谢hzwer的题解 大大减少了我的代码量 两层for分类讨论确实比四个if else美观多辽)
收获：看到二进制不要直接想状压，还有可能是树形结构或者二分搜索
#include
#include
#includeusing namespace std;
const int N=(112)+5;
int n,a[N],tot;
long long ans=0,bin[25],fac[25];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}
void ini()
{
bin[0]=fac[0]=1;
for(int i=1;i20;i++)
bin[i]=bin[i-1]1,fac[i]=1LL*i*fac[i-1];
}
bool judge(int p,int k)
{
for(int j=1;j)
if(a[p+j]!=a[p+j-1]+1)return 0;
return 1;
}
void sw_(int x,int y,int k)
{
for(int i=0;i)
swap(a[x+i],a[y+i]);
}
void dfs(int p,int val)
{
if(p==n+1)
{
ans+=fac[val];
return ;
}
int bl1,bl2;bl1=bl2=0;
for(int i=1;ibin[p])
if(!judge(i,p))
{
if(!bl1)bl1=i;
else if(!bl2)bl2=i;
else return ;
}
if(!bl1&&!bl2)dfs(p+1,val);
else if(bl1&&!bl2)
{
sw_(bl1,bl1+bin[p-1],p-1);
dfs(p+1,val+1);
sw_(bl1,bl1+bin[p-1],p-1);
}
else
{
for(int num1=0;num12;num1++)
for(int num2=0;num22;num2++)
{
sw_(bl1+num1*bin[p-1],bl2+num2*bin[p-1],p-1);
if(judge(bl1,p)&&judge(bl2,p))
{
dfs(p+1,val+1);
sw_(bl1+num1*bin[p-1],bl2+num2*bin[p-1],p-1);
break;
}
sw_(bl1+num1*bin[p-1],bl2+num2*bin[p-1],p-1);
}
}
}
int main()
{
n=read();
ini();
for(int i=1;i)
a[i]=read();
dfs(1,0);
coutendl;
return 0;
}
[SDOI2015]排序 题解 (搜索)
标签：代码量 $2 name 分类 需要 表示 状压 dfs EDA
原文地址：https://www.cnblogs.com/Rorschach-XR/p/11164567.html