? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? [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
Sample Output

6

HINT

100%的數據, 1<=N<=12.

Source

Round 1 感謝ZKY制作非官方數據

?

分析：

顯然，對于每一種方案，我改變其操作順序，仍然不影響結果，所以我們只需枚舉每種操作做與不做即可，然后將排列數加入答案即可。

考慮進一步優化，對于第i種操作，將序列分為若干個長為2^(i-1)的小段，由于每種操作只能用一次，則當每個小段各自元素都連續且遞增，就不需要這種操作了（相當于每2^(i-1)個為一組，每組都排好了序，要想是整體進一步排序，只能依靠下一步操作來排了），如果有一個不連續遞增，則將這組分為兩份后交換即可，如果有2組不滿足，分四種情況討論，最后如果超過2個，顯然無法使它們有序，則對這種方案剪枝。

關鍵思想是由局部有序一直操作直至全局有序，當枚舉第i種操作時，此時2^(i-2)長度的段必然是有序的（不合法情況已去除），只需考慮2^(i-1)長度的段即可。

program sort; vara:array[0..10000]of longint;n,i,m:longint; ans,tot:int64; procedure swap(x1,y1,x2,y2:longint); var i,t:longint; beginfor i:=0 to y1-x1 dobegin t:=a[x1+i]; a[x1+i]:=a[x2+i]; a[x2+i]:=t; end; end; function cheak:boolean; var i:longint; beginfor i:=2 to m do if a[i]<>a[i-1]+1 then exit(false);exit(true); end; procedure dfs(x:longint); var i,j,t,v,s,k:longint; l:int64; w:array[0..2]of longint; beginif x>=n thenbegin if cheak=false then exit;l:=1;for i:=1 to tot do l:=l*i; inc(ans,l); exit; end;t:=1 shl (x+1); v:=1 shl x; s:=v; k:=0;for i:=1 to m div t dobeginif (a[s]+1<>a[s+1])or(a[s] mod v<>0) then begin inc(k); if k>2 then exit;w[k]:=s; end;s:=s+t;end;if k=0 then dfs(x+1);inc(tot);if k=1 then begin swap(w[1]-v+1,w[1],w[1]+1,w[1]+v); dfs(x+1); swap(w[1]-v+1,w[1],w[1]+1,w[1]+v); end;if k=2 thenbeginif (a[w[1]]+1=a[w[2]+1])and(a[w[2]]+1=a[w[1]+1]) thenbeginswap(w[1]-v+1,w[1],w[2]-v+1,w[2]); dfs(x+1); swap(w[1]-v+1,w[1],w[2]-v+1,w[2]);swap(w[1]+1,w[1]+v,w[2]+1,w[2]+v); dfs(x+1); swap(w[1]+1,w[1]+v,w[2]+1,w[2]+v);end;if (a[w[2]]+1=a[w[1]-v+1])and(a[w[2]+v]+1=a[w[1]+1]) thenbegin swap(w[1]-v+1,w[1],w[2]+1,w[2]+v);dfs(x+1); swap(w[1]-v+1,w[1],w[2]+1,w[2]+v);end;if (a[w[1]+v]+1=a[w[2]+1])and(a[w[1]]+1=a[w[2]-v+1]) thenbegin swap(w[1]+1,w[1]+v,w[2]-v+1,w[2]);dfs(x+1); swap(w[1]+1,w[1]+v,w[2]-v+1,w[2]); end;end;dec(tot); end; beginreadln(n);m:=1 shl n;for i:=1 to m do read(a[i]);ans:=0; tot:=0;dfs(0);writeln(ans); end. View Code

?

轉載于:https://www.cnblogs.com/qtyytq/p/5903125.html

總結

以上是生活随笔為你收集整理的BZOJ 3990： [SDOI2015]排序（搜索+剪枝）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。