Life of Asuwill

main=0

PAT 1001-1010 题解

前言

PAT 是浙江大学搞出来的一个编程（Programming）能力（Ability）测试（Test），在姥姥的大力推广下，目前也逐渐走上了正道，详细介绍可以直接到官网查看 http://pat.zju.edu.cn/

我断断续续也将上面的题目做得差不多了，想来也应该总结一下，算是给自己一个交代。题解大致的形式将会是每10个（或者少于10个）题目一篇博文，对每个题目而言，会简述题目大意，然后是思路整理，然后是代码链接。我已经完成的题目的代码都在github上，请戳我

1001. A+B Format (20)

题意

按照给定的格式输出两个整数的和：即每三位数一组用逗号分隔，例如 999991 就应该输出为 999,991

思路

简单题，可以将和每次三位取出（即按照1000进制），然后再从高位开始输出即可，注意处理负数，中间合适的位置加上, 主要代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void format(int  n)
{
  bool neg = false;
  if(n<0)
  {
    neg = true;
    n = -n;
  }
  stack<int> vi;
  do
  {
    vi.push(n%1000);
    n /= 1000;
  }while(n!=0);
  if(neg)
    cout << "-";
  cout << vi.top();
  vi.pop();
  while(!vi.empty())
  {
    int top = vi.top();
    vi.pop();
    printf(",%03d",top);
  }
  cout << endl;
}

完整代码请戳我

1002. A+B for Polynomials (25)

题意

求两个多项式的和，a 和 b 都以 K N1 aN1 N2 aN2 ... NK aNK的形式表示，其中 K 表示多项式中中非零项的个数，Ni 和 aNi 分别表示指数和系数

思路

类似于归并的思想，从高到低将指数相同的项的系数加起来，如果某指数项只在一个数中有，直接保留在结果里即可，需要注意的是如果系数加起来为0，这一项就不能放进结果。 核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

  // p1+p1
  vector<Poly> result;
  vector<Poly>::iterator vi1 = p1.begin();
  vector<Poly>::iterator vi2 = p2.begin();
  while((vi1 != p1.end()) && (vi2!= p2.end()))
  {
    if(vi1->exp == vi2->exp)
    {
      tmp.exp = vi1->exp;
      tmp.coe = vi1->coe + vi2->coe;
      if(tmp.coe !=0)
        result.push_back(tmp);
      ++vi1;
      ++vi2;
    }
    else if(vi1->exp > vi2->exp)
    {
      result.push_back(*vi1);
      ++vi1;
    }
    else
    {
      result.push_back(*vi2);
      ++vi2;
    }
  }
  while(vi1 != p1.end())
  {
    result.push_back(*vi1);
    ++vi1;
  }
  while(vi2 != p2.end())
  {
    result.push_back(*vi2);
    ++vi2;
  }

完整代码请戳我

1003. Emergency (25)

题意

给定城市之间的道路距离，以及每个城市的营救队的人数，求从城市 c1 到 c2的最短路径的条数，以及沿途能够召集的最大人数。

思路

典型的最短路径题，采用Dijkstra算法，但是这里不仅仅是找出一条最短路径，而是要计算最短路径的条数，并且需要统计沿途能够召集的最大人数。能够召集的人数没什么问题，只需要在最短路径的基础上加上一个人数的比较，callup[c]表示达到城市c的时候能够召集的最大人数。用count_path[c]表示到达城市c的最短路径的条数。

  1. 如果 dist[c] + edge[c,adj] < dist[adj] 则 dist[adj] = dist[c] + edge[c,adj]; count_path[adj] = count_path[c]； callup[adj] = callup[c] + people[adj]
  2. 如果 dist[c] + edge[c,adj] == dist[adj] 也就是有多条距离相同的路径到达城市adj，这个时候 count_path[adj] = count_path[adj] + count_path[c]; callup[adj] = max { callup[adj], callup[c] + people[adj] }

代码结构：

1
2
3
4
5
6
7
8
9
10
11
12

  // start from start city
  dist[start] = 0;
  count[start] = 1;// one shortest path from start to start
  callup[start] = people[start];
  while(true)
  {
    int city = nearest_city();
    visited[city] = true;
    if(city == end)
      break;
    update_neighbor(city);
  }

nearest_city，可以通过priority_queue最小堆实现，我当时用了线性遍历查找，因为测试数据小，也能过。

完整代码请戳我

1004. Counting Leaves (30)

题意

统计一个家谱树中没有孩子的成员，也就是叶子节点的个数，题目要求按层输出每一层没有孩子的成员 输入：

N M

ID k ID[1] ID[2] … ID[k]

…

其中 N是总结点树，M是非叶子节点数目，接下来 M 行每一行都是 节点号 孩子个数 孩子编号列表

思路

输入之后构成一个图（一棵树），使用矩阵或者邻接链表都行： 类似于

编号 孩子列表

01 02 03

02 04

03 05

从根开始采用广度优先遍历，统计每一层没有孩子的节点即可，具体操作核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

struct Node
{
  int id;
  int level;
};
int count[MAX_NODE];
queue<Node> q;
//...
Node root;
root.id = 1;
root.level = 1;
q.push(root);
while(!q.empty())
{
  Node node = q.front();
  q.pop();
  if(node has no child)
  {
      count[node.level]++;
  }
  else
  {
      for child of node
      {
          Node c;
          c.id = child
          c.level = node.level+1;
          q.push(c);
      }
  }
}

1005. Spell It Right (20)

题意

输出一个数N的各位数字的和，但是和的每一位都需要用对应的英语输出。例如，输入12345 算出和是15，则输出 one five。需要注意的是N的范围是[0,10^100]

思路

简单题，数字到英文的映射可以直接用数组char* i2eng[] = {"zero","one",..., "nine"}，使用字符串接收输入，然后求和就行了，然后再将每一位对应输出即可。

完整代码请戳我.cpp “1005”)

1006. Sign In and Sign Out (25)

题意

根据 签到以及离开的记录，找出第一个来以及最后一个走的人

思路

简单的题，遍历所有记录，分别记住签到最早的人以及离开最晚的人即可，连排序都用不上

完整代码请戳我

1007. Maximum Subsequence Sum (25)

题意

给定一个整数序列，求其中的一个连续子序列，该子序列中元素的和是所有连续子序列中最大的，输出和以及序列开始、结束的元素。题目规定，如果序列里的值都是负数，则最大和定义为0，输出整个序列开始、结束元素。

思路

非常经典的一个题目，记得当年算法基础教材里面就讲了这道题目，而且是讲了三个还是四个方法，复杂度从最高O(N3)到最低O(N)，当真把我给镇住了！这算法带来的效率提高真不是一般厉害。 O(N）复杂度的算法核心如下

1
2
3
4
5
6
7
8

max_sum = -1;
sum = 0;
for(int i = 0; i < n; ++i)
{
  sum += a[i];
  sum = max(sum,0);
  max_sum = max(max_sum, sum);
}

解释起来也比较好理解：

  1. 如果加上当前元素后，sum < 0，那么得到当前和的这一序列肯定不属于所求序列的一部分，因为加上一个负值，和肯定是变小的。因此将sum重置为0，接下去继续找；
  2. 每一步都需要将最新的sum与已知的max_sum比较，如果新的和已经更大了，则更新max_sum的值。

当然，要完成这道题，代码要稍微复杂点，比如要注意序列里是否有非负数出现，在更新sum 或者 max_sum的时候，同时需要记住对应的序列开始结束的位置。 完整代码请戳我

1008. Elevator (20)

题意

给定一串电梯的请求序列，计算电梯完成所有请求所需要的时间。已知电梯上移一层楼需要 6s，下移一层需要 4s，每次停下来需要花 5s。

思路

就是简单的模拟题，按照给定的顺序模拟电梯运行，计算相应的时间花费。

完整代码请戳我

1009. Product of Polynomials (25)

题意

计算多项式的乘积

思路

前面有一道题1002. A+B for Polynomials (25) 已经做了多项式的加法操作，再定义一个多项式与单项相乘的方法，然后将一个多项式的每一个项与另外一个多项式相乘，将结果再求和即可。 完整代码请戳我

1010. Radix (25)

题意

给定两个数以及其中一个数的进制，求是否存在一个进制使得另外一个数与该数的值相等。两个数的都是由{0-9} 以及 {a-z}组成

思路

要比较不同进制的数，最好是将其都变成十进制数来比较，因此需要一个将其他进制转换为十进制的函数。有了这个函数之后，将已知进制的数转为10进制数，然后看尝试给另外一个数设置进制，然后转为10进制，判断结果是否一致。设置进制的起始值具体看给定的数中出现的字母，比如出现的最大数是a，也就是至少是11进制，以此类推，没有上限。

  1. 如果算出的结果相等，则结束，给出答案
  2. 如果偏小，则测试下一个进制
  3. 如果偏大，则结束，输出 Impossible

这个做法有一个问题，就是可能会超时，想想，如果给定 A = zzzzzzz，是37进制,而B = 10，那么从二进制开始尝试，需要尝试的次数就非常多，很可能会超时。因此，我们不能按顺序递增进制来猜，必须跳跃性地猜。可以想到的办法就是二分法。需要尝试的基的上限是 A的值。稍微可以优化一下的是，如果B只有一位，那么值其实是确定的，这个时候可以快速判定是否存在解，而不用按照前面的方式傻乎乎的计算很多次。

完整代码请戳我

【PAT 1001-1010 完】

原文地址：http://jiangdapeng.github.io/blog/2013/10/20/pat-1001-1010-solutions/
Written by Asuwill posted at http://jiangdapeng.github.io
版权声明：自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0