L3-009 长城 (30 分)-PAT 团体程序设计天梯赛 GPLT

正如我们所知,中国古代长城的建造是为了抵御外敌入侵。在长城上,建造了许多烽火台。每个烽火台都监视着一个特定的地区范围。一旦某个地区有外敌入侵,值守在对应烽火台上的士兵就会将敌情通报给周围的烽火台,并迅速接力地传递到总部。

现在如图1所示,若水平为南北方向、垂直为海拔高度方向,假设长城就是依次相联的一系列线段,而且在此范围内的任一垂直线与这些线段有且仅有唯一的交点。

进一步地,假设烽火台只能建造在线段的端点处。我们认为烽火台本身是没有高度的,每个烽火台只负责向北方(图1中向左)瞭望,而且一旦有外敌入侵,只要敌人与烽火台之间未被山体遮挡,哨兵就会立即察觉。当然,按照这一军规,对于南侧的敌情各烽火台并不负责任。一旦哨兵发现敌情,他就会立即以狼烟或烽火的形式,向其南方的烽火台传递警报,直到位于最南侧的总部。

以图2中的长城为例,负责守卫的四个烽火台用蓝白圆点示意,最南侧的总部用红色圆点示意。如果红色星形标示的地方出现敌情,将被哨兵们发现并沿红色折线将警报传递到总部。当然,就这个例子而言只需两个烽火台的协作,但其他位置的敌情可能需要更多。

然而反过来,即便这里的4个烽火台全部参与,依然有不能覆盖的(黄色)区域。

另外,为避免歧义,我们在这里约定,与某个烽火台的视线刚好相切的区域都认为可以被该烽火台所监视。以图3中的长城为例,若A、B、C、D点均共线,且在D点设置一处烽火台,则A、B、C以及线段BC上的任何一点都在该烽火台的监视范围之内。

好了,倘若你是秦始皇的太尉,为不致出现更多孟姜女式的悲剧,如何在保证长城安全的前提下,使消耗的民力(建造的烽火台)最少呢?

输入格式:

输入在第一行给出一个正整数N(3 ≤ N ≤105),即刻画长城边缘的折线顶点(含起点和终点)数。随后N行,每行给出一个顶点的xy坐标,其间以空格分隔。注意顶点从南到北依次给出,第一个顶点为总部所在位置。坐标为区间[−109,109)内的整数,且没有重合点。

输出格式:

在一行中输出所需建造烽火台(不含总部)的最少数目。

输入样例:

10
67 32
48 -49
32 53
22 -44
19 22
11 40
10 -65
-1 -23
-3 31
-7 59

输出样例:

2

分析:根据题目易知,我们需要判断一共有几个凸出来的点。可以借助堆栈结构,从南到北判断每个点是否为凸出点,不是的话说明可以被前面某个烽火台观测到,直接弹出就不用管了。每次判断三个点,当前输入点l,上一个留在堆栈内的待观察点mid和再前面一个点r,如果直线lr的斜率是否大于等于(题目特殊规定)直线lmid的斜率,是的话说明不是凸出来点。当栈中存在大于2个的点时,表示mid点为烽火。top表示栈顶,X,Y中存储折线顶点坐标,tower为模拟堆栈数组,vis数组中记录某个点是否被标记为烽火台,函数isConcave判断是否是凹点或平行中点~

L3-006 迎风一刀斩 (30 分)-PAT 团体程序设计天梯赛 GPLT

迎着一面矩形的大旗一刀斩下,如果你的刀够快的话,这笔直一刀可以切出两块多边形的残片。反过来说,如果有人拿着两块残片来吹牛,说这是自己迎风一刀斩落的,你能检查一下这是不是真的吗?

注意摆在你面前的两个多边形可不一定是端端正正摆好的,它们可能被平移、被旋转(逆时针90度、180度、或270度),或者被(镜像)翻面。

这里假设原始大旗的四边都与坐标轴是平行的。

输入格式:

输入第一行给出一个正整数N(≤20),随后给出N对多边形。每个多边形按下列格式给出:

kx1​y1​⋯xkyk

其中k(2<k≤10)是多边形顶点个数;(xi​,yi​)(0≤xi​,yi​≤108)是顶点坐标,按照顺时针或逆时针的顺序给出。

注意:题目保证没有多余顶点。即每个多边形的顶点都是不重复的,任意3个相邻顶点不共线。

输出格式:

对每一对多边形,输出YES或者NO

输入样例:

8
3 0 0 1 0 1 1
3 0 0 1 1 0 1
3 0 0 1 0 1 1
3 0 0 1 1 0 2
4 0 4 1 4 1 0 0 0
4 4 0 4 1 0 1 0 0
3 0 0 1 1 0 1
4 2 3 1 4 1 7 2 7
5 10 10 10 12 12 12 14 11 14 10
3 28 35 29 35 29 37
3 7 9 8 11 8 9
5 87 26 92 26 92 23 90 22 87 22
5 0 0 2 0 1 1 1 2 0 2
4 0 0 1 1 2 1 2 0
4 0 0 0 1 1 1 2 0
4 0 0 0 1 1 1 2 0

输出样例:

YES
NO
YES
YES
YES
YES
NO
YES

分析:要让两个图形能够拼接成矩形只有四种情况 1.两个直角三角形 2.两个矩形 3.一个三角形配一个五角形 4.两个直角梯形。由于题目特殊的旋转限制,直角边只会和x轴或y轴平行。非矩形情况首先判断是不是有 边数 – 1 的直角边,然后判断两个图形斜边是否相等。四边形则先判断是否是两个直角梯形,是的话高且斜边都相等则符合,如果是两个矩形 任意一边相等即可。k1表示第一个图形的斜率,k2表示第二个图形的斜率,SLength中储存较短的平行于x轴的边,LLength中储存较长的平行于x轴的边,SWidth中储存较短的平行于y轴的边,LWidth中储存较长的平行于y轴的边,res表示有多少条直角边,dif为两点距离~

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的容量等于纸片数量,则表示已经完成所有匹配,输出结果并返回~