总览
overview
考PAT主要还是为了当浙大的机试成绩。其实两年前我大二刚开学的时候也考过一次，那次被最后一题卡住了，只拿了70分。我非常清楚的记得那道题是给你一棵树的前序和后序，让你输出可能的树的中序。我苦于不会建树，一分未拿。
今天的题感觉和两年前还是难了些，不过算法少了很多，两年前我记得还求了个最小生成树貌似，今年真的时是没有模板题了，数据结构也仅限于最后一道的树，不过相对地思维维度稍微深了一些。
Anywey，反正最后还是侥幸拿到了满分(๑¯∀¯๑)
A
狼人问题
题目大意
有n个人，每个人说一个数字num[i]，正数代表该玩家指认num[i]号玩家是村民，负数代表该玩家指认-num[i]号玩家是狼。已知一共有两匹狼，一匹狼说真话，一匹狼说假话，村民中有一个人说真话，一个人说假话。请输出符合题目条件的狼的标号，且要求字母序最小。
思路
枚举狼，然后暴力判是否符合题目要求即可（必定只有一狼和一村民在说假话）。
坑点
没有什么坑点，就是刚开始考试看到这种题真的是有点慌的，因为以前做20分的题基本不用过脑子，而这道题看起来实在是有点吓人，我也是先去做的第二题回来才想到思路。
B
药品问题
题目大意
有n个药品关系，有关系的药品放在一起就会发生反应。对于每个关系，给出两个药品的名称。然后给你m次询问，每次询问给出k个药品，问你放在一起会不会有某一对药品发生反应。
思路
map记录药品名与编号的对应关系，set数组记录药品会与哪些其他药品发生反应，n^2暴力判即可。
坑点
没有什么坑点，我看了下数据范围觉得n^2枚举可能超时，稍微加了一丢丢辣鸡的剪枝（事实证明真的没什么用）。这应该是这次考试最简单的一道题了。
C
旅行商问题
题目大意
给你一张图，m次询问。每次询问给出一条路径，你要判断这个路径是否真实存在，存在输出路径长，否则输出NA。你还要判断该路径是否是一个普通环（除了起点会经过两次，每个点只经过一次，且起点和终点），或者是一个一般环（不是普通环的环），或者根本就不是环。如果该路径不存在，那么这个路径也不是环。最后你要输出是一般环或普通环的路径的最小值。
思路
也是一道完全暴力题，暴力判路径是否存在，暴力判数据类型。
坑点
这道题应该是我花的时间最长的一道题。我第一发交上去是22分，我就先去做了最后一题再回来改的bug。这个bug大概改了20分钟，我测了一些自造的样例都没有问题（其实是样例造的烂）。后来我发现是我判环的类型时把一些不是环的图判成了一般环，改了之后顺利ac。
D
最近公共祖先问题
题目大意
给你一棵树的前序和中序遍历，再有m次询问。对于每次询问有两个节点，求这两个节点的LCA（最近公共祖先）。如果一方是另一方的祖先，或者该节点不存在什么的都要输出一些奇奇怪怪的东西。
思路
先建树。set记录出现过的数据。对于每一次询问，先看看询问的点在不在set里面。然后求出两个节点各自到根的路径，这时可以判断一方是不是另一方的祖先。最后如果不是上述情况的话就从根开始暴力比较路径，若有数据不同，那么前一个就是询问节点的LCA。
坑点
很多年以后，奥雷连诺上校站在行刑队面前，准会想起父亲带他去参观冰块的那个遥远的下午。当时，马孔多是个20户人家的村庄，一座座土房都盖在河岸上，河水清澈，沿着遍布石头的河床流去，河里的石头光滑、洁白，活像史前的巨蛋。
我拿到这道题，仿佛回到了两年前的下午，我对着一道相似的题苦思冥想而不得结果。但是这次我已经知道了该怎么建树。我迅速完成了代码的构建，交了一发，是29分。于是我先去改了前面一题的bug，改完后重新回来看这道题。我又看了一边自己的代码，发现我有一个题目描述未提到的特判。我把两个相同节点的询问会定义为输出两者的LCA，而不是a是a的祖先这样。我把这个特判去掉之后交了一发，顺利AC。至此长舒一口气。
总结
summarize
这次的难度比两年前肯定是更高的，但是我凸了，也更强了。刚开始看到第一题真的很慌，因为毕竟事关考研，但是还好ACM比赛的经验还是让我冷静下来去敲了第二题，回来再看第一题就很清晰了。（事实证明我的选择真的很正确）
前面两题都是一发就过，让我的心态很快放平了。这时考试时间刚过一小时，给我后面的题留出了充足的时间。等我把最后两题打完交了之后（还没有debug）还剩40分钟，有足够的时间来给我找错误。这时出了一个小意外，在我刚交完第四题的代码时，电脑死机自动关机了。现在想想好后怕，真的只差了那么几秒，我的代码可是没有备份的。我换了一台机器后花了大概20分钟来找第三题的错误，a掉第三题后第四题是秒过，就这样拿到了满分。我a完全部的题时距考试结束还有20分钟，默默溜出了考场。
