第一种方法对于该题目其实有点取巧的感觉；首先，注意一点，对于最长不下降子序列来说，其序列的元素一定是非递减的，所以我们的当务之急是如何将值转换为递增序列，从而使得算法能够继续进行；对于这个问题，我们可以使用hashtable进行处理，也就是利用hashtable重新使得值递增；

这道题也是动态规划的几大问题之一，也就是最大连续序列和问题； 对于这个问题，我们需要考虑的首先还是转换方程的问题：我们设置一个dp数组，dp[i]代表的是到当前的最大序列和。 所以有转换方程：dp[i]=max(a[i],dp[i-1]+a[i])所以边界就是dp[0]=a[0]，然后从1开始计算； 代码如下： {代码...}

对于这道题，我们着手于i~j个字符，所以关注点在于i和j，所以我们建立一个二维矩阵来保存动态规划途中的计算值。对于dpi，其值为1时，意为i-j的字串是回文子串，为其他值则不是；

还是贪心算法应用；建立string的数组，输入之后，两两进行比较，a+b>b+a，则两两交换位置，将每个string放到合适的位置，从而使得局部最优，变为整体最优；

这道题的题目和之前的PAT题目相同，也是采用打表的方法；先预先算好所有的元素；建立两个数组，left，right；left从左到右遍历，索引index装从左到index中最大的元素；right从右到左遍历，索引index装从右到index中最小元素；之后从0~n比较left，right相应的成员，也就是看左边最大和右边最小是否符合题目规范

具体的思路就是，输入第一个序列；在输入第二个序列的时候进行判断，主要的判断逻辑为：如果输入的值小于第一个序列的相应值，cout++，跳过该值；如果大于相应值，进行向后判断，cout计算增加的值；如果发现途中cout的值等于中点值，直接进行输出，程序停止；

这道题的贪心思路就是分两个情况，一个大于零，一个小于零，分别进行排序，大的乘大的；对于代码里，我们直接对其进行sort排序，然后分两种情况，一个负数，一个正数；对于负数，采用的是同时两个序列从最小的开始选取，直到有一个队列穷举完毕；正数情况类似；但是需要注意的是一定要从头遍历，从而以防出现元素漏掉的...

1.如果在可到达范围内第一次出现了低于当前油价的站点，则到达该站点；这个选择的依据是，如果我们在a,有a->b->c，b站点油价便宜，所以我们应该去b加油再跑到c，而不是加a站的油跑到c。

简单的贪心问题，和背包问题类似，这里不再赘述 {代码...}

平衡二叉树AVL，写过总结，这里不再赘述； {代码...}

和完全二叉排序树那道题类似，采用的方法还是中序遍历空树填节点的方法；代码如下： {代码...}

这道题自己起先想到的思路是根据完全二叉树性质，找出左右子树，递归进行；但是示例给出的思想很值得学习；对于一个二叉搜索树，其中序序列必递增的，所以可以利用这一点；我们先对输入的节点序列进行递增排序，之后我们对一个空的数组进行中序遍历，每遇到一个节点，就把相应的递增序列的值保存进去；这是一种对空序列...

简单的不用考虑平衡的二叉查询树；我发现我有读题障碍症。。。 {代码...}

并查集的应用，但是一上来有点蒙蔽，因为这次多了一个媒介，通过活动来判断人员是否在一个集合；有一个示例思路：构建活动的集合，首次发现在该活动的人员，将对应活动索引的内容设置为该人员编号；如果后面输入还有该活动，就将具有该活动的人员和数组内的人员进行并查集合并；大致代码如下所示：

也不难，使用DFS就能很好的解决问题；对于DFS的途中节点记录有两种方法，这个需要注意一下:1.使用vector模拟栈，每次递归的时候压栈或者弹栈，遇到符合要求的时候直接复制该栈保存；2.使用path数组，并且利用numnode来追踪path数组的长度，其中path[i]代表路径上第i个节点的编号。由于numnode限制了path的长度，所以无需...

还是数层数和数节点的问题，个人觉得用BFS比较好；当然用DFS也能做，具体的思路就是建立层数数组，深度遍历到x层的时候，如果是叶子节点就leaf[x]++，如果不是就不管，继续跳过；代码片段可以这样：

思路借鉴了之前的图的层数，发现这个贼好用；关键在于输出浮点数的格式，这个要注意一下 {代码...}

并查集用多了。。。第一时间想到的是并查集却没有想到静态数组，这是一个比较大的失误；这道题的关键在于如下几个点：1.如何保存输入的树；2.如何寻找根节点；3.如何完成树的反转；1，2两点都很容易解决，可能比较难一点的是第三点；其实第三点也不难，我们观察一下就可以知道，树的反转本身就是在后序遍历的过程中对左...

和刚刚之前的那道题类似，只不过多考察了一个四大遍历输出中的一个；自己跟个智障一样检查了一个小时，结果发现少了一个返回指针，真是干他娘的； {代码...}

本题主要考虑两个点：四种遍历和遍历序列生成树；后序序列+中序序列可以确定出唯一一颗子树，并且通过观察我们也可以发现两序列的判别点：1.后续序列的其中一颗子树序列的最后一个节点必定是该子树的根节点；2.通过该根节点可以将中序序列分为左右两个子树，通过子树序列再去第一步进行子树序列的判断；

熟练运用set和map有奇效；最主要的目光应该聚焦在输入上；当出现多个同一行输入的字符串是，如果要使用string录入，可以采取如下方式，其中使用getchar来得到换行符，从而标志输入是否结束：

唯一要注意的是当读入字符串进行有效字符截取的时候，队尾可能还会有有效字符，记得在循环结束的时候进行word的判别； {代码...}

个人觉得用hash也可以，但是map更加简便一点，重要的是map的遍历和操作方式需要注意以下;详细代码如下所示： {代码...}

但是这道题的示例代码给出了所谓打表的新思路，之前没参加过ACM或者OJ比赛，也就没听说过；简单的来说就是对可能的输出结果进行计算，在输入值的时候可以直接按表输出，减少了不必要的重复计算；

这是活用递推里面比较经典的一种题型；如果采用最简单的暴力枚举，则会出现time limited错误。这道题关键是能够找到递推的思路。对于序列中的每一个每一个A，如果能够有PAT出现，则必定A的左右都有P和T；如果A左边有a个P，右边有b个T，则可以推出含有该A的PAT有a*b个；所以解法就被分解成以下几个步骤：1.寻找左边P的个...

示例思想中提到了二分以及two point概念，这个需要后面进行总结；这个示例也给出了一个新的思路。对于两个数字和m，查找两个加数，可以进行i和m-i的枚举，通过遍历数组查看两个加数是否存在，来进行遍历；由于从头遍历，所以找到的第一个和就是最小的a，借此省去了不必要的麻烦；

水题这道题PAT环境下出现了gets函数无法使用的情况，但是在自己本机的编译器上是可以运行的； {代码...}

水题，还是没神马可说的 {代码...}

水题，没神马可说的 {代码...}

水题，有时候不要总是寻求最优解，直接比较也可以；关键点是利用hashtable来存储元素是否被输出过，要注意一下ASCII码的关系；这里注意一个取巧的方式，直接利用字符来当作下标索引，可以避免不必要的索引换算