sheepyWYY-CSDN博客

原创 PAT 甲级汇总

终于把PAT甲级的题目都补齐啦~~~撒花~~~臭不要脸的给自己弄了个汇总 23333。1001. A+B Format解析http://blog.csdn.net/sheepywyy/article/details/539950441002. A+B for Polynomials 解析http://blog.csdn.net/sheepywyy/a

2017-08-12 22:59:06 4851 1

原创 1147 Heaps 解析

感觉最近两次30分的题，不像以前那么麻烦了...检查最大最小堆.然后做一个后续遍历...序号从1开始就好了..多注意下端点的值，别搞错就好了。#include <iostream>#include <string>#include <string.h>#include <queue>#include <map>#inc...

2019-02-19 23:34:04 304

原创 1146 Topological Order 解析

初看题目.妈耶...拓扑排序.只知道手工算。没敲过代码啊啊啊....绝望.jpg..再仔细看题...发现...emmmm 貌似标记有没有前驱指向当前的点就好了..前驱为0，就OK。否则就不是拓扑序列。这个貌似叫入度？？？这中间闹了一个小插曲，不知道你们会不会遇到。我处理的时候是同步处理的，就是读一个数判定一次，失败就跳出。这一跳出就出问题了。怎么都查不出来怎么回事。算法怎么想都没有问题...

2019-02-19 23:32:07 225

原创 1145 Hashing - Average Search Time 解析

这个很少有的直接考hash的实现..依然素数直接存着保存时间。Hash的停止判定我有些忘了...看别人的解法是循环表长次没有插入就失败..记得不是太清楚了...这个题有点水的成分，要再看看hash了。#include <iostream>#include <string>#include <string.h>#include <queu...

2019-02-19 23:27:13 401

原创 1144 The Missing Number 解析

这个题没什么好说的。常规的hash就好了，然后遍历。注意数值的范围就好了。#include <iostream>#include <string>#include <string.h>#include <queue>#include <map>#include <set>#include <stack...

2019-02-19 23:23:37 194

原创 1143 Lowest Common Ancestor 解析

开始看到这个题觉得还挺简单的..写个带父节点的BST直接遍历就好了。结果还是太年轻....会超时...于是，我们就要在查找的过程中做手脚了..我们同时在树里面查找两个节点，每一轮找完之后，如果发现两个节点一样，我们就记录下来，就是他们的共有父节点。这样就能省下一次查找的时间。另外这个题的一个坑点：仔细审题：if the LCA is found and A is the key. ...

2019-02-16 15:05:28 337

原创 1142 Maximal Clique

许久没有练习PAT了，是时候刷一刷新的PAT了。感觉现在图的题换了风格。这个题目的Clique的主要解法还是：从一个点开始构建整个Clique，每次添加一个点，如果这个点和已经在Clique集合里面的点都临界我们就把他加入到Clique集合里面来。补充一下后面修改的时候遇到的问题。感觉这个题还是验证原序列之后再添加邻接点好一点。不然直接算可能性还是比较多可能性的。我现在写的程序有...

2019-02-12 21:22:55 161

原创 1139. First Contact 解析

这个题真的是恶意满满... 找同性的你们还找中间人 emmmmm 如果把4位id当作整数去处理就会遇到极大的坑:1.有小于4位的值,输出的时候需要补零2.最大的坑.case2中会有-0000 http://blog.csdn.net/gl486546/article/details/78816363 看这个大神的帖子才发现这个问题,之前想到了0点会有问题 ,但是真的没有想到会出-0这样

2018-01-04 21:39:59 661

原创 1138. Postorder Traversal 解析

刚开始看题，觉得怎么考这么简单的题。。然后一看N 50000 就知道是个大坑了. 建树是不行的.时间会超,递归到第一个值就可以了#include #include #include #include #include #include #include #include #include #include #define MAX 50010using namesp

2018-01-04 21:33:10 615

原创 1137. Final Grading 解析

要注意主要是取百分比的时候需要进位。按四舍五入的规则就好。#include #include #include #include #include #include #include #include #include #include #define MAX 10010using namespace std;int p,m,n;struct node{ s

2018-01-04 21:30:11 608

原创 1136. A Delayed Palindrome 解析

用string读入来回倒吧，写个简单的加法就好。#include #include #include #include #include #include #include #include #include #include using namespace std;string n;bool isPal(string s){ string ans;

2018-01-04 21:27:26 329

原创 1135. Is It A Red-Black Tree 解析

当时被红黑树吓傻了。。。然后走上了不归路。主要还是没有理解红黑树也是一个顺序树，中序就是从小到大的顺序。然后结合给的前序建树。后面判定的时候也是没有理解那个任意定点到树叶节点黑色节点数相同的意思。当作黑色节点高度这样去想会容易不少。还是知道的太少了。。#include #include #include #include #include #include #i

2018-01-03 23:05:05 682

原创 1134. Vertex Cover 解析

这个题还是挺有新意的，要想想才能做。当时不知道怎么回事绕进去了。估计一直做图的题做傻了。。。。这个题需要反过来想。把边编号，然后放到对应的定点vector里面去，然后对给的顶点集去访问边，看边有没有全部被访问。#include #include #include #include #include #include #include #include #include

2018-01-03 23:02:11 716

原创 1133. Splitting A Linked List 解析

就是把一个链表按负数，0-k ，大于k的顺序排序。emmm 直接老办法。遍历链表的时候放到不同的vector里面去，后面倒到一起输出就好了。#include #include #include #include #include #include #include #include #include #define MAX 100000using nam

2018-01-03 23:00:24 301

原创 1132. Cut Integer 解析

就是把两个数拆成两截，然后看能不能被两部分整除~int 就足够了没有溢出的情况#include #include #include #include #include #include #include #include #include using namespace std;int n ;string num;int a,b,z;bool s

2018-01-03 22:58:40 731

原创 1115. Counting Nodes in a BST 解析

按要求建立BST树然后层序遍历，统计每层的个数和最大层数，按要求输出最后两行个数就好。#include #include #include #include #include #include #include #include #include #define MAX 10010using namespace std;int n;struct node{

2017-09-01 00:33:05 523

原创 1072. Gas Station 解析

这个题的题目真的是好长好长，而且要理清的东西挺多的。不过后面的输出给了比较时候要用的数据的提示。首先，我们要保证加油站到居民楼越远越好，靠的是min{加油站到剧名楼的距离}的大小，取大的。然后min{}还相等，取avg{加油站到剧名楼的距离}的大小，取小的。然后avg{}还相等，取编号小的。这个题为了便于处理，我把编号连续化了，居民楼的编号排前面，加油站的接在后面。这样dijstr

2017-08-12 22:47:53 374

原创 1065. A+B and C (64bit)

主要考察数据相加会溢出的问题。溢出只有两种情况1、正+正溢出为负肯定比c大2、负+负溢出为正肯定比c小考虑好这两个就问题了。#include #include #include #include #include #include #include #include #include #include using namespace s

2017-08-11 23:19:31 299

原创 1064. Complete Binary Search Tree 解析

参考了 http://blog.csdn.net/iaccepted/article/details/20726067 的思想这个题很好的利用了树的的各种性质，很值得琢磨。首先：完全二叉树放在以1为开始编号的数组中满足左孩子的编号 = root编号*2；右孩子的编号 = root编号*2+1;而且按数组顺序输出直接就是层序遍历的顺序。其次：二叉搜索树的中序序列就是顺序排序

2017-07-27 00:24:10 284

原创 1063. Set Similarity 解析

参考了 http://blog.csdn.net/u014646950/article/details/47608823 的做法刚开始做的时候最后一个测试点总是超时。应该直接把重复的都去除掉，用set自带的查找去完成（效率高），没找到会返回结尾来判定是否找到。#include #include #include #include #include #include #inc

2017-07-27 00:19:58 690

原创 1062. Talent and Virtue 解析

分组排序：vg,tg >= L 的才进入排序vg.tg >= H的圣人tg=H的君子tg=vt的小人剩下的君子。然后再内部排序按总成绩，vg，id的顺序进行排序。#include #include #include #include #include #include #include #include #include using namespac

2017-07-27 00:17:14 483

原创 1061. Dating 解析

一开始把题目想复杂了。以为要匹配字符一样的比较。结果发现直接按顺序相同位置进行比较就好了。。。#include #include #include #include #include #include #include #include #include using namespace std;char day[7][4] ={"MON","TUE","WED","TH

2017-07-27 00:12:56 385

原创 1060. Are They Equal 解析

这个题目考虑到的情况挺多的感觉。首先科学记数法0.X 除了0以外X都不为零。然后输入的数据也是很怪。。需要考虑进去。。比如 0.001 这样的，小数但是小数点后面不是有效数而是0的。再比如 00100 这样的，整数但是前面有0的。（被坑死。。。当时怎么都查不出来）再再比如0 应该记为 0.00……0*10^0..还有精确位数为4 数字为120这样的还需要补0.都考虑到

2017-07-26 14:23:40 1054 1

原创 1059. Prime Factors 解析

分解质因数的问题。我为了减少时间把2-10000的所有素数都计算出来了，存成了一个数组。然后直接一个个的除。逃。。。#include #include #include #include #include #include #include #include #include #include #include using namespace std;int n

2017-07-26 14:18:04 609

原创 1058. A+B in Hogwarts 解析

这个题目是常见的不同进制的加法计算，处理好数据的截取和进位就好。#include #include #include #include #include #include #include #include #include #include #include using namespace std;string A,B;struct Node{ int g,s

2017-07-26 14:15:56 543

原创 1057. Stack 解析

这个题注意peek media的时候输出的中值，而且题目对时间的要求比较高，一直排序时间跟不上的。甚至我用了string都超时了..尴尬..（没有用树状数组）参考了：http://blog.csdn.net/gemire/article/details/21644347 里面提供的用两个set维护的方法，感觉理解起来简单些。树状数组的思维很厉害，但理解起来比较难。正好对set不熟悉，可

2017-07-23 12:06:06 325

原创 1056. Mice and Rice 解析

注意题目中的第三行的元素ci是第二行bi的位置信息。也就是说是吧第二行的第【ci】个元素放到第三行第【i】的位置。然后按NG的大小进行排序。我这里为了排名方便，用了两个数组维护进入下一轮和没有进入下一轮的位置。感觉反而变得比较繁琐了。#include #include #include #include #include #include #include #includ

2017-07-23 12:01:22 694

原创 1055. The World's Richest 解析

按题目给出的年龄范围输出排序的问题。直接排好序，按要求输出就好。#include #include #include #include #include #include #include #include #define MAX 100010using namespace std;int n,k;int m,mina,maxa;struct node{ cha

2017-07-23 11:56:58 369

原创 1054. The Dominant Color 解析

找出最多的颜色，并且输出。我直接用map标记颜色编号，然后统计出现的次数，记录最大值，当当前次数大于最大值则就是最对的那个颜色。#include #include #include #include #include #include #include #include #define MAX 480000using namespace std;int m,n;

2017-07-23 11:55:25 414

原创 1053. Path of Equal Weight 解析

直接DFS回溯就好，到叶子节点判定是否满足条件，满足加入结果。最后排序就好。#include #include #include #include #include #include #include #include #include #define MAX 105using namespace std;struct Node{ int weight; v

2017-07-13 20:53:48 723 3

原创 1052. Linked List Sorting 解析

给一个链表，然后按链表里面的数据排序，重新排成一个链表。给的数据里面有掺杂的无用节点，不能直接排序。所以要遍历一遍链表之后再排序。#include #include #include #include #include #include #include #include #include #define MAX 100010using namespace std;

2017-07-13 20:51:26 1092

原创 1051. Pop Sequence 解析

模拟整个栈的出入栈情况就好了。#include #include #include #include #include #include #include #include #include #define MAX 1010using namespace std;//m最大容量 n序列长度 k出栈序列个数int m,n,k;int PopSeq[MAX];

2017-07-13 20:48:57 493

原创 1050. String Subtraction 解析

在句子中删去指定字符。直接标记就好了，然后输出的时候标记的不输出。#include #include #include #include #include #include #include #include #include using namespace std;string s,d;bool isDel[256];int main(){ memset

2017-07-13 20:46:38 273

原创 1049. Counting Ones 解析

题目是要求数1-N的数字里面一共有多少个数字1，别理解成含有1的数字的个数了。如果有《编程之美》这本书可以看看里面的介绍。讲的不错的。我这里就贴两个图大概说下规律。佩服总结出这个规律的人。。。#include #include #include #include #include #include #include #include using

2017-07-12 23:36:03 459 1

原创 1048. Find Coins 解析

找两个硬币看能不能付钱，两个硬币必须正好等于要付的价格。那就直接从小到大排序，然后从第一个元素开始，找价格减去当前硬币的价值，看能不能找到。注意二分查找的最后位置。这个后面再找个时间研究下。里面其实有很多细节需要注意的。#include #include #include #include #include #include #include #include #de

2017-07-11 23:02:07 1812

原创 1047. Student List for Course 解析

按照学生的选课情况，输出这门课有哪些学生上，并按字幕顺序输出。注意，无论这个课有没有人上都要打印课程号和人数。这个题通过对学生姓名的处理有两种方法。一种是用字符数组来存名字，来避免string的超时问题。将字符数组放在结构体里面然后用vector类来排序处理。#include #include #include #include #include #include #i

2017-07-11 22:58:32 337

原创 1046. Shortest Distance 解析

问题是一个环中的亮点，怎么走最近的问题。一个环中的亮点肯定是有两条路径的，一个顺时针，一个逆时针，两者的和等于环的长度。有了这一点，我们就好做了。在读入数据的时候我们就累加posd【i】表示从【1】到【i】的顺时针的距离。那么从【a】到【b】的距离就等于posd【b】-posd【a】，另一段就不用说了。两个求最小。#include #include #include

2017-07-11 22:49:22 398

原创 1045. Favorite Color Stripe 解析

直接把问题转化成最长不下降子序的问题。这个题目时间的要求比较高。所以注意数据的处理。一是爱娃不喜欢的颜色不放进比较序列里面直接丢掉能加快处理。二是在转序列的时候注意直接把转好的序列丢进去不然会超时三是在转序号的时候注意没有匹配的情况。虽然进行第一步后不用考虑这一步。这涉及到样例3的通过还是说下。map的特殊性没有赋值的会匹配到0上2 3 1 5 64 2 2 2 2

2017-07-08 21:56:35 523

原创 1082. Read Number in Chinese 解析

给一个数字要用中文读出。主要还是单位的判定和零的读法。例如：10000000 这样的读 yi Yi 不用读万10080 这样的度yi Wan ling ba Shi 只读一个零而且后面的0不读。8001000 这样的度ba Bai Wan yi Qian后面的零不读。所以我们主要是4位为一个处理但愿进行处理，和标记位的更新。用len确定现在的位数，来添加单位。#inc

2017-05-09 13:38:40 607 3

原创 1087. All Roads Lead to Rome 解析

条条大路通罗马。Dijstra+DFS通杀。。。#include #include #include #include #include #define MAX 200using namespace std;int n, k;string st;map city2int;map int2city;struct Link { int len; int C

2017-05-09 09:17:53 1921

c#实用画板小程序实例

空空如也