房地产做网站的意义,软件开发模型有哪些,装信通装修网,网站建设运营计划书Acwing 309. 装饰围栏
题意#xff1a;
有n个模板#xff0c;长度分别是1到N#xff0c;现在按照高低交错的方式排列模板#xff0c;能到的很多种排列的方案。 每个方案都可以写作一个长度为N的序列#xff0c;序列中的个元素是木板的长度#xff0c;把这些序列按照字典…Acwing 309. 装饰围栏
题意
有n个模板长度分别是1到N现在按照高低交错的方式排列模板能到的很多种排列的方案。 每个方案都可以写作一个长度为N的序列序列中的个元素是木板的长度把这些序列按照字典序排序。问你排名为C的的序列是什么养的
题解
有T种排列然后特定排列的排名是C这类问题可以根据康托尔集合的思维方式来求解 康托尔排列的计数方法 只考虑最左边的第一位x应该是什么 如果第一位xh后面的N-1个空构成的方案数为T1如果T1C,说明该情况的方案数将第C位包含其中那么第一位就应该是h 否则第一位xx1CC-T1再次重复考虑 为什么C要减T1呢我们一开始只考虑第一位xh和xh1的情况数量是相继排列的如果C大于xh的情况那么和xh1比较时要减去xh的情况 举例我们按照字典序对1到3排名
123
132
213
231
312
321
求第三位的排列方式
我们设第一位是1然后方案数为23,所以看第一位是112的情况C3-21此时21,说明第一位就是h本题稍微复杂些因为排列方式为交错排序我们规定高位表示左右两侧比他矮低位就是左右两侧比他高。0表示低位1表示高位 设dp(i,j,0/1表示一共用了i块模板最左边的一块填的是j这一位处于低位/高位的方案数 j等价于最左边的模板排名是j
状态转移有 dp[i][j][0] sum{dp[i-1][k][1], jki} dp[i][j][1] sum{dp[i-1][k][0], 1kj}
边界条件dp[1][1][0] dp[1][1][1] 1
这求出的是方案数然后求排名为C的数以1开头的数有多少个以2开始的有多少个…一直这样进行 C-(1xxxx)-(2xxxx) 减到不能减为止那么此时第一位为h就是第一位的值后几位同理
代码
记得开longlong
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn30;
ll dp[maxn][maxn][3];
/*
dp[1][1][0]dp[1][1][1]1;
dp[i][j][0]sum{dp[i-1][k][1],jki}
dp[i][j][1]sum{dp[i-1][k][0],ikj}
*/
void init(){dp[1][1][0]dp[1][1][1]1;for(int i2;i20;i){for(int j1;ji;j){for(int kj;ki;k)dp[i][j][0]dp[i-1][k][1];for(int k1;kj;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 i1;iN;i){if(dp[N][i][1]C){vis[i]1;a[1]i;k1;break;}else C-dp[N][i][1];if(dp[N][i][0]C){vis[i]1;a[1]i;k0;break; }else C-dp[N][i][0];}for(int i2;iN;i){k^1;//高低位交错进行int j1;for(int x1;xN;x){if(vis[x])continue;if(k0xa[i-1]||k1xa[i-1]){//当前为低位且小于前一项||当前在高位且大于前一项 if(dp[N-i1][j][k]C){vis[x]1;a[i]x;break;}else C-dp[N-i1][j][k];}j;} }
}
int main()
{init();int Tread();while(T--){cinNC;memset(vis,0,sizeof(vis));work();for(int i1;iN;i)couta[i] ;coutendl;} return 0;
}
