「BZOJ3990」[SDOI2015] 排序
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
HINT
100%的数据, 1<=N<=12.
题解
膜拜PoPoQQQ大爷：
题目大意：给定一个长度为2^n的排列，有n个操作，第i个操作为「将序列分成2^(n-i+1)段，每段长2^(i-1)，然后任选两段交换」，每个操作最多用一次，求有多少操作序列能把序列排出来
Orz dzy
首先我们很容易发现一个操作序列是否合法与序列的顺序是无关的
因此我们只需要确定某个操作序列中每个操作选不选就行了 那么这类操作序列对答案的贡献就是选择的操作数的阶乘
我们从小到大DFS，对于第i次操作我们将序列分成2^(n-i)段，每段长度2^i
我们找到序列中不是连续递增的段，如果这样的段超过2个，显然就废了
如果没有这样的段，就不需要执行这个操作
如果有一个这样的段，判断将这个段的前半部分和后半部分交换后是否连续递增，如果是就交换然后继续DFS
如果有两个这样的段，判断四种交换情况然后DFS
似乎只有一种情况可能合法？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define mod 10000007 using namespace std; 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; } int n; int bin[20],fac[20],a[5005]; ll ans; bool check(int x,int k) { for(int i=1;i<bin[k];i++)if(a[x+i]!=a[x+i-1]+1)return 0; return 1; } void swap(int x,int y,int k) { for(int i=0;i<bin[k];i++) swap(a[x+i],a[y+i]); } void dfs(int k,int now) { if(k==n+1) { ans+=fac[now]; return; } int t1=0,t2=0; for(int i=1;i<=bin[n];i+=bin[k]) if(!check(i,k)) { if(!t1)t1=i; else if(!t2)t2=i; else return; } if(!t1&&!t2)dfs(k+1,now); else if(t1&&!t2) { swap(t1,t1+bin[k-1],k-1); dfs(k+1,now+1); swap(t1,t1+bin[k-1],k-1); } else { for(int x=0;x<=1;x++) for(int y=0;y<=1;y++) { swap(t1+x*bin[k-1],t2+y*bin[k-1],k-1); if(check(t1,k)&&check(t2,k)) { dfs(k+1,now+1); swap(t1+x*bin[k-1],t2+y*bin[k-1],k-1); break; } swap(t1+x*bin[k-1],t2+y*bin[k-1],k-1); } } } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; fac[0]=1;for(int i=1;i<=12;i++)fac[i]=fac[i-1]*i; n=read(); for(int i=1;i<=bin[n];i++)a[i]=read(); dfs(1,0); printf("%lld",ans); return 0; } |
计数器 9854587
OI 课件=>
OI 课件=>
程序是不是错了？输入2 1 4 2 3，应该是0，您的输出2
要确认最终序列合法性。。。
已更正
不是只有一种情况 比如 1 4 3 2