Acwing 309. 裝飾圍欄

題意：

有n個模板，長度分別是1到N，現在按照高低交錯的方式排列模板，能到的很多種排列的方案。
每個方案都可以寫作一個長度為N的序列，序列中的個元素是木板的長度，把這些序列按照字典序排序。問你排名為C的的序列是什么養的？

題解：

有T種排列，然后特定排列的排名是C，這類問題可以根據康托爾集合的思維方式來求解

康托爾排列的計數方法：
只考慮最左邊的第一位x應該是什么？
如果第一位x=h，后面的N-1個空構成的方案數為T1，如果T1>=C,說明該情況的方案數將第C位包含其中，那么第一位就應該是h
否則，第一位x=x+1，C=C-T1，再次重復考慮
為什么C要減T1呢？我們一開始只考慮第一位，x=h和x=h+1的情況數量是相繼排列的，如果C大于x=h的情況，那么和x=h+1比較時要減去x=h的情況
舉例：我們按照字典序對1到3排名：

123 132 213 231 312 321 求第三位的排列方式： 我們設第一位是1，然后方案數為2<3,所以看第一位是1+1=2的情況，C=3-2=1，此時2>1,說明第一位就是h

本題稍微復雜些，因為排列方式為交錯排序，我們規定高位表示左右兩側比他矮，低位就是左右兩側比他高。0表示低位，1表示高位
設dp(i,j,0/1）表示一共用了i塊模板，最左邊的一塊填的是j，這一位處于低位/高位的方案數
j等價于最左邊的模板排名是j

狀態轉移有：
dp[i][j][0] = sum{dp[i-1][k][1], j<=k<i}
dp[i][j][1] = sum{dp[i-1][k][0], 1<=k<j}

邊界條件：dp[1][1][0] = dp[1][1][1] = 1

這求出的是方案數，然后求排名為C的數，以1開頭的數有多少個？以2開始的有多少個？…一直這樣進行
C-(1xxxx)-(2xxxx)
減到不能減為止，那么此時第一位為h，就是第一位的值，后幾位同理

代碼：

記得開longlong

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=30; ll dp[maxn][maxn][3]; /* dp[1][1][0]=dp[1][1][1]=1; dp[i][j][0]=sum{dp[i-1][k][1],j<=k<i} dp[i][j][1]=sum{dp[i-1][k][0],i<=k<j} */ void init(){dp[1][1][0]=dp[1][1][1]=1;for(int i=2;i<=20;i++){for(int j=1;j<=i;j++){for(int k=j;k<i;k++)dp[i][j][0]+=dp[i-1][k][1];for(int k=1;k<j;k++)dp[i][j][1]+=dp[i-1][k][0];} } } int a[maxn]; bool vis[maxn]; ll N,C; void work(){int k;//先將第一位處理好 for(int i=1;i<=N;i++){if(dp[N][i][1]>=C){vis[i]=1;a[1]=i;k=1;break;}else C-=dp[N][i][1];if(dp[N][i][0]>=C){vis[i]=1;a[1]=i;k=0;break; }else C-=dp[N][i][0];}for(int i=2;i<=N;i++){k^=1;//高低位交錯進行int j=1;for(int x=1;x<=N;x++){if(vis[x])continue;if(k==0&&x<a[i-1]||k==1&&x>a[i-1]){//當前為低位且小于前一項||當前在高位且大于前一項 if(dp[N-i+1][j][k]>=C){vis[x]=1;a[i]=x;break;}else C-=dp[N-i+1][j][k];}j++;} } } int main() {init();int T=read();while(T--){cin>>N>>C;memset(vis,0,sizeof(vis));work();for(int i=1;i<=N;i++)cout<<a[i]<<" ";cout<<endl;} return 0; }

總結

以上是生活随笔為你收集整理的Acwing 309. 装饰围栏的全部內容，希望文章能夠幫你解決所遇到的問題。

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