129. 火车进栈 ACWING

2024-04-16 03:08
文章标签 acwing 火车 进栈 129

本文主要是介绍129. 火车进栈 ACWING,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这里有n列火车将要进站再出站,但是,每列火车只有1节,那就是车头。

这n列火车按1到n的顺序从东方左转进站,这个车站是南北方向的,它虽然无限长,只可惜是一个死胡同,而且站台只有一条股道,火车只能倒着从西方出去,而且每列火车必须进站,先进后出。

也就是说这个火车站其实就相当于一个栈,每次可以让右侧头火车进栈,或者让栈顶火车出站。

车站示意如图:

        出站<——    <——进站|车||站||__|

现在请你按《字典序》输出前20种可能的出栈方案。

输入格式
输入一个整数n,代表火车数量。

输出格式
按照《字典序》输出前20种答案,每行一种,不要空格。

数据范围
1≤n≤20
输入样例:
3
输出样例:
123
132
213
231
321

思路: 只有两种状态:1.当前栈顶出栈 2.下一个元素进栈
代码dfs中两次if回溯分别对应着两种状态。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>using namespace std;vector<int>ans;
stack<int>s;
int n,remain = 20;void dfs(int x)
{if(!remain)return;if(ans.size() == n){remain--;for(int i = 0;i < ans.size();i++){printf("%d",ans[i]);}printf("\n");return;}if(s.size()){ans.push_back(s.top());s.pop();dfs(x);s.push(ans.back());ans.pop_back();}if(x <= n){s.push(x);dfs(x + 1);s.pop();}
}int main()
{scanf("%d",&n);dfs(1);
}

这篇关于129. 火车进栈 ACWING的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907652

相关文章

【AcWing】851. 求最短路

spfa算法其实是对贝尔曼福特算法做一个优化。 贝尔曼福特算法会遍历所有边来更新,但是每一次迭代的话我不一定每条边都会更新,SPFA是对这个做优化。 如果说dist[b]在当前这次迭代想变小的话,那么一定是dist[a]变小了,只有a变小了,a的后继(b)才会变小。 用宽搜来做优化,用一个队列,队列里边存的就是所有变小了的结点(队列里存的是待更新的点)。 基本思路就是我更新过谁,我再拿

基于Spring Boot的火车订票管理系统

你好呀,我是计算机学姐码农小野!如果有相关需求,可以私信联系我。 开发语言:Java 数据库:MySQL 技术:JAVA语言 + Spring Boot框架 工具:IDEA/Eclipse、Navicat、Tomcat 系统展示 首页 管理员界面 用户购票 订单管理 摘要 随着网络技术的不断发展,火车订票管理系统逐渐由传统的线下操作转变为线上服

【AcWing】852. spfa判断负环

#include<iostream>#include<algorithm>#include<cstring>#include<queue>using namespace std;const int N= 1e5+10;int n,m;int h[N],w[N],e[N],ne[N],idx;int dist[N],cnt[N];//cnt存最短路径的边数bool st[N];v

AcWing 282. 石子合并

必看的视频讲解↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 【E28【模板】区间DP 石子合并——信息学竞赛算法】 合并过程总开销等于红色数字总和,可以理解为花费的总体力! f数组的含义是f【i】【j】是从第i堆石子开始到第j堆石子的花费体力最小值 如何理解三层for呢? 第一层for是控制区间长度len,第二层for是控制区间起点位置i,第三层for是控制区间

AcWing 897. 最长公共子序列

动态规划就是多见识应用题就完事儿了,也没有什么好说的。 讲解参考: 【E05 线性DP 最长公共子序列】 #include<iostream>#include<algorithm>#define N 1010using namespace std;char a[N],b[N];int n,m;int f[N][N];int main(){cin >> n >> m >> a

1hdu022数据结构堆栈-火车进站

/*判断一串序列能否按照堆栈的方式,进出栈之后得到另外一组序列*/ /*要把题目当做已知进出序列进行对比*/ #include<iostream>#include<cstdio>#include<cstring>using namespace std;struct node{char st[4];}str[10000];int main(){int n,i,j,t,k,ok

AcWing 2. 01背包问题

一定要看的视频讲解:↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 【E08【模板】背包DP 01背包——信息学竞赛算法】 i表示放入i个物品,j表示第j个物品,用于访问体积v【j】 #include <iostream>#include <algorithm>using namespace std;const int N = 1010;int n, m;int v[N]

数学建模学习(129):使用Python基于TOPSIS算法的多准则决策分析

案例代码都可做模板,但一定要理解原理和代码的逻辑。 文章目录 1. 引言2. TOPSIS算法原理与步骤2.1 MCDA背景与TOPSIS的适用性2.2 TOPSIS算法的详细步骤解析与数学公式 3. 案例背景与应用场景4. 数据说明与标准化处理4.1 数据4.2 数据标准化步骤与权重选择 5. 代码实现5.1 代码5.2 结果分析 1. 引言 在当今快速发展的信息时

Algorithm学习笔记 --- 铁轨(火车重排问题)

某城市有一个火车站,铁轨铺设如图所示。有n节车厢从A方向驶入车站,按进站顺序编号1~n。现让这些火车按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢,可以借助中转站C。C是一个可以停放任意多节车厢的车站,但由于末端封顶,驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢,一旦从A移入C,就不能再回到A了;一旦从C移入B,就不能回到C了。换句话说,在任意时刻,只有两种选择:A→C和C→B。

129- 横向移动WmicscriptSmbCrackMapExecProxyChainsImpacket

本章任然使用上一节的拓扑 章节点 IPC,WMI,SMB,PTH,PTK,PTT,SPN,WinRM,WinRS,RDP,Plink,DCOM,SSH;Exchange,LLMNR投毒,Plink,DCOM,Kerberos_TGS,GPO&DACL, 域控提权漏洞,约束委派,数据库攻防,系统补丁下发执行,EDR定向下发执行等 #域信息收集-目标&用户&凭据&网络 #域横向移动-wm