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$是最后一个元素的父节点

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