1 malloc_88

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 14w+

1131 Subway Map (30分)

1131 Subway Map (30分)找最少的站点和最少的转乘点路线,这个其实是可以直接用DFS的。但是怎样找最少的转乘路线?假设从a到b到c,只要确定a到b的路线与b到以c的路线不同就可以将转乘路线加1.#include<cstdio>#include<vector>#include<unordered_map>using namespace std;const int maxn = 1e4+10;unordered_map<int,

2020-07-23 18:25:31

根据中序和层序建立二叉树

题目描述:给出一个N,表示结点数,然后第二行给出层序遍历,第三行给出中序遍历,求该树的前序遍历。样例:73 5 4 2 6 7 12 5 3 6 4 7 1首先我们可以根据层序的最前面的结点找到根结点,然后下一个结点所在的位置与中序中的位置有关。例如:由层序知根结点是3,然后5是3的子结点。因为在中序中5在3的左边,所以5是3的左结点。然后层序的下一个结点是4,在中序中4在3的右边下一个结点是2,中序中2在5的左边:层序下一个是6,中序中6在3的右边,在4的左边:接下来的两个也是

2020-07-23 15:51:03

1103 Integer Factorization (30分)

1103 Integer Factorization (30分)典型的背包问题,找出要放入背包的数据与个数以及规定的重量。而这里的数据是从1开始每个数的p次方,所以不如提前将所有数的p次方存在一个fac容器中,等到用的时候直接取就可以了。这里用DFS,而题中规定不能超过k个,总和要等于n,而且要子序列总和最大。若总和相等,要求找出最大子序列。所以DFS的时候从fac中最大的数开始。#include<cstdio>#include<vector>using namespac

2020-07-19 13:38:20

1025 PAT Ranking (25分)

1025 PAT Ranking (25分)这个题刚开始怕会有重复的id, 所以用了一个unordered_map来保存序号,可是写好后发现答案全错,仔细检查了一遍没发现错误。后来直接用一个int型变量cnt来保存序号,反而都对了。始终想不明白问题出现在哪里?刚开始的写法:#include<cstdio>#include<algorithm>#include<vector>#include<iostream>#include<unor

2020-07-16 21:10:21

1019 General Palindromic Number (20分)测试点2 4

刚开始用的string来判断是否是回文数,结果有两个测试点过不去,之后发现是有的数可能大于10,这时候无法表示,所以进行了修改。刚开始的写法:#include<cstdio>#include<string>#include<iostream>#include<algorithm>using namespace std;string getNum(int num, int radix){ int r = 0; string res; w..

2020-07-16 17:28:26

1153 Decode Registration Card of PAT (25分)

1153 Decode Registration Card of PAT (25分)刚开始写的时候,傻乎乎的写考虑了所有A B T的情况,在type=2的时候,type=3的时候又分别考虑,考虑了很多条件,后来越来越混乱。觉得太复杂,写不下去。然后看了一下柳神的代码,才发现原来可以写得这么简单。事实上只要关心考生考号的某个部分与所给的字符串相等时就可以把该考生放进一个容器中了。而type=1和type=3的情况是差不多的,都是要输出两个元素, 一个降序一个升序,而刚好降序的都是int型, 升序的

2020-07-14 20:09:36

1150 Travelling Salesman Problem (25分)

1150 Travelling Salesman Problem (25分)这题刚开始想用一个数组来记录访问的每个点的次数,然后再检查是否符合条件。后来看了柳神的代码,发现这种方式过于麻烦。要检验是否访问过所有点,只需要用一个set< int > s将访问过的点都插入,最后再检查s的size,如果size == n(即所有点个数)则说明访问过所有点,其次还要用一个vector< int > v来存储所有访问点,这样如果第一个点等于最后一个点说明是一个环。再检查v的size是

2020-07-14 15:13:16

1145 Hashing - Average Search Time (25分)

用平方探测法计算平均查找时间;位置用(x+j*j)%Msize来查找,其中j是步长,小于等于Msize, x是要插入的位置。用一个数组保存各个位置上的数,如果某个位置数字为0代表没有数字在这个位置上,则查找结束,或者j超过Msize,查找也结束。之前错以为位置用x%Msize+j*j来查找,导致无法通过样例。#include<cstdio>const int maxn = 10010;int num[maxn];bool isPrime(int x){ if(x <= ..

2020-07-14 10:27:56

1133 Splitting A Linked List (25分)

1133 Splitting A Linked List (25分)#include<cstdio>#include<algorithm>using namespace std;struct node{ int data, next, pos, rank, address; bool inlist;}m[100010];bool cmp(node a, node b){ if(a.inlist != b.inlist) return a.inlist >

2020-07-11 08:50:48

1130 Infix Expression (25分)

#include<cstdio>#include<vector>#include<string>using namespace std;int n;struct node{ char data[12]; int left, right;}m[30];bool have[30];vector<string> res;void DFS(int index){ if(index == -1) return; if(m[index].le

2020-07-10 10:23:42

1096 Consecutive Factors (20分)

1096 Consecutive Factors (20分)注意:这里寻找连续的乘积上限为2, 下限为根号n,否则测试点4过不了。当找不到一个因子的时候,如n=3的时候就可以直接输出n。#include<cstdio>#include<cmath>#include<algorithm>using namespace std;typedef long long LL;int main(){ int n, num, maxN = 0; scanf("%d"

2020-07-01 09:49:02

1088 Rational Arithmetic (20分)

1088 Rational Arithmetic (20分)#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;ll gcd(ll a, ll b){ if(b == 0) return a; else return gcd(b, a%b); } struct Fraction{ ll up, down; }a, b, c; Fraction red(F

2020-06-30 09:10:30

1086 Tree Traversals Again (25分)

方法一:#include<cstdio>#include<stack>#include<vector>#include<cstring>using namespace std;vector<int> In, post, pre;stack<int> origin;void getPost(int preL, int preR, int inL, int inR){ if(preL > preR) ret...

2020-06-27 09:41:25

1078 Hashing (25分)

注意用平方探测法的时候步长j要小于表长。#include<cstdio>#include<algorithm>using namespace std;bool isprime(int x){ if(x <= 1) return false; for(int i = 2; i*i <= x; i++) if(x % i == 0) return false; return true;}int a[10010];bool vis[10010];..

2020-06-22 10:11:06

1077 Kuchiguse (20分)

分析:注意这里是一行一行的输入,所以要用getline。注意第一个数字与第一行字符之间要用getchar()接收空格。刚开始的想法是先将前两个反转,然后找出公共前缀,然后接下来每接收一行就一行行的比较是否有公共前缀,结果有一个测试点过不去。#include<iostream>#include<string>#include<algorithm>using namespace std;int main(){ string s,t; int n, fla..

2020-06-22 09:24:02

1076 Forwards on Weibo (30分)

刚开始用DFS结果有两个测试点过不了:#include<cstdio>#include<vector>#include<queue>#include<algorithm>using namespace std;vector<int> v[1010];bool vis[1010];int n, level;void DFS(int s, int &num, int depth){ if(depth > leve..

2020-06-21 22:16:00

1069 The Black Hole of Numbers (20分)

1069 The Black Hole of Numbers (20分)#include<cstdio>#include<algorithm>using namespace std;int to_int(int num[]){ int sum = 0; for(int i = 0; i < 4; i++) sum = sum*10+num[i]; return sum;}void to_array(int n, int num[]){ for(int

2020-06-19 11:45:16

1067 Sort with Swap(0, i) (25分)

1067 Sort with Swap(0, i) (25分)分析:由于每次只能用0来交换,使最后的序列变为递增,所以最好的办法是每次看0处在什么位置,如果是5号位,就将5与0交换,这样每个数字都只要一次就能回到原来的位置。但是如果0刚好在0号位,那么需要在找到一个没换好的位置,将这个位置与0交换,再重新进行之前的步骤。#include<cstdio>#include<algorithm>using namespace std;const int maxn = 1e5+10

2020-06-19 09:53:52

1061 Dating (20分)

1061 Dating (20分)注意:week是从星期一到星期日,所以相应的字母只能是A~G。时间只能是0 ~ 24小时,则10 ~ 24只能是A ~ N。#include<cstdio>#include<iostream>#include<string>using namespace std;string s[8] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};bool vis[256];int

2020-06-18 09:51:27

1060 Are They Equal (25分) 与 1073 Scientific Notation (20分) 科学计数问题

1060 Are They Equal (25分)分析:题目中所给的数据可以分为两种情况:0.abcdef…abcd.efgh…而最终要显示的数据是‘0.’+数字的主体部分+’*^’+小数点的位置。所以首先要找出小数点的位置和主体部分的数字。在1的情况下,数字可能是000.000133;这样我们首先要处理前导0,以及小数点部分之后的0,因为最终形式是0.133,所以我们还需要计算小数点的位置,小数点后面有几个0,e就自减几次,这样就可以得到最终的指数部分。在2的情况下,数字可能是00123.

2020-06-18 08:47:34

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。