火车进栈

背景

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

描述

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

输入格式

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

输出格式

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

测试样例

输入

3

输出

123  132  213  231  321

 

 

输入

5

输出

12345

12354

12435

12453

12543

13245

13254

13425

13452

13542

14325

14352

14532

15432

21345

21354

21435

21453

21543

23145

问题分析：就是模拟进栈出栈的问题，这里因为是有序的，所以每个数字后面比这个数字小的几个数字应该是逆序，所以先用dfs全排列出所有情况，然后再按这种方法来判断

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<iostream> using namespace std; int a[22]; int book[22]; int cnt = 0; int n; int check() { int maxn; for(int i=0; i<n; i++) { int s = 0; for(int j=i+1; j<n; j++) { if (a[j] < a[i]) { if (s == 0) { maxn = a[j]; s = 1; } if (maxn < a[j]) return 0; } } } return 1; } void dfs(int m) { if (m == n && cnt<=20) { if (check()) { for(int i=0; i<n; i++) printf("%d",a[i]); printf("\n"); cnt++; return ; } } for(int j=1; j<=n; j++) { if (book[j] == 0) { a[m] = j; book[j] = 1; dfs(m+1); if (cnt == 20) return ; book[j] = 0; } } } int main() { scanf("%d",&n); memset(a,0,sizeof(a)); memset(book,0,sizeof(book)); dfs(0); return 0; } 还有另外一种模拟进出栈的方法，不是很懂，先搁着，似乎是用了卡特兰数？ #include<stdio.h> #include<iostream> #include<stack> #include<string.h> #include<vector> using namespace std; int book[23]; int temp[23]; int N; int time; int check(); void dfs(int t); int main(){ while(scanf("%d",&N)!=EOF){ memset(book,0,sizeof(book)); time = 0; dfs(0); } return 0; } //模拟进栈 int check(){ stack<int>s; vector<int >v; int t = 0; for(int i=1;i<=N;i++){ while(!s.empty()&&s.top()==temp[t]){ v.push_back(s.top()); s.pop(); t++; } if(i==temp[t]){ v.push_back(i); t++; } else{ s.push(i); } while(!s.empty()&&s.top()==temp[t]){ v.push_back(s.top()); s.pop(); t++; } } for(int i=0;i<N;i++){ if(v[i]!=temp[i]) return 0; } return 1; } //搜出全排列 void dfs(int t){ if(t==N){ int status = check(); if(status&&time<20){ time++; for(int i=0;i<N;i++){ printf("%d",temp[i]); } printf("\n"); } return ; } for(int i=1;i<=N;i++){ if(book[i]==0){ temp[t] = i; book[i] = 1; dfs(t+1); if(time>=20) return ; book[i] = 0; } } }