2013年8月30日PAT(A)解题报告

0

A. Dating (20)

对应PAT练习编号1061

解题要点:

  1. 取日期时要限定范围’A’-‘G’,并不是说第一个相同的大写字母都是有用的,如果不在A~G的范围内就忽略它
  2. 取小时的时候要限定范围’0′-‘9’或’A’-‘N’,注意0~9和A~N的计算方法是不一样的,并且与第一条类似,如果相同的大写字母在N之后也直接忽略;
  3. 取分钟的时候注意题目写明的是相同的”letter”,其他的数字、符号什么的都不可以,因此这里只要是”letter”并且大小写相同都可以,也就是’A’-‘Z’或’a’-‘z’。

B. Talent and Virtue (25)

对应PAT练习编号1062

解题要点:

  1. 输入时即进行分类,根据题目的描述,将输入的数据分类或者标记(也就是这里有两种思路,第一种是给四种人每种人开一个vector或者数组来存放,第二种是所有人都在一个数组里面存放但是外加一个key来表示每个人的种类);
  2. 输出排序,根据题目描述,依次输出圣人、君子、愚人以及剩下符合最低排序条件的,并且每一类人都要按照给出的排序方法进行排序;
  3. 注意不要超时(这里有个坑),因为输入和输出的量都会很大(105),因此用cin、cout必然会超时,在输入输出的时候要用scanf和printf。

C. Set Similarity (25)

对应PAT练习编号1063

解题要点:

  1. 去重,魅族输入的M个数字里面可能有重复的,需要把它们先去掉才行,剩下的数的个数才是该组数字的实际数量;
  2. 找出指定的两组中相同数字的个数,这里如果用M1*M2的方法进行遍历的话一定会超时的,可以进行排序之后依次进行对比;
  3. 相似率=(相同数字的个数)/(A组中数字个数+B组中数字个数-相同数字的个数)*100%,注意最后输出的时候保留1位小数和输出”%”。

D. Complete Binary Search Tree (30)

对应PAT练习编号1064

解题要点:

  1. 对输入的数据进行排序,CBST中各节点的排布和节点上实际数字没有任何关系,只和各节点数的相对大小有关系;
  2. 用递归的方法找到每一棵子树的根结点,然后分别处理它的左子树和右子树;
  3. 树构建完毕之后进行层序遍历,输出各节点。

Comments

您的电子邮箱地址不会被公开。 必填项已用*标注