PAT | 蓝桥 | LeetCode学习路径 & 刷题经验

你们要不要考虑也节省一下时间~

这份PDF题目叫做《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验 by 柳婼》,希望可以帮助学习算法路上的小可爱们节约时间、少踩一些坑、多走一些捷径~

一年前看过我blog的人应该知道,我曾经开通过知乎的值乎付费咨询,大概开通了大半年时间,期间也收到了很多咨询,绝大多数提问的话题都是“PAT、蓝桥、LeetCode怎么学如何刷题”,我也一一认真做了回答(绝大多数回答都在半小时以上),但是值乎的回答只能够发布语音,而且有回答时效,提问也有字数限制,后来问的人越来越多,我一天要花数小时在知乎回答上,而且回答的都是几乎相同的问题…对于分享算法经验来说,短短半小时确实不够,很多观点无法详细解释缘由,值乎一对一咨询确实不是一个很好的分享算法经验的平台,听者也很难短时间形成对问题答案的清晰理解,所以后来半年前我就关闭了知乎咨询的功能~不过还是有很多小可爱通过各种渠道向我咨询经验等问题,所以我花了好多天时间将这些问题的回答、刷题笔记、经验全都整理在了一份PDF中~这些问题包括:

里面不仅有关于这些竞赛的介绍、应该看哪些书、如何刷题,还有我自己刷算法过程中整理的笔记,目录如下:

这份经验一共3万7千字(想当年800字的高考作文都写那么辛苦…)在算法路上,我能帮的只有这么多了…希望能帮助你们少走很多弯路,少踩很多坑~剩下的就是靠你们自己刷题啦~还和离线版订阅获取的方式一样…打赏29元并备注邮箱号即可…打赏二维码在每篇博客文章点进去的最下面…24小时内发送到邮箱…(一般一两个小时就收到了~)时间仓促,后期还会对这份文档的内容进行扩充完善…到时候有版本更新还会继续发送到邮箱中~感谢支持与信任~

L3-023 计算图 (30 分)–PAT 团体程序设计天梯赛 GPLT

“计算图”(computational graph)是现代深度学习系统的基础执行引擎,提供了一种表示任意数学表达式的方法,例如用有向无环图表示的神经网络。 图中的节点表示基本操作或输入变量,边表示节点之间的中间值的依赖性。 例如,下图就是一个函数 f(x1​,x2​)=lnx1​+x1​x2​−sinx2​ 的计算图。

现在给定一个计算图,请你根据所有输入变量计算函数值及其偏导数(即梯度)。 例如,给定输入x1​=2,x2​=5,上述计算图获得函数值 f(2,5)=ln(2)+2×5−sin(5)=11.652;并且根据微分链式法则,上图得到的梯度 ∇f=[∂f/∂x1​,∂f/∂x2​]=[1/x1​+x2​,x1​−cosx2​]=[5.500,1.716]。

知道你已经把微积分忘了,所以这里只要求你处理几个简单的算子:加法、减法、乘法、指数(ex,即编程语言中的 exp(x) 函数)、对数(lnx,即编程语言中的 log(x) 函数)和正弦函数(sinx,即编程语言中的 sin(x) 函数)。

友情提醒:

  • 常数的导数是 0;x 的导数是 1;ex 的导数还是 ex;lnx 的导数是 1/x;sinx 的导数是 cosx
  • 回顾一下什么是偏导数:在数学中,一个多变量的函数的偏导数,就是它关于其中一个变量的导数而保持其他变量恒定。在上面的例子中,当我们对 x1​ 求偏导数 ∂f/∂x1​ 时,就将 x2​ 当成常数,所以得到 lnx1​ 的导数是 1/x1​,x1​x2​ 的导数是 x2​,sinx2​ 的导数是 0。
  • 回顾一下链式法则:复合函数的导数是构成复合这有限个函数在相应点的导数的乘积,即若有 u=f(y),y=g(x),则 du/dx=du/dydy/dx。例如对 sin(lnx) 求导,就得到 cos(lnx)⋅(1/x)。

如果你注意观察,可以发现在计算图中,计算函数值是一个从左向右进行的计算,而计算偏导数则正好相反。

输入格式:

输入在第一行给出正整数 N(≤5×104),为计算图中的顶点数。

以下 N 行,第 i 行给出第 i 个顶点的信息,其中 i=0,1,⋯,N−1。第一个值是顶点的类型编号,分别为:

  • 0 代表输入变量
  • 1 代表加法,对应 x1​+x2​
  • 2 代表减法,对应 x1​−x2​
  • 3 代表乘法,对应 x1​×x2​
  • 4 代表指数,对应 ex
  • 5 代表对数,对应 lnx
  • 6 代表正弦函数,对应 sinx

对于输入变量,后面会跟它的双精度浮点数值;对于单目算子,后面会跟它对应的单个变量的顶点编号(编号从 0 开始);对于双目算子,后面会跟它对应两个变量的顶点编号。

题目保证只有一个输出顶点(即没有出边的顶点,例如上图最右边的 -),且计算过程不会超过双精度浮点数的计算精度范围。

输出格式:

首先在第一行输出给定计算图的函数值。在第二行顺序输出函数对于每个变量的偏导数的值,其间以一个空格分隔,行首尾不得有多余空格。偏导数的输出顺序与输入变量的出现顺序相同。输出小数点后 3 位。

输入样例:

7
0 2.0
0 5.0
5 0
3 0 1
6 1
1 2 3
2 5 4

输出样例:

11.652
5.500 1.716

分析:结构体A中存储相关节点信息,de[i]表示第i个点是否被其他节点调用操作到,使用deal做dfs操作来根据题意进行题目的模拟运行,其中,c为1表示求导,c为0表示正常晕眩,index表示当前节点信息,to为求偏导数得目标,Record则是一个dfs下的记忆优化,start为一个可以作为出发点的节点。依题意输入数据后,遍历找出一个出发点节点,然后直接丢到deal函数中即可得到答案~注意导数运算的相关规则~

 

L3-022 地铁一日游 (30 分)-PAT 团体程序设计天梯赛 GPLT

森森喜欢坐地铁。这个假期,他终于来到了传说中的地铁之城——魔都,打算好好过一把坐地铁的瘾!

魔都地铁的计价规则是:起步价 2 元,出发站与到达站的最短距离(即计费距离)每 K 公里增加 1 元车费。

例如取 K = 10,动安寺站离魔都绿桥站为 40 公里,则车费为 2 + 4 = 6 元。

为了获得最大的满足感,森森决定用以下的方式坐地铁:在某一站上车(不妨设为地铁站 A),则对于所有车费相同的到达站,森森只会在计费距离最远的站或线路末端站点出站,然后用森森美图 App 在站点外拍一张认证照,再按同样的方式前往下一个站点。

坐着坐着,森森突然好奇起来:在给定出发站的情况下(在出发时森森也会拍一张照),他的整个旅程中能够留下哪些站点的认证照?

地铁是铁路运输的一种形式,指在地下运行为主的城市轨道交通系统。一般来说,地铁由若干个站点组成,并有多条不同的线路双向行驶,可类比公交车,当两条或更多条线路经过同一个站点时,可进行换乘,更换自己所乘坐的线路。举例来说,魔都 1 号线和 2 号线都经过人民广场站,则乘坐 1 号线到达人民广场时就可以换乘到 2 号线前往 2 号线的各个站点。换乘不需出站(也拍不到认证照),因此森森乘坐地铁时换乘不受限制。

输入格式:
输入第一行是三个正整数 N、M 和 K,表示魔都地铁有 N 个车站 (1 ≤ N ≤ 200),M 条线路 (1 ≤ M ≤ 1500),最短距离每超过 K 公里 (1 ≤ K ≤ 106),加 1 元车费。

接下来 M 行,每行由以下格式组成:

<站点1><空格><距离><空格><站点2><空格><距离><空格><站点3> … <站点X-1><空格><距离><空格><站点X>

其中站点是一个 1 到 N 的编号;两个站点编号之间的距离指两个站在该线路上的距离。两站之间距离是一个不大于 106 的正整数。一条线路上的站点互不相同。

注意:两个站之间可能有多条直接连接的线路,且距离不一定相等。

再接下来有一个正整数 Q (1 ≤ Q ≤ 200),表示森森尝试从 Q 个站点出发。

最后有 Q 行,每行一个正整数 Xi**,表示森森尝试从编号为 **Xi 的站点出发。

输出格式:
对于森森每个尝试的站点,输出一行若干个整数,表示能够到达的站点编号。站点编号从小到大排序。

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

输出样例:
1 2 4 5 6
1 2 3 4 5 6
1 2 4 5 6
1 2 4 5 6

分析:Ter[i]数组表示第i个节点是不是两端的站点,Station中存储站点i直接能留下认证照的站点,Ans中存储站点i最终能留下认证照的站点,Fur_Dis中存储每个花费下能到达的最远距离,由于所有票价都有一个2的基础,所以加布加都可以。刚开始将地图的信息输入至Edge中,并记录两侧端点的信息。由于相同的两个站点也可能有不同距离的路线,所以这里需要取最小值。然后用Floyd最短路算法求出两个站点之间最短的路线。然后再遍历出每个节点到达的所有距离需要多少花费,如果该花费是最小值,说明该站点可以拍照。最后再通过简单的dfs,找出一个站点能以其他可换乘的车站作为中转点,可以到达的所有站点~

L3-019 代码排版 (30 分)-PAT 团体程序设计天梯赛 GPLT

某编程大赛中设计有一个挑战环节,选手可以查看其他选手的代码,发现错误后,提交一组测试数据将对手挑落马下。为了减小被挑战的几率,有些选手会故意将代码写得很难看懂,比如把所有回车去掉,提交所有内容都在一行的程序,令挑战者望而生畏。

为了对付这种选手,现请你编写一个代码排版程序,将写成一行的程序重新排版。当然要写一个完美的排版程序可太难了,这里只简单地要求处理C语言里的for、while、if-else这三种特殊结构,而将其他所有句子都当成顺序执行的语句处理。输出的要求如下:

  • 默认程序起始没有缩进;每一级缩进是 2 个空格;
  • 每行开头除了规定的缩进空格外,不输出多余的空格;
  • 顺序执行的程序体是以分号“;”结尾的,遇到分号就换行;
  • 在一对大括号“{”和“}”中的程序体输出时,两端的大括号单独占一行,内部程序体每行加一级缩进,即:
 
  • for的格式为:
 
  • while的格式为:
 
  • if-else的格式为:

输入格式:

输入在一行中给出不超过 331 个字符的非空字符串,以回车结束。题目保证输入的是一个语法正确、可以正常编译运行的 main 函数模块。

输出格式:

按题面要求的格式,输出排版后的程序。

输入样例:

输出样例:

 
分析:point表示当前处理的文本位置,space储存但前需要在行首加多少空格,mark表示自动补充的大括号数量,use表示是否开启了大括号自动补充。在Function函数内,集成了’跳过无效空格’、’空格输出’、’关键字匹配’以及’补充的打括号补全’功能,很好用。刚开始我们需要将int main ()部分单独输出,因为该部分可能存在不可移出的空格。然后对于剩下的主体部分,主要分成三个模块处理——’大括号匹配整理’、’关键字匹配整理’以及’其余代码匹配整理’。特别注意在有些关键字后面添加了代码没有自带大括号,需要自己去补全并记录相关数量信息。在space为0时结束程序,剩下的就是简单的模拟即可~

L3-029 还原文件 (30 分)-PAT 团体程序设计天梯赛 GPLT

一份重要文件被撕成两半,其中一半还被送进了碎纸机。我们将碎纸机里找到的纸条进行编号,如图 1 所示。然后根据断口的折线形状跟没有切碎的半张纸进行匹配,最后还原成图 2 的样子。要求你输出还原后纸条的正确拼接顺序。

输入格式:
输入首先在第一行中给出一个正整数 N(1<N≤10​5​​),为没有切碎的半张纸上断口折线角点的个数;随后一行给出从左到右 N 个折线角点的高度值(均为不超过 100 的非负整数)。

随后一行给出一个正整数 M(≤100),为碎纸机里的纸条数量。接下去有 M 行,其中第 i 行给出编号为 i(1≤i≤M)的纸条的断口信息,格式为:
K h[1] h[2] … h[K]
其中 K 是断口折线角点的个数(不超过 104 +1),后面是从左到右 K 个折线角点的高度值。为简单起见,这个“高度”跟没有切碎的半张纸上断口折线角点的高度是一致的。

输出格式:
在一行中输出还原后纸条的正确拼接顺序。纸条编号间以一个空格分隔,行首尾不得有多余空格。题目数据保证存在唯一解。

输入样例:
17
95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80
6
4 68 58 58 80
3 81 68 68
3 95 70 80
3 68 60 80
5 80 72 88 81 81
4 80 97 97 68

输出样例:
3 6 1 5 2 4

分析:h[i]存储第i个折线角点的高度,frag[i]存储第i个纸条碎片的信息。通过DFS从没有切碎的纸片最左端开始尝试所有纸条碎片的匹配,p表示当前所需要匹配的碎片左侧在未碎纸片上的位置,将匹配上的纸条碎片编号添加到Ans中记录,并使用vis标记是否已经匹配上了,如果Ans的容量等于纸片数量,则表示已经完成所有匹配,输出结果并返回~

L3-028 森森旅游 (30 分)-PAT 团体程序设计天梯赛 GPLT

好久没出去旅游啦!森森决定去 Z 省旅游一下。

Z 省有 n 座城市(从 1 到 n 编号)以及 m 条连接两座城市的有向旅行线路(例如自驾、长途汽车、火车、飞机、轮船等),每次经过一条旅行线路时都需要支付该线路的费用(但这个收费标准可能不止一种,例如车票跟机票一般不是一个价格)。

Z 省为了鼓励大家在省内多逛逛,推出了旅游金计划:在 i 号城市可以用 1 元现金兑换 ai 元旅游金(只要现金足够,可以无限次兑换)。城市间的交通即可以使用现金支付路费,也可以用旅游金支付。具体来说,当通过第 j 条旅行线路时,可以用 cj 元现金或 dj 元旅游金支付路费。注意: 每次只能选择一种支付方式,不可同时使用现金和旅游金混合支付。但对于不同的线路,旅客可以自由选择不同的支付方式。

森森决定从 1 号城市出发,到 n 号城市去。他打算在出发前准备一些现金,并在途中的某个城市将剩余现金 全部 换成旅游金后继续旅游,直到到达 n 号城市为止。当然,他也可以选择在 1 号城市就兑换旅游金,或全部使用现金完成旅程。

Z 省政府会根据每个城市参与活动的情况调整汇率(即调整在某个城市 1 元现金能换多少旅游金)。现在你需要帮助森森计算一下,在每次调整之后最少需要携带多少现金才能完成他的旅程。

输入格式:
输入在第一行给出三个整数 n,m 与 q(1≤n≤105​,1≤m≤2×105,1≤q≤105),依次表示城市的数量、旅行线路的数量以及汇率调整的次数。

接下来 m 行,每行给出四个整数 u,v,c 与 d(1≤u,v≤n,1≤c,d≤109),表示一条从 u 号城市通向 v 号城市的有向旅行线路。每次通过该线路需要支付 c 元现金或 d 元旅游金。数字间以空格分隔。输入保证从 1 号城市出发,一定可以通过若干条线路到达 n 号城市,但两城市间的旅行线路可能不止一条,对应不同的收费标准;也允许在城市内部游玩(即 u 和 v 相同)。

接下来的一行输入 n 个整数 a1,a2,⋯,an(1≤ai≤109),其中 ai表示一开始在 i 号城市能用 1 元现金兑换 ai个旅游金。数字间以空格分隔。

接下来 q 行描述汇率的调整。第 i 行输入两个整数 xi 与 ai′(1≤xi≤n,1≤a
​i′ ≤109),表示第 i 次汇率调整后,xi号城市能用 1 元现金兑换 ai′个旅游金,而其它城市旅游金汇率不变。请注意:每次汇率调整都是在上一次汇率调整的基础上进行的。

输出格式:
对每一次汇率调整,在对应的一行中输出调整后森森至少需要准备多少现金,才能按他的计划从 1 号城市旅行到 n 号城市。

再次提醒:如果森森决定在途中的某个城市兑换旅游金,那么他必须将剩余现金全部、一次性兑换,剩下的旅途将完全使用旅游金支付。

输入样例:
6 11 3
1 2 3 5
1 3 8 4
2 4 4 6
3 1 8 6
1 3 10 8
2 3 2 8
3 4 5 3
3 5 10 7
3 3 2 3
4 6 10 12
5 6 10 6
3 4 5 2 5 100
1 2
2 1
1 17

输出样例:
8
8
1

样例解释:
对于第一次汇率调整,森森可以沿着 1→2→4→6 的线路旅行,并在 2 号城市兑换旅游金;

对于第二次汇率调整,森森可以沿着 1→2→3→4→6 的线路旅行,并在 3 号城市兑换旅游金;

对于第三次汇率调整,森森可以沿着 1→3→5→6 的线路旅行,并在 1 号城市兑换旅游金。

分析:主体思路是,用Dijskra最短路算法分别算出:
1.使用现金从城市1出发,到达所有城市的最小花费(储存在cashD内)
2.使用旅游金从城市n出发,到达所有城市的最小花费(储存在voucherD内)
这样我们就能通过枚举中转点的方式,得到在第i个城市将现金换成旅游金的情况下所需要的现金总额~就是使用从城市1到达第i个城市所需要的最小现金数 + 从第i个城市到城市n所需要的最小旅游金数所转换成的现金数量,就可以得到在第i个城市兑换所需要的总现金费用,储存在tran[i]内~
huan[i]中储存第i个城市的汇率,cashE[i]和voucherE[i]中储分别储存使用现金和旅游金到达i可下一个城市的花费。最后将所有中转点所要用的花费储存在一个可以有重复值的multiset容器 minCost 中。最后在更新汇率时,将更新前花费从 minCost 中删除,并插入新值,然后输出 minCost 中的最小值就是答案啦~

注意:如果某点使用现金或旅游金不可达,那么该点的tran值则设置为0,在更新时该点也无需操作~

L3-025 那就别担心了 (30 分)-PAT 团体程序设计天梯赛 GPLT

下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题,其实都不用担心。

博主将这种逻辑推演称为“逻辑自洽”,即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题(开玩笑的,千万别以为这是真正的逻辑自洽的定义……)。现给定一个更为复杂的逻辑推理图,本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的,以及存在多少种不同的推理路径。例如上图,从“你遇到难题了吗?”到“那就别担心了”就是一种“逻辑自洽”的推理,一共有 3 条不同的推理路径。

输入格式:
输入首先在一行中给出两个正整数 N(1<N≤500)和 M,分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。

接下来 M 行,每行给出一对命题之间的推理关系,即两个命题的编号 S1 S2,表示可以从 S1 推出 S2。题目保证任意两命题之间只存在最多一种推理关系,且任一命题不能循环自证(即从该命题出发推出该命题自己)。

最后一行给出待检验的两个命题的编号 A B。

输出格式:
在一行中首先输出从 A 到 B 有多少种不同的推理路径,然后输出 Yes 如果推理是“逻辑自洽”的,或 No 如果不是。题目保证输出数据不超过 10​9​​ 。

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

输出样例 1:
3 Yes

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

输出样例 2:
3 No

分析:Edge中储存第i个命题可以推出的命题编号,A、B表示起始路径和终点路径,laneNum[i]储存从第i个命题到第B个命题有多少种不同的推理路径,laneNum[B]的初始值为1。consistency表示推理是否逻辑自洽。通过记忆化dfs从A点开始更新laneNum的值,index表示当前所在的命题编号,如果laneNum[index]为0则表示已经向后搜索过,直接返回其数值即可~将laneNum[index]加上它所有可以到达的后续节点Next的laneNum值,如若某点的laneNum值为0,则表示从A出发到这一命题,不能继续向下推理到命题B,则标记consistency为1~