PAT甲级题解（慢慢刷中）

博主欢迎转载，但请给出本文链接，我尊重你，你尊重我，谢谢~
http://www.cnblogs.com/chenxiwenruo/p/6102219.html
特别不喜欢那些随便转载别人的原创文章又不给出链接的
所以不准偷偷复制博主的博客噢~~

时隔两年，又开始刷题啦，这篇用于PAT甲级题解，会随着不断刷题持续更新中，至于更新速度呢，嘿嘿，无法估计，不知道什么时候刷完这100多道题。

带*的是我认为比较不错的题目，其它的难点也顶多是细节处理的问题~

做着做着，发现有些题目真的是太水了，都不想写题解了，就贴个代码吧，就是这样任性~~

寒假刷的不多，然而一个题解都没写，妈呀，要狂补一下了。。。

发现，做过的题目中，涉及字符串处理的有很多，即使不是关于字符串的题目，有时候也需要对输入啥的进行处理。

说简单也简单，说难也难，所以要刷PAT的童鞋，对于字符串处理还是需要多多考虑全面滴~

细心的童鞋中间可能会发现缺了几道题，是还存在样例没有全过的情况，一旦解决了会慢慢补上滴~

这一百多道题里面，算法题其实并不算很多，大多数主要是模拟、排序、字符串处理啥的。

算法和数据结构的话，主要有：

1.AVL平衡树 (PAT竟然会有两道考AVL树的，有点超出我的预期，当时学数据结构的时候没尝试写过AVL树额，看来多学点还是有必要的)

2.最短路，主要就是dijkstra算法，这个肯定要会写，有的还要让你输出路径。

3.并查集

用来求是否在同一个类别、求连通分支啥的，很简单学学就会了。

其实并查集最主要难的在于种类并查集，但是PAT没有出这类题，所以也就不说了。

4.dfs和bfs，这都不会的话，你好意思说学过计算机么~~

5.树状数组，两种用法，1.单点更新，区间求和2.区间更新，单点求和

6.链表

7.剩下的主要就是STL的运用，如map、vector、queue等，还有巧用struct来定义结构体，以及如何自定义排序