火车进站

#!/user/local/bin/python3

TrainNum=int(input())
TrainIDlist=list(map(int,input().split()))

train_id_list=[[item,0,0] for item in TrainIDlist]
#第二列表示当前火车的第一个排列组合在matrix里面的行索引
#第三列表示当前火车的最后一个排列组合在matrix里面的列索引

matrix=[[0 for j in range(TrainNum*2)]]
matrix[0][0]=TrainIDlist[0]
matrix[0][1]=TrainIDlist[0]
train_id_list[0][1]=0
train_id_list[0][2]=0

##迭代计算所有排列组合
for i in range(1,TrainNum):
    upp_train_id=TrainIDlist[i-1]
    train_id=TrainIDlist[i]
    fcombin_index=train_id_list[i-1][1]   #上一辆火车的第一个排列组合在matrix里面的行索引
    lcombin_index=train_id_list[i-1][2]   #上一辆火车的最后一个排列组合在matrix里面的行索引
    train_id_list[i][1]=train_id_list[i-1][2]+1
    for j in range(fcombin_index,lcombin_index+1):
        upp_in_index=matrix[j].index(upp_train_id)  #上一辆火车进场以后，当前火车马上进场马上出场，所有的位置都可以插入
        for p in range(upp_in_index,i*2):
            matrix.append(matrix[j].copy())       
            nRowIndex=len(matrix)-1
            matrix[nRowIndex][p+1]=train_id
            matrix[nRowIndex][p+2]=train_id
            newindex=p+3
            while newindex<i*2+2:
                matrix[nRowIndex][newindex]=matrix[j][newindex-2]
                newindex+=1
    train_id_list[i][2]=len(matrix)-1

resultList=[]
for x in range(train_id_list[TrainNum-1][1],len(matrix)):   #去掉matrix里面的进站信息，只保留出站信息
    resultList.append(matrix[x].copy())
    for id in TrainIDlist:
        resultList[-1].remove(id)
resultList.sort()

for item in resultList:
    print(" ".join(map(str,item)))

# dfs结合栈
import sys
from collections import deque

def dfs(in_stack, out_stack, current_out):
    # in_stack 还没进站的车  out_stack 已经进站但还没出栈的车    current_out 当前的出站序列
    if not in_stack and not out_stack:
        record.append(current_out)
        return
    if in_stack:
        dfs(in_stack[1:], out_stack+[in_stack[0]], current_out)
    
    # 出站操作：如果栈中有火车可以出站
    if out_stack:
        dfs(in_stack, out_stack[:-1], current_out + [out_stack[-1]])

    

data = sys.stdin.read().splitlines()
trian_list = list(map(int,data[-1].split()))
record = []
# print(trian_list)
dfs(trian_list,[],[]) 
record = sorted(record)
for r in record:
    print(*r)

"""
栈的出栈序列排列问题”或称“卡特兰数问题”：
给定一个数组，该数组中的元素依次入栈。在入栈的过程中，允许在任意时刻进行出栈操作。
问题是：通过这些入栈和出栈操作，最后得到的出栈序列有哪些可能？以及有多少种可能的出栈序列？
使用递归回溯法
"""


def generate_stack_permutations(seq):
    n = len(seq)

    # 存储所有可能的出栈序列
    results = []

    # 递归函数来模拟栈操作
    """该递归函数会造成算力浪费"""

    def backtrack(input_seq, stack, output_seq):
        # 如果整个序列都已入栈并且栈已空，则输出序列是完成的
        if not input_seq and not stack:
            results.append(output_seq[:])
            return

        # 如果输入序列还有元素可入栈
        """
        本步完成了一次输入序列的单元素入栈操作，并对剩下的序列继续调用函数
        最后移除刚刚入栈的元素，回溯到原先的状态
        """
        if input_seq:
            # 模拟入栈操作
            stack.append(input_seq[0])
            backtrack(input_seq[1:], stack, output_seq)
            """回溯法"""
            stack.pop()  # 删除stack最后一个，回溯入栈操作

        # 如果栈中有元素可出栈
        if stack:
            # 模拟出栈操作
            popped = stack.pop()  # 出栈一个元素
            output_seq.append(popped)  # 加入输出序列
            backtrack(input_seq, stack, output_seq)  # 递归
            output_seq.pop()  # 回溯，移除刚加入的元素
            """回溯法"""
            stack.append(popped)  # 回溯堆栈状态

    # 开始递归
    backtrack(seq, [], [])
    return results


n = input()
input_sequence = [int(i) for i in input().split(' ')]
all_permutations = generate_stack_permutations(input_sequence)

# 输出所有可能的出栈序列，字典序排序
all_permutations = sorted(all_permutations)
for permutation in all_permutations:
    print(" ".join([str(i) for i in permutation]))

# 输出总数量
# print("总出栈序列数量:", len(all_permutations))

def updateTrainExitSequence(train_outside,train_inside,all_exit_way,exit_way_arr):
    if(train_outside):
        enter_train = train_outside.pop(0)
        train_inside.append(enter_train)
        updateTrainExitSequence(train_outside,train_inside,all_exit_way,exit_way_arr)
        train_inside.pop()
        train_outside.insert(0,enter_train)
    if(train_inside):
        exit_train = train_inside.pop()
        exit_way_arr.append(exit_train + " ")
        updateTrainExitSequence(train_outside,train_inside,all_exit_way,exit_way_arr)
        exit_way_arr.pop()
        train_inside.append(exit_train)
    if(not train_outside and not train_inside):
        all_exit_way.append("".join(exit_way_arr))


train_num = int(input())
train_outside = input().split()
all_exit_way = []
updateTrainExitSequence(train_outside,[],all_exit_way,[])
all_exit_way.sort()
for exit_way in all_exit_way: print(exit_way)

    该代码核心思想参考其它大神(并非自创)，我这边大概写一下我理解的思路
    n, nums = input(), input().split()
    res = []
    def dfs(w, i, o):

        # 如果没有 待需要进栈的火车 和 需要出栈的火车，证明所有火车都已出栈
        # 需要将都已出栈的火车添加到res
        if not w and not i:
            res.append(' '.join(map(str, o)))

        # 如果有 待需要进栈的火车，那么则安排一辆火车进栈
        if w:
            dfs(w[1:], i + [w[0]], o)

        #如果有进栈的火车，那么可以安排火车出栈
        if i:
            dfs(w, i[:-1], o + [i[-1]])
    dfs(nums, [], [])

    #sorted 按照题目要求，字典序输出
    for i in sorted(res):
        print(i)

n=input().strip()
in_order=input().strip().split(' ')
res=[]

def in_out(station,waiting,out_station):
    if waiting:
        in_out(station+[waiting[0]],waiting[1:],out_station)
    if station:
        in_out(station[:-1],waiting,out_station+[station[-1]])
    if not station and not waiting:
        res.append(out_station)

in_out([],in_order,[])
res.sort()
for i in res:
    print(*i)

n=int(input())
x=list(map(str,input().split()))
rem=[]
def ways(x=[],s=[],o=[]):
    if x==[] and s==[]:
        rem.append(o)
    if x:
        ways(x[1:],s+list(x[0]),o)
    if s:
        ways(x,s[:-1],o+list(s[-1]))

ways(x)
rem=list(sorted(rem))
for i in rem:
    print(*i)

n = input()
ss = input().split()
ss.reverse()
ou = []
def cel(s, i, o):
    if not s and not i:
        ou.append(o)     
        return 
    if s:
        on = o.copy()
        sn = s.copy()
        sn.pop()
        inew = i.copy()
        inew.append(s[-1])
        cel(sn, inew, on)
    if i:
        on = o.copy()
        sn = s.copy()
        inew = i.copy()
        inew.pop()
        on.append(i[-1])
        cel(sn, inew, on)

cel(ss, [], [])

ou.sort()
for i in ou:
    for j in i:
        print(j, end=' ')
    print('')

#此题动态规划解题，等候入站的序列和出站的序列不为空都会有
对应的入站和出站，边界为两者都为空时，将此时用于装出站序列的out列表
加入到出站方案列表中。
def trail(wait,stack,out):
    if not wait and not stack:#边界
        l.append(' '.join(map(str,out)))
    else:
        if wait:#入站
            trail(wait[1:],stack+[wait[0]],out)
        if stack:#出站
            trail(wait,stack[:-1],out+[stack[-1]])


while True:
    try:
        l = []
        n = int(input())
        wait = list(map(int,input().split()))
        trail(wait,[],[])
        l = sorted(l)#排序
        for i in l:
            print(i)
    except:
        break

小白答案都得看几十遍
while True:
    try:
        n = int(input())
        trains = input().strip().split(" ")
        res = []

        def rec_trains(cur_index, in_trains, out_trains):
            # 最后一个火车已经入站，此时只能出站
            print( cur_index,in_trains,out_trains,'/')
            
            if trains[-1] in in_trains:
                res.append(" ".join(out_trains + in_trains[::-1]))
                # print(res,cur_index)
                return
            # 没有火车入站，此时只能入站
            elif in_trains == []:
                rec_trains(cur_index + 1, in_trains + [trains[cur_index]], out_trains)
            else:
                # 出站，当前车站的最后一个火车出战
                rec_trains(cur_index, in_trains[:-1], out_trains + [in_trains[-1]])
                # print(cur_index)
                # 入站，当前的火车入站
                rec_trains(cur_index + 1, in_trains + [trains[cur_index]], out_trains)

        rec_trains(0, [], [])
        res.sort()
        print("\n".join(res))
    except:
        break

python DFS就是香

class Solution:
    def __init__(self):
        self.ans = []

    def dfs(self, wait, stack, leave):
        if len(wait) == 0 and len(stack) == 0:
            self.ans.append(leave)

        if len(wait) > 0:  # 从等待队列中 入栈
            self.dfs(wait[1:], stack + [wait[0]], leave[:])

        if len(stack) > 0:  # 出栈
            self.dfs(wait[:], stack[:-1], leave + [stack[-1]])
        return self.ans

# 处理一些输入输出
if __name__ == '__main__':
    while True:
        try:
            n = input()
            nums = list(map(int, input().split()))
            sol = Solution()
            ret = sol.dfs(nums, [], [])
            for line in sorted(ret):
                print(" ".join(map(str, line)))
        except:
            break