背景 话说这是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 输入 8 输出 12345678 12345687 12345768 12345786 12345876 12346578 12346587 12346758 12346785 12346875 12347658 12347685 12347865 12348765 12354678 12354687 12354768 12354786 12354876 12356478 输入 13 输出 12345678910111213 12345678910111312 12345678910121113 12345678910121311 12345678910131211 12345678911101213 12345678911101312 12345678911121013 12345678911121310 12345678911131210 12345678912111013 12345678912111310 12345678912131110 12345678913121110 12345678109111213 12345678109111312 12345678109121113 12345678109121311 12345678109131211 12345678101191213 输入 16 输出 12345678910111213141516 12345678910111213141615 12345678910111213151416 12345678910111213151614 12345678910111213161514 12345678910111214131516 12345678910111214131615 12345678910111214151316 12345678910111214151613 12345678910111214161513 12345678910111215141316 12345678910111215141613 12345678910111215161413 12345678910111216151413 12345678910111312141516 12345678910111312141615 12345678910111312151416 12345678910111312151614 12345678910111312161514
12345678910111314121516
//（模拟）栈，全排列（dfs）
#include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #include<stack> using namespace std; int n,num=0,a[25],book[25]; int suit() { vector<int>vt; stack<int>st; int i,j=0; for(i=1;i<=n;i++)// i代表了火车入栈的顺序 {//上来先比较当前要入栈的元素和全排列的是否相同 if(i==a[j])//若相同，则该元素入栈后又要立即出栈，所以不必入栈了，存入一个数组vt { vt.push_back(i); j++; } else st.push(i);//若不同，则入栈 while(!st.empty()&&a[j]==st.top()) // 若判断完了a[j]，j++，则a[j]变成了下一个元素，因为变完了的a[j]可能和栈顶元素相等，需要判断是否和此时的栈顶元素是否相等，若相等则出栈，并且存入vt数组，（当时做题的时候把while循环写在了for循环之外）否则可能当i全入栈后也没有找到与a[j]相等的，这样就会错判该顺序不，满足题意。
{ vt.push_back(a[j]); st.pop(); j++; } } for(i=0;i<n;i++) { if(vt[i]!=a[i])// 最后比较模拟的出栈顺序是否和全排列的结果一样，若一样则满足题意
return 0; } return 1; } void dfs(int step)//深搜找出全排列结果， int i,j; if(step==n&&num<20)
{ if(suit())//再判断是否满足出栈顺序 { { num++; for(i=0;i<n;i++) printf("%d",a[i]); printf("\n"); } return; } for(i=1;i<=n;i++) { if(book[i]==0) { a[step]=i; book[i]=1; dfs(step+1);
// if(num>=20)
// return ; a[step]=0; book[i]=0; } } return; } int main() { scanf("%d",&n); memset(book,0,sizeof(book));
// memset(a,0,sizeof(a)); dfs(0); return 0; }
转载请注明原文地址: https://ju.6miu.com/read-23681.html
