L2-037 包装机 (25 分)-PAT 团体程序设计天梯赛 GPLT

一种自动包装机的结构如图 1 所示。首先机器中有 N 条轨道,放置了一些物品。轨道下面有一个筐。当某条轨道的按钮被按下时,活塞向左推动,将轨道尽头的一件物品推落筐中。当 0 号按钮被按下时,机械手将抓取筐顶部的一件物品,放到流水线上。图 2 显示了顺序按下按钮 3、2、3、0、1、2、0 后包装机的状态。

一种特殊情况是,因为筐的容量是有限的,当筐已经满了,但仍然有某条轨道的按钮被按下时,系统应强制启动 0 号键,先从筐里抓出一件物品,再将对应轨道的物品推落。此外,如果轨道已经空了,再按对应的按钮不会发生任何事;同样的,如果筐是空的,按 0 号按钮也不会发生任何事。

现给定一系列按钮操作,请你依次列出流水线上的物品。

输入格式:
输入第一行给出 3 个正整数 N(≤100)、M(≤1000)和 S​max​​(≤100),分别为轨道的条数(于是轨道从 1 到 N 编号)、每条轨道初始放置的物品数量、以及筐的最大容量。随后 N 行,每行给出 M 个英文大写字母,表示每条轨道的初始物品摆放。

最后一行给出一系列数字,顺序对应被按下的按钮编号,直到 −1 标志输入结束,这个数字不要处理。数字间以空格分隔。题目保证至少会取出一件物品放在流水线上。

输出格式:
在一行中顺序输出流水线上的物品,不得有任何空格。

输入样例:
3 4 4
GPLT
PATA
OMSA
3 2 3 0 1 2 0 2 2 0 -1

输出样例:
MATA

分析:Q[i]内保存每个轨道上的商品,St保存当前筐的状态~接下来按题意进行模拟操作就可以了,注意0操作前判断St是否为空,其余操作前判断相对应的Q[i]是否为空~

L2-034 口罩发放 (25 分)-PAT 团体程序设计天梯赛 GPLT

为了抗击来势汹汹的 COVID19 新型冠状病毒,全国各地均启动了各项措施控制疫情发展,其中一个重要的环节是口罩的发放。

某市出于给市民发放口罩的需要,推出了一款小程序让市民填写信息,方便工作的开展。小程序收集了各种信息,包括市民的姓名、身份证、身体情况、提交时间等,但因为数据量太大,需要根据一定规则进行筛选和处理,请你编写程序,按照给定规则输出口罩的寄送名单。

输入格式:
输入第一行是两个正整数 D 和 P(1≤D,P≤30),表示有 D 天的数据,市民两次获得口罩的时间至少需要间隔 P 天。

接下来 D 块数据,每块给出一天的申请信息。第 i 块数据(i=1,⋯,D)的第一行是两个整数 T​i 和 S​i(1 ≤ Ti,S​i ≤ 1000),表示在第 i 天有 Ti 条申请,总共有 Si个口罩发放名额。随后 Ti行,每行给出一条申请信息,格式如下:

姓名 身份证号 身体情况 提交时间

给定数据约束如下:

姓名 是一个长度不超过 10 的不包含空格的非空字符串;
身份证号 是一个长度不超过 20 的非空字符串;
身体情况 是 0 或者 1,0 表示自觉良好,1 表示有相关症状;
提交时间 是 hh:mm,为24小时时间(由 00:00 到 23:59。例如 09:08。)。注意,给定的记录的提交时间不一定有序;
身份证号 各不相同,同一个身份证号被认为是同一个人,数据保证同一个身份证号姓名是相同的。

能发放口罩的记录要求如下:

身份证号 必须是 18 位的数字(可以包含前导0);
同一个身份证号若在第 i 天申请成功,则接下来的 P 天不能再次申请。也就是说,若第 i 天申请成功,则等到第 i+P+1 天才能再次申请;
在上面两条都符合的情况下,按照提交时间的先后顺序发放,直至全部记录处理完毕或 S​i个名额用完。如果提交时间相同,则按照在列表中出现的先后顺序决定。

输出格式:
对于每一天的申请记录,每行输出一位得到口罩的人的姓名及身份证号,用一个空格隔开。顺序按照发放顺序确定。

在输出完发放记录后,你还需要输出有合法记录的、身体状况为 1 的申请人的姓名及身份证号,用空格隔开。顺序按照申请记录中出现的顺序确定,同一个人只需要输出一次。

输入样例:
4 2
5 3
A 123456789012345670 1 13:58
B 123456789012345671 0 13:58
C 12345678901234567 0 13:22
D 123456789012345672 0 03:24
C 123456789012345673 0 13:59
4 3
A 123456789012345670 1 13:58
E 123456789012345674 0 13:59
C 123456789012345673 0 13:59
F F 0 14:00
1 3
E 123456789012345674 1 13:58
1 1
A 123456789012345670 0 14:11

输出样例:
D 123456789012345672
A 123456789012345670
B 123456789012345671
E 123456789012345674
C 123456789012345673
A 123456789012345670
A 123456789012345670
E 123456789012345674

样例解释:
输出中,第一行到第三行是第一天的部分;第四、五行是第二天的部分;第三天没有符合要求的市民;第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。

题意:给一堆数据,要求输出每天可以发放到口罩的人,以及总的生病的人数。但是前提是他们的身份证合法,如果是假的身份证,可能是假人或者坏人,不能给他们发口罩(๑• . •๑)

分析:首先用结构体node作为输入的申请信息的基本结构,将输入的申请信息记录在Record中,同时用j标注这是今天的第几次申请。isIllegal函数验证其身份证的合法性,如果不合法就把它的名字改成空用以标记非法用户。lastGet中储存上次领到口罩的时间。ill记录合法的生过病的人,gotten记录是否已经添加到合法生病名单中。最后检查所有合法用户,并检查距离上一次领口罩是否间隔P天,后完成口罩发放~

L2-036 网红点打卡攻略 (25 分)-PAT 团体程序设计天梯赛 GPLT

一个旅游景点,如果被带火了的话,就被称为“网红点”。大家来网红点游玩,俗称“打卡”。在各个网红点打卡的快(省)乐(钱)方法称为“攻略”。你的任务就是从一大堆攻略中,找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。

输入格式:
首先第一行给出两个正整数:网红点的个数 N(1<N≤200)和网红点之间通路的条数 M。随后 M 行,每行给出有通路的两个网红点、以及这条路上的旅行花费(为正整数),格式为“网红点1 网红点2 费用”,其中网红点从 1 到 N 编号;同时也给出你家到某些网红点的花费,格式相同,其中你家的编号固定为 0。

再下一行给出一个正整数 K,是待检验的攻略的数量。随后 K 行,每行给出一条待检攻略,格式为:n V1 V2⋯ V​n
​​其中 n(≤200) 是攻略中的网红点数,V​i是路径上的网红点编号。这里假设你从家里出发,从 V​1 开始打卡,最后从 Vn​​ 回家。

输出格式:
在第一行输出满足要求的攻略的个数。

在第二行中,首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号(从 1 开始),然后输出这个攻略的总路费,其间以一个空格分隔。如果这样的攻略不唯一,则输出序号最小的那个。

题目保证至少存在一个有效攻略,并且总路费不超过 10​9​​ 。

输入样例:
6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

输出样例:
3
5 11

样例说明:
第 2、3、4、6 条都不满足攻略的基本要求,即不能做到从家里出发,在每个网红点打卡仅一次,且能回到家里。所以满足条件的攻略有 3 条。

第 1 条攻略的总路费是:(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14;

第 5 条攻略的总路费同理可算得:1 + 1 + 1 + 2 + 3 + 1 + 2 = 11,是一条更省钱的攻略;

第 7 条攻略的总路费同理可算得:2 + 1 + 1 + 2 + 2 + 2 + 1 = 11,与第 5 条花费相同,但序号较大,所以不输出。

分析:在Edge[u][v]中存储u到v的花费,在每一次询问中,Path中储存攻略路径,因为起始和终点都要为0号点,所以将 Path[0] 与Path[N + 1] 置为0~判断攻略中城市数n与总城市数N是否相等,如果不相等则不满足要求~

Has[i]标记第i个点是否出现过,如果出现过2次,那么也是不满足要求~

之后判断路径上两点之间是否有边相连,没有的话也表示改路径不合法,有的话就用累加到cost中~Ansnum表示总的合法路径,Ansid记录最少划分路径的编号,Anscost记录最少划分路径的费用~

L2-035 完全二叉树的层序遍历 (25 分)-PAT 团体程序设计天梯赛 GPLT

一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是完美二叉树。对于深度为 D 的,有 N 个结点的二叉树,若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点,这样的树就是完全二叉树。

给定一棵完全二叉树的后序遍历,请你给出这棵树的层序遍历结果。

输入格式:
输入在第一行中给出正整数 N(≤30),即树中结点个数。第二行给出后序遍历序列,为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。

输出格式:
在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔,行首尾不得有多余空格。

输入样例:
8
91 71 2 34 10 15 55 18

输出样例:
1

分析:在In中保存输入的后序遍历序列,在dfs保存从根节点开始按层序遍历序列的序号。深度优先搜索,index标表示当前节点,大于n则返回。按照完全二叉树的遍历原理进行后序遍历,先进入左右子树(编号为index*2 和 index*2+1,即index右移1位,和index右移1位+1),cnt为后序遍历的位置标记,并将当前所在的后序遍历的元素,填入dfs[index]内~

L2-033 简单计算器 (25 分)-PAT 团体程序设计天梯赛 GPLT

本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。如上图所示,计算器由两个堆栈组成,一个堆栈 S1存放数字,另一个堆栈 S2存放运算符。计算器的最下方有一个等号键,每次按下这个键,计算器就执行以下操作:

1、从 S1中弹出两个数字,顺序为 n1和 n2;
2、从 S2中弹出一个运算符 op;执行计算 n2 op n1;
3、将得到的结果压回 S1。
4、直到两个堆栈都为空时,计算结束,最后的结果将显示在屏幕上。

输入格式:
输入首先在第一行给出正整数 N(1<N≤103),为 S1​中数字的个数。

第二行给出 N 个绝对值不超过 100 的整数;第三行给出 N−1 个运算符 —— 这里仅考虑 +、-、*、/ 这四种运算。一行中的数字和符号都以空格分隔。

输出格式:
将输入的数字和运算符按给定顺序分别压入堆栈 S​1和 S2,将执行计算的最后结果输出。注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过 109 。

如果执行除法时出现分母为零的非法操作,则在一行中输出:ERROR: X/0,其中 X 是当时的分子。然后结束程序。

输入样例 1:
5
40 5 8 3 2
/ * – +

输出样例 1:
2

输入样例 2:
5
2 5 8 4 4
* / – +

输出样例 2:
ERROR: 5/0

分析:使用In存储输入数字,Record存储运算符。因为模拟堆栈,所以输入从n-1开始反向输入,Sum存储最终答案~

L2-032 彩虹瓶 (25 分)-PAT 团体程序设计天梯赛 GPLT

彩虹瓶的制作过程(并不)是这样的:先把一大批空瓶铺放在装填场地上,然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。

假设彩虹瓶里要按顺序装 N 种颜色的小球(不妨将顺序就编号为 1 到 N)。现在工厂里有每种颜色的小球各一箱,工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色,就直接拆箱装填;如果不是,就把箱子先码放在一个临时货架上,码放的方法就是一箱一箱堆上去。当一种颜色装填完以后,先看看货架顶端的一箱是不是下一个要装填的颜色,如果是就取下来装填,否则去工厂里再搬一箱过来。

如果工厂里发货的顺序比较好,工人就可以顺利地完成装填。例如要按顺序装填 7 种颜色,工厂按照 7、6、1、3、2、5、4 这个顺序发货,则工人先拿到 7、6 两种不能装填的颜色,将其按照 7 在下、6 在上的顺序堆在货架上;拿到 1 时可以直接装填;拿到 3 时又得临时码放在 6 号颜色箱上;拿到 2 时可以直接装填;随后从货架顶取下 3 进行装填;然后拿到 5,临时码放到 6 上面;最后取了 4 号颜色直接装填;剩下的工作就是顺序从货架上取下 5、6、7 依次装填。

但如果工厂按照 3、1、5、4、2、6、7 这个顺序发货,工人就必须要愤怒地折腾货架了,因为装填完 2 号颜色以后,不把货架上的多个箱子搬下来就拿不到 3 号箱,就不可能顺利完成任务。

另外,货架的容量有限,如果要堆积的货物超过容量,工人也没办法顺利完成任务。例如工厂按照 7、6、5、4、3、2、1 这个顺序发货,如果货架够高,能码放 6 只箱子,那还是可以顺利完工的;但如果货架只能码放 5 只箱子,工人就又要愤怒了……

本题就请你判断一下,工厂的发货顺序能否让工人顺利完成任务。

输入格式:
输入首先在第一行给出 3 个正整数,分别是彩虹瓶的颜色数量 N(1<N≤103)、临时货架的容量 M(<N)、以及需要判断的发货顺序的数量 K。

随后 K 行,每行给出 N 个数字,是 1 到N 的一个排列,对应工厂的发货顺序。一行中的数字都以空格分隔。

输出格式:
对每个发货顺序,如果工人可以愉快完工,就在一行中输出 YES;否则输出 NO。

输入样例:
7 5 3
7 6 1 3 2 5 4
3 1 5 4 2 6 7
7 6 5 4 3 2 1

输出样例:
YES
NO
NO

分析:need表示当前所需要装填箱子的颜色编号,这里使用了一个名叫Stack的数字来模拟堆栈操作,用num来表示堆顶位置。在模拟过程中,如果当前输入等于需要填装的编号,那么需要进一步判断堆顶元素是否是下一个需要的编号。只有在堆容量内才会继续向Stack压入新元素,最后判断num是否回归到初始值,则可判断整体是否可以愉快地完工~