PAT解题报告

浙江大学PAT(Programming Ability Test) A-level、top-level以及CCCC练习题的部分解题报告。
源码在 https://github.com/CalvinNeo/PAT

[YN\d]\t(\d\+\-)+\t([\w ]+)\(\d+\).*

1001 A+B Format

注意判断-999,999的情况

1002 A+B for Polynomials

1003 Emergency

1004 Counting Leaves

1005 Spell It Right

比较简单,注意POSIX没有itoa,得用sprintf。特别地,对于二进制数字,可以借助于bitset来输出
accumulate第三个size_t参数最好直接设为0,在函数外加上初值。

1006 Sign In and Sign Out

1007 Maximum Subsequence Sum

思路:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(maxsumto[i-1]+n[i] < n[i])
{
// re-count maxsumto here
maxsumto[i] = n[i];
start[i] = i;
if (maxv < maxsumto[i]) {
maxv = maxsumto[i];
maxid = start[i];
}
}else{
maxsumto[i] += n[i];
start[i] = start[i - 1];
if (maxv < maxsumto[i]) {
maxv = maxsumto[i];
maxid = start[i];
}
}

有一个bug,为了方便计算,输入数据从n[1..k],定义n[0] = start[0] = 0; 考虑1 -1 1 -1 1 -1 1 -1 1 -1这样的序列,得到结果为1 0 1,但是实际的结果应当是1 1 1。因此start[0] = 1。

HHU1 1003

注意LL应当用printf("%lld")或者printf("%I64d")输出,但是double应当用printf("%f")输出。此外,要注意输入3 1 1 4的输出是4而不是1。

HHU2 1001

二叉查找树的中序遍历非递归实现使用一个栈,栈中的节点都已经遍历过左子树。比较容易的做法是再开一个vis数组用来记录这N个节点是否全部被遍历过。

HHU2 1002(POJ2823)

线段树的大小MAXN应当至少为4N

HHU4(HDU5524)

这一题问一个$N$节点的完全二叉树一共有多少个节点数不同的子树。这一题的关键在于完全二叉树的性质

  1. 二叉树始终有叶子,但是叶子节点只能出现在最下层或者次下层。最下层的叶子应当集中在左侧。
  2. 完全二叉树左右子树中至少有一个满二叉树,这个满二叉树的节点个数可以直接由其深度算得,另外一半的非满二叉树继续递归,最终一定能得到一个满二叉树
  3. $N$节点的完全二叉树深度为$ \lfloor log(N) \rfloor +1 $,上$\lfloor log(N) \rfloor$层一定是满二叉树。对于满二叉树,第$i$层有$2_{i-1}$个节点,前$i$层有$2_{i} - 1$个节点。
  4. 完全二叉树的数组表示形式是连续的,当index从0开始时,$[0, len/2 - 1]$区间内的节点有孩子,其中$len/2 - 1$是最后一个元素的父节点

注意分清二叉查找树和二叉堆的区别。二叉查找树需要左孩子小于根小于右孩子。而二叉堆是一棵完全二叉树,要求满足递归的堆序性,即根小于等于或大于等于所有的孩子。