jdflyfly的小博客
249326109 · 共 66 篇文章
[置顶] pat 1004. Counting Leaves (30)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1004 题意:统计一颗给定树的每层的叶子节点数目。 分析:基于节点数据量比较小,可以简单地利用链接矩阵的方式存储树,然后利用dfs遍历,遍历的时候记录深度变量用于统计。 #include<stdio.h> int mat[105][105]; int num[105]; int n, m; int maxDep = -1; void dfs(int id, int dep) { int isLeaf = 1; int i; for (i = 1; i <= n; i++) { if (mat…
[置顶] pat 1003. Emergency (25)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1003 题意:计算两个点之间的加权最短路径,若有多条最短路径,选取沿途节点权重和最大的。 分析:利用Dijkstra算法求出最短路径,然后利用dfs遍历选取路径最短并且节点权重最大。 #include<stdio.h> #include<stdlib.h> #include<string.h> #define Inf 100000000 int road[505][505]; int people[505]; int n, m, from, to; int known[505]; int d…
工厂模式总结
简单工厂模式 , 工厂方法模式 和 抽象工厂模式 都是属于创建型设计模式,这三种创建型模式都不需要知道具体类。我们掌握一种思想,就是在创建一个对象时,需要把容易发生变化的地方给封装起来,来控制变化(哪里变化,封装哪里),以适应客户的变动,项目的扩展。 简单工厂模式 :简单工厂没有抽象类,只有一个具体工厂类如MyFactory,然后MyFactory里面有个工厂方法CreateProduct返回一个基类产品,具体返回什么具体实例通过传入参数然后用case判断。 比如下面的例子:产品是手机,分别有子类 诺基亚手机和苹果手机,两种手机都通过CellphoneProducer类来控制产生。 pack…
pat 1018. Public Bike Management (30)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1018 题意(转biaobiaoqi):以杭州的公用自行车站点管理为背景。每个站点是一个节点,每个节点上最多停放 Cmax 辆自行车,Cmax/2 为节点的最佳状态。不同节点间距离不同,整个构成了一张带权无向图。要求从起始点(公用自行车管理中心)出发,去目的地维护目的地节点的车辆状态,如果车辆低于 Cmax/2,则给它添加车辆到 Cmax/2 辆,如果多于 Cmax/2,则去除掉几辆车。同时,在去往目的地的过程中,也需要调整所有沿途站点的车辆(这里题目没有交代清楚,实际测试是只能在去往目的地…
pat 1019. General Palindromic Number (20)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1019 题意:给定一个十进制数和一个进制,判断该数字在该进制下是否为回文。 分析:简单的数字进制处理。 #include<stdio.h> int numStr[100]; int idx; int palindrome(int num,int radix){ if(num==0) return 1; int rem; while(num){ rem=num%radix; num/=radix; numStr[idx++]=rem; } int i; for(i=0;i<=idx/2;i++…
pat 1020. Tree Traversals (25)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1020 题意:给定二叉树的后序遍历和中序遍历,求层序遍历。 分析:根据后续遍历和中序遍历,可以递归的构建树,建好树之后利用queue层序遍历。 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct Node{ int val; struct Node* left; struct Node* right; }Node; int post[35]; int in[35]; int n; Node* root;…
1022. Digital Library (30)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1022 题意:给定 N (<=10000) 本书的信息,包括 7 位 ID,最多 80 字符的书名,最多 80 字符的作者名, 多个最多 10 字符的关键词,最多 80 字符的出版商和属于 [1000, 3000]的出版时间。 另给出 M (<=1000) 的查询请求,按照查询格式分为: 1: 书名 2: 作者 3: 关键词 4: 出版商 5: 年份 分析:其他属性排序后遍历查询即可,关键词合理的方法应该建立倒排索引,这里用vector水过了。。 #include<stdio.h> #inc…
pat 1011. World Cup Betting (20)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1011 题意:给定数据,找到每行的最大值根据公式计算结果。 分析:简单模拟题目。 #include<stdio.h> double bigger(double a, double b) { if (a > b) return a; else return b; } int main() { double max1, max2, max3; char bet1, bet2, bet3; double w, t, l; scanf("%lf%lf%lf", &w, &t, &l); max1 =…
pat 1009. Product of Polynomials (25)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1009 题意:计算多项式的乘积。 分析:基于编程方便,还是采用数组的方式来实现。 #include<stdio.h> typedef struct Poly { int exp; double coe; } Poly; Poly a[1005]; Poly b[1005]; double res[2005]; int main() { int n; scanf("%d", &n); int i; for (i = 0; i < n; i++) { scanf("%d%lf", &a[i].e…
pat 1008. Elevator (20)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1008 题意:给出楼层序列计算电梯运行时间。 分析:简单模拟题。 #include<stdio.h> int main() { int n; int count = 0; int cur = 0; int tmp; scanf("%d", &n); while (n--) { scanf("%d", &tmp); if (tmp > cur) { count += (tmp - cur) * 6 + 5; } else if (tmp < cur) { count += (cur - tmp…
pat 1007. Maximum Subsequence Sum (25)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1007 题意:经典的最大连续子串问题。 分析:采用最优的O(N) 算法。 #include<stdio.h> int seq[10005]; int main() { // freopen("in.txt", "r", stdin); int n; scanf("%d", &n); int i; for (i = 0; i < n; i++) scanf("%d", &seq[i]); int maxSum = -1; int left, right; int thisSum = 0; in…
pat 1006. Sign In and Sign Out (25)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1006 题意:分析每个人到达和离开实验室的时间,找到最早来和最晚走的人。 分析:简单的一次遍历寻找最大最小值,我直接利用字符串比较时间的大小,也可以读入int 转化成分钟处理。 #include<stdio.h> #include<string.h> char firstPer[20]; char lastPer[20]; char firstTime[20] = "23:59:59"; char lastTime[20] = "00:00:00"; int main() { int n; …
pat 1005. Spell It Right (20)
链接: http://pat.zju.edu.cn/contests/pat-a-practise/1005 题意:计算一个大数每位数字相加之和,结果输出每位数字对应的英文。 分析:结果输出利用hash的思想。 #include<stdio.h> int arr[20]; int idx = 0; char str[10][10] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" }; int main() { char ch; int sum = 0; while (1) {…
1002. A+B for Polynomials (25)
链接:http://pat.zju.edu.cn/contests/pat-a-practise/1002 题意:多项式相加并且格式化输出。 分析:指数范围不大,可以简单用数组实现,数组的索引对应指数,内容对应系数。 #include<stdio.h> double result[1005]; int main() { int k; scanf("%d", &k); int exp; double coe; while (k--) { scanf("%d%lf", &exp, &coe); result[exp] += coe; } scanf("%d", &k); while (k--) …