Tyvj p1336 火车进站搜索全排列

背景

话说这是NOI夏or冬令营中的水题...... 做题前明确的是，这题当然<>n皇后/全排列 这里有n列火车将要进站再出站…… 但是，每列火车只有1节---那就是车头……

描述

有n列火车按1到n的顺序从东方左转进站，这个车站是南北方向的，它虽然无限长， 只可惜是一个死胡同，而且站台只有一条轨道， 火车只能倒着从西方出去，而且每列火车必须进站，先进后出。 （某生：不就是个栈吗？每次可以让右侧头火车进栈，或者让栈顶火车出站？ 占卜哥：闭嘴！） 就像这样：   出站<——-    <——进站             |车|             |站|             |__| 现在请你按《字典序》输出前20种可能的出栈方案。 注意：这题当然不等于全排列！！！

输入格式

一个数n N<=20 数据保证不会TLE所以千万不要halt

输出格式

《字典序》输出前20种答案，每行一种，不要空格

测试样例

输入

3

输出

123  132  213  231  321

 

 搜索做，每次枚举出栈多少个元素，记录出栈顺序，只需要输出20个，所以不会T

#include<stdio.h> #include<algorithm> #include<queue> #include<string.h> using namespace std; int stack[30],num[30],n,ans;//stack是模拟的当前栈，num是已经出栈的顺序 int dfs(int t,int l,int ri)//t是出了多少个，l是当前栈里有几个，ri是到了第几个点 { int i,k,s[30]; stack[l]=ri; if(ans>=20) return 0; if(ri==n) { ans++; for(i=1;i<t;i++) printf("%d",num[i]); for(i=l;i>=1;i--) printf("%d",stack[i]); printf("\n"); return 0; } for(i=1;i<=l;i++) s[i]=stack[i]; int tt=t; for(k=1;k<=l+1;k++) { for(i=l;i>=k;i--) { num[t++]=stack[i]; } dfs(t,k,ri+1); t=tt; for(i=1;i<=l;i++) stack[i]=s[i]; } return 0; } int main() { int i,ans=0; scanf("%d",&n); dfs(1,1,1); return 0; } 生成全排列判断

#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<string> #include<algorithm> #include<queue> #include<vector> #include<map> #include<set> #define eps 1e-9 #define PI 3.141592653589793 #define bs 1000000007 #define bsize 256 #define MEM(a) memset(a,0,sizeof(a)) #define inf 0x3f3f3f3f #define rep(i,be,n) for(i=be;i<n;i++) typedef long long ll; using namespace std; vector<int>a,b; int book[20]; int check() { MEM(book); int stack[20],top=0; int i,j; for(i=0;i<a.size();i++) { if(top!=0) { if(stack[top-1]>a[i]) return 0; } for(j=1;j<a[i];j++) { if(!book[j]) stack[top++]=j; } book[a[i]]=1; } return 1; } int main() { int i,n,ans=0; cin>>n; for(i=1;i<=n;i++) { a.push_back(i); b.push_back(i); } if(check()) { for(i=0;i<a.size();i++) cout<<a[i]; cout<<endl; ans++; } next_permutation(a.begin(),a.end()); while(a!=b&&ans<20) { if(check()) { for(i=0;i<a.size();i++) cout<<a[i]; cout<<endl; ans++; } next_permutation(a.begin(),a.end()); } return 0; }