L3-021 神坛 (30 分)-PAT 团体程序设计天梯赛 GPLT

在古老的迈瑞城,巍然屹立着 n 块神石。长老们商议,选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比,因此神坛的面积越小越好。特殊地,如果有两块神石坐标相同,或者三块神石共线,神坛的面积为 0.000

长老们发现这个问题没有那么简单,于是委托你编程解决这个难题。

输入格式:

输入在第一行给出一个正整数 n(3 ≤ n ≤ 5000)。随后 n 行,每行有两个整数,分别表示神石的横坐标、纵坐标(−109≤ 横坐标、纵坐标 <109)。

输出格式:

在一行中输出神坛的最小面积,四舍五入保留 3 位小数。

输入样例:

8 3 4 2 4 1 1 4 1 0 3 3 0 1 3 4 2

输出样例:

0.500

分析:A中存储神石的点坐标,B中存储去掉枚举点且排序后,两神石的之间的向量值。枚举每一个点作为起始点,按照极坐标将B排序后,按照向量计算中,三角形面积 = 1/2 * |x1y2 – x2y1|,遍历求出最小神坛面积~

L3-020 至多删三个字符 (30 分)-PAT 团体程序设计天梯赛 GPLT

给定一个全部由小写英文字母组成的字符串,允许你至多删掉其中 3 个字符,结果可能有多少种不同的字符串?

输入格式:

输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 106] 内的字符串。

输出格式:

在一行中输出至多删掉其中 3 个字符后不同字符串的个数。

输入样例:

ababcc

输出样例:

25

提示:

删掉 0 个字符得到 “ababcc”。

删掉 1 个字符得到 “babcc”, “aabcc”, “abbcc”, “abacc” 和 “ababc”。

删掉 2 个字符得到 “abcc”, “bbcc”, “bacc”, “babc”, “aacc”, “aabc”, “abbc”, “abac” 和 “abab”。

删掉 3 个字符得到 “abc”, “bcc”, “acc”, “bbc”, “bac”, “bab”, “aac”, “aab”, “abb” 和 “aba”。

分析:一个简单的动态规划题~使用dp[i][j]表示前i个字符串在删除j个字符的情况下能取到多少种情况。由于第i个字符只有删除以及不能删除两种情况,可以得到dp[i][j] = dp[i – 1][j](第i个字符不删,前i-1个字符删除掉j个再加上当前字符能取到的个数) + dp[i – 1][ j – 1](第i个字符删了,前i-1个字符删除掉j-1个能取到的个数)~注意可能存在的重复情况,如liuchuo在dp[6][3]时删除下标为3、4、5的”uch”后得到字符串的与删除下标为4、5、6的”chu”后得到的字符串都为”liu”,所以需要记录当前(下标为i)字符上一次出现的位置last(存在vis数组中),并判断i与last的差是否大于等于目前的j,如果更多的话,就已经不可能受到影响了,故需要减去dp[last – 1][j – (i – last)]的数量。 最后将所有删减情况加起来,得到最终答案~

L3-017 森森快递 (30 分)-PAT 团体程序设计天梯赛 GPLT

森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N−1)编号。由于道路限制,第i号城市(i=0,⋯,N−2)与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci​公斤。

公司开张后很快接到了Q张订单,其中j张订单描述了某些指定的货物要从Sj​号城市运输到Tj​号城市。这里我们简单地假设所有货物都有无限货源,森森会不定时地挑选其中一部分货物进行运输。安全起见,这些货物不会在中途卸货。

为了让公司整体效益更佳,森森想知道如何安排订单的运输,能使得运输的货物重量最大且符合道路的限制?要注意的是,发货时间有可能是任何时刻,所以我们安排订单的时候,必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输,则这两张订单的运输同时受2-3以及3-4两条道路的限制,因为两张订单的货物可能会同时在这些道路上运输。

输入格式:

输入在第一行给出两个正整数NQ(2≤N≤105, 1≤Q≤105),表示总共的城市数以及订单数量。

第二行给出(N−1)个数,顺次表示相邻两城市间的道路允许的最大运货重量Ci​(i=0,⋯,N−2)。题目保证每个Ci​是不超过231的非负整数。

接下来Q行,每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法,并且不存在起点和终点重合的情况。

输出格式:

在一行中输出可运输货物的最大重量。

输入样例:

10 6
0 7 8 5 2 3 1 9 10
0 9
1 8
2 7
6 3
4 5
4 2

输出样例:

7

样例提示:我们选择执行最后两张订单,即把5公斤货从城市4运到城市2,并且把2公斤货从城市4运到城市5,就可以得到最大运输量7公斤。

分析:每个路程受到其中最小承重量限制,不同的运输路线[a, b],[c,d]之间有3种关系 1.[a, b]与[c,d]无交集,则可以同时进行两个运输订单 2.如果一个路线包含于另一个路线中,那么选择少的那一段显然更优 3.[a, b]与[c,d]存在交集,交集为[c,b],则能最大运输货物重量为min([c,b],[a,c] + [b,d]。 综上,我们可以将点坐标,按照右端点从小到大的顺序排列,相等的情况下,按照左端点从小到大的顺序排列。只需要建立一棵具有区间加以及区间最小值的线段树即可,符合结分配合律,故不需要lazy数组。遍历排序后的接线信息,每个路线取到最大运输货物后,减少本线路的通货承重量,即可得到最终答案~

注意:输入的路线起始与结束不一定小的在前面,大的在后面~

 

L3-016 二叉搜索树的结构 (30 分)-PAT 团体程序设计天梯赛 GPLT

二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。(摘自百度百科)

给定一系列互不相等的整数,将它们顺次插入一棵初始为空的二叉搜索树,然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后,得到一棵二叉搜索树,则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”(指自顶向下的深度相同)、“2是4的双亲结点”、“3是4的左孩子”都是正确的;而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。

输入格式:

输入在第一行给出一个正整数N(≤100),随后一行给出N个互不相同的整数,数字间以空格分隔,要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M(≤100),随后M行,每行给出一句待判断的陈述句。陈述句有以下6种:

  • A is the root,即”A是树的根”;
  • A and B are siblings,即”AB是兄弟结点”;
  • A is the parent of B,即”AB的双亲结点”;
  • A is the left child of B,即”AB的左孩子”;
  • A is the right child of B,即”AB的右孩子”;
  • A and B are on the same level,即”AB在同一层上”。

题目保证所有给定的整数都在整型范围内。

输出格式:

对每句陈述,如果正确则输出Yes,否则输出No,每句占一行。

输入样例:

5
2 4 1 3 0
8
2 is the root
1 and 4 are siblings
3 and 0 are on the same level
2 is the parent of 4
3 is the left child of 4
1 is the right child of 2
4 and 0 are on the same level
100 is the right child of 3

输出样例:

Yes
Yes
Yes
Yes
Yes
No
No
No

分析:简单的二叉搜索树内结点关系问题~Tree中存储每个节点的信息,cnt保存每个节点的序列号,root为树的根,f的值表示问讯关系是否成立,Find查询节点数值对应的序列号。insert为插入新节点进入二叉搜索树的函数,按照规则判断左右孩子是否为空(用-1表示),是的话就当成新节点的位置插入~

 

L3-012 水果忍者 (30 分)-PAT 团体程序设计天梯赛 GPLT

2010年风靡全球的“水果忍者”游戏,想必大家肯定都玩过吧?(没玩过也没关系啦~)在游戏当中,画面里会随机地弹射出一系列的水果与炸弹,玩家尽可能砍掉所有的水果而避免砍中炸弹,就可以完成游戏规定的任务。如果玩家可以一刀砍下画面当中一连串的水果,则会有额外的奖励,如图1所示。

现在假如你是“水果忍者”游戏的玩家,你要做的一件事情就是,将画面当中的水果一刀砍下。这个问题看上去有些复杂,让我们把问题简化一些。我们将游戏世界想象成一个二维的平面。游戏当中的每个水果被简化成一条一条的垂直于水平线的竖直线段。而一刀砍下我们也仅考虑成能否找到一条直线,使之可以穿过所有代表水果的线段。

如图2所示,其中绿色的垂直线段表示的就是一个一个的水果;灰色的虚线即表示穿过所有线段的某一条直线。可以从上图当中看出,对于这样一组线段的排列,我们是可以找到一刀切开所有水果的方案的。

另外,我们约定,如果某条直线恰好穿过了线段的端点也表示它砍中了这个线段所表示的水果。假如你是这样一个功能的开发者,你要如何来找到一条穿过它们的直线呢?

输入格式:

输入在第一行给出一个正整数N(≤104),表示水果的个数。随后N行,每行给出三个整数xy1​、y2​,其间以空格分隔,表示一条端点为(x,y1​)和(x,y2​)的水果,其中y1​>y2​。注意:给出的水果输入集合一定存在一条可以将其全部穿过的直线,不需考虑不存在的情况。坐标为区间 [−106,106) 内的整数。

输出格式:

在一行中输出穿过所有线段的直线上具有整数坐标的任意两点p1​(x1​,y1​)和p2​(x2​,y2​),格式为 x1​y1​x2​y2​。注意:本题答案不唯一,由特殊裁判程序判定,但一定存在四个坐标全是整数的解。

输入样例:

5
-30 -52 -84
38 22 -49
-99 -22 -99
48 59 -18
-36 -50 -72

输出样例:

-99 -99 -30 -52

分析:将所有水果信息按照x轴顺序排列好,枚举每一条水果线段,以最它的最低点作为参照点,然后取和其他所有线段点所成直线的交集。如果与所有的水果都有公共的斜率交集,说明存在以枚举线段最低点为刀砍线上的一个点。方便起见,选取其余线段最大斜率的最小值作为目标直线上的另外一个点,即为答案~Fruit中存储每个水果的坐标信息,kmax表示从枚举点出发能经过所有线段的直线的最大斜率,kmin表示从枚举点出发能经过所有线段的直线的最小斜率,tkmax、tkmin为两个水果之间的最大、最小斜率~

 

L3-011 直捣黄龙 (30 分)-PAT 团体程序设计天梯赛 GPLT

本题是一部战争大片 —— 你需要从己方大本营出发,一路攻城略地杀到敌方大本营。首先时间就是生命,所以你必须选择合适的路径,以最快的速度占领敌方大本营。当这样的路径不唯一时,要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一,则选择可以有效杀伤最多敌军的路径。

输入格式:

输入第一行给出 2 个正整数 N(2 ≤ N ≤ 200,城镇总数)和 K(城镇间道路条数),以及己方大本营和敌方大本营的代号。随后 N-1 行,每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量,其间以空格分隔。再后面有 K 行,每行按格式城镇1 城镇2 距离给出两个城镇之间道路的长度。这里设每个城镇(包括双方大本营)的代号是由 3 个大写英文字母组成的字符串。

输出格式:

按照题目要求找到最合适的进攻路径(题目保证速度最快、解放最多、杀伤最强的路径是唯一的),并在第一行按照格式己方大本营->城镇1->...->敌方大本营输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数,其间以 1 个空格分隔,行首尾不得有多余空格。

输入样例:

10 12 PAT DBY
DBY 100
PTA 20
PDS 90
PMS 40
TAP 50
ATP 200
LNN 80
LAO 30
LON 70
PAT PTA 10
PAT PMS 10
PAT ATP 20
PAT LNN 10
LNN LAO 10
LAO LON 10
LON DBY 10
PMS TAP 10
TAP DBY 10
DBY PDS 10
PDS PTA 10
DBY ATP 10

输出样例:

PAT->PTA->PDS->DBY
3 30 210

分析:本题相对比较简单,只需要根据题目要求调整最短路径的判定条件就好,为了方便操作,这里大本营代号(字符串)与数值之间要做一个映射~ntoi保存名字到编号的转换,iton保存编号到名字的转换,num中储存各个大本营敌军数量,Num中存储歼敌总数,path中存储每个大本营由哪个地方过来的,Dis存储出发点到各点的最短距离,sum中存储路径数,liberation存储了解放的大本营个数~