浙大PTA数据结构与算法题目集（中文）题解集复习用 |
您所在的位置：网站首页 › pta题目以及答案 › 浙大PTA数据结构与算法题目集（中文）题解集复习用 |
|
文章目录
7-1 最大子列和问题 (20分)（dp或贪心）7-2 一元多项式的乘法与加法运算 (20分)7-3 树的同构 (25分)7-4 是否同一棵二叉搜索树 (25分)7-5 堆中的路径 (25分)（数据结构--堆）7-6 列出连通集 (25分)（BFS、DFS遍历图）7-7 六度空间 (30分)（遍历节点进行BFS）几个求最短路算法的比较与分析（面试前再看看）
7-8 哈利·波特的考试 (25分)（多源最短路floyd）7-9 旅游规划 (25分)（单源最短路dijkstra）求最小生成树算法的比较与分析
7-10 公路村村通 (30分)（最小生成树prim）7-11 关键活动 (30分)7-12 排序 (25分)7-13 统计工龄 (20分)（桶排序或直接用map）7-14 电话聊天狂人 (25分)（stl-map应用）std::[string](http://www.cplusplus.com/reference/string/string/)::compareReturn Value
7-15 QQ帐户的申请与登陆 (25分)（用stl-map简单模拟）7-16 一元多项式求导 (20分)7-17 汉诺塔的非递归实现 (25分)7-18 银行业务队列简单模拟 (25分)（模拟）7-19 求链式线性表的倒数第K项 (20分)（vector简单使用）7-23 还原二叉树 (25分)（树）7-24 树种统计 (25分)（string类型的输入和输出）7-25 朋友圈 (25分)（并查集）7-26 Windows消息队列 (25分)（stl-priority_queue）7-29 修理牧场 (25分)（优先队列实现哈夫曼树）7-31 笛卡尔树 (25分)（BST判断的变式）7-32 哥尼斯堡的“七桥问题” (25分)（欧拉回路）7-33 地下迷宫探索 (30分)（dfs遍历图）7-34 任务调度的合理性 (25分)（验证是否为拓扑序列）7-36 社交网络图中结点的“重要性”计算 (30分)（无权图BFS）7-37 模拟EXCEL排序 (25分)（重载sort函数进行自定义排序）7-38 寻找大富翁 (25分)（优先队列实现最大堆）7-39 魔法优惠券 (25分)（贪心）7-40 奥运排行榜 (25分)7-41 PAT排名汇总 (25分)7-50 畅通工程之局部最小花费问题（最小生成树kruskal）还是畅通工程
7-1 最大子列和问题 (20分)（dp或贪心）
给定K个整数组成的序列{ N1, N2, …, N**K }，“连续子列”被定义为{ N**i, N**i+1, …, N**j }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。 本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下： 数据1：与样例等价，测试基本正确性；数据2：102个随机整数；数据3：103个随机整数；数据4：104个随机整数；数据5：105个随机整数；输入格式: 输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。 输出格式: 在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。 输入样例: 6 -2 11 -4 13 -5 -2输出样例: 20 #include #include using namespace std; int main(){ //dp[i]表示到i为止最大的子数组和 //dp[i+1] = max(dp[i] + a[i], a[i]) int dp[100005]={0}; int a[100005]; int k; cin>>k; for(int i = 0; i < k; i++){ cin>>a[i]; } int sum = -1; dp[0] = a[0]; for(int i = 1; i < k; i++){ dp[i] = max(dp[i-1] + a[i], a[i]); } for(int i = 0; i < k; i++){ sum = max(sum, dp[i]); } if (sum < 0) sum = 0; printf("%d", sum); return 0; } 7-2 一元多项式的乘法与加法运算 (20分)设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。 输出格式: 输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。 输入样例: 4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1输出样例: 15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1 5 20 -4 4 -5 2 9 1 -2 0 #include using namespace std; int main(){ int n, a[1005] ={0}, coff, exp, muti[2001] = {0}, add[1005]={0}; cin >> n; for(int i = 0; i < n; i++){ cin >> coff >> exp; a[exp] = coff; add[exp] = coff; } cin >> n; for(int i = 0; i < n; i++){ cin >> coff >> exp; for(int j = 0; j < 1005; j++){ muti[exp + j] += a[j] * coff; } add[exp] += coff; } int cnt = 0; for(int j = 2000; j >= 0; j--){ if(muti[j]!=0){ if(cnt){ cout b; if(op == 'L'){ //老帐户登陆 if(m.count(a) 1){ int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); int t = a + b; cout node[i].k2 >> node[i].lchild >> node[i].rchild; } //找根节点 for(int i = 0; i < n; i++){ vis[node[i].lchild] = 1; vis[node[i].rchild] = 1; } for(int i = 0; i < n; i++){ if(!vis[i]) { root = i; break; } } if(IsVaild(root, MIN, INF)){ cout > m; for(int i = 0; i < m; i++){ scanf("%d%d", &b, &c); //别用cin a[b][c]=a[c][b] = 1; cnt[b]++; //记录每一个顶点的度数 cnt[c]++; } dfs(1); int f = 1; for(int i=1; i m >> s; for(int i = 1; i m; for(int j = 1; j > t; g[t][i] = 1; a[i]++; } } queue q; for(int i = 1; i 0){ int cur = q.front(); q.pop(); for(int i = 1; i > m; for(int i = 0; i < m; i++){ int a, b; scanf("%d%d", &a, &b); adj[a].push_back(b); adj[b].push_back(a); //别忘了是个无向图 } cin >> k; for(int i = 0; i < k; i++){ int target; scanf("%d", &target); printf("Cc(%d)=%.2f\n", target, bfs(target, n)); } return 0; } double bfs(int x, int n){ for(int i = 1; i 0){ return b.sno < a.sno; } return b.sno > a.sno; } return a.score < b.score; } int main(){ int n, c; cin >> n >> c; for(int i = 0; i < n; i++){ scanf("%s%s%d", s[i].sno, s[i].name, &s[i].score); } if(c == 1){ sort(s, s+n, cmp1); for(int i = 0; i < n; i++){ printf("%s %s %d\n", s[i].sno, s[i].name, s[i].score); } }else if(c == 2){ sort(s, s+n, cmp2); for(int i = 0; i < n; i++){ printf("%s %s %d\n", s[i].sno, s[i].name, s[i].score); } }else if(c == 3){ sort(s, s+n, cmp3); for(int i = 0; i < n; i++){ printf("%s %s %d\n", s[i].sno, s[i].name, s[i].score); } } return 0; } 7-38 寻找大富翁 (25分)（优先队列实现最大堆）胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。 输入格式: 输入首先给出两个正整数N（≤106）和M（≤10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。 输出格式: 在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。 输入样例: 8 3 8 12 7 3 20 9 5 18输出样例: 20 18 12 #include #include #include using namespace std; int main(){ int n, k; priority_queue pq;//less规定优先队列的顺序为从大到小排列，即队头为最大的 cin >> n >> k; for(int i = 0; i < n; i++){ int x; scanf("%d", &x); pq.push(x); } int flag = 0; while(k-- && pq.size()>0){ if(flag){ cout > n; for(int i = 0; i < n; i++){ scanf("%d", &b[i]); } sort(a, a+n); sort(b, b+n); int sum = 0; int i; for(i = n-1; i>=0; i--){ //正*正 = 正 if(a[i]>0 && b[i]>0){ sum += a[i]*b[i]; }else{ break; } } for(int j = 0; j < i; j++){ //负*负 = 负 if(a[j] return cost if(parent[num] == num) return num; return parent[num] = findParent(parent[num]); } void Union(int a, int b) { int pa = findParent(a); int pb = findParent(b); if(pa != pb) parent[pb] = pa; } int main() { int N, cnt, a, b, mon, build; vector v; scanf("%d", &N); cnt = N * (N - 1) / 2; // 初始化集合 for(int i = 0; i a, b, mon}); } int sum = 0; // Kruskal sort(v.begin(), v.end()); for(int i = 0; i sum += v[i].cost; Union(v[i].a, v[i].b); } } printf("%d", sum); return 0; } 还是畅通工程题目描述 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 输入描述: 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。输出描述: 对每个测试用例，在1行里输出最小的公路总长度。示例1 输入 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0输出 3 5 #include #include using namespace std; #define maxn 10005 struct edge{ int from, to, w; bool operator}; int Find(int x){ if(f[x] == x) return x; return f[x] = Find(f[x]); } int main(){ int n; while(cin >> n && n!=0){ for(int i = 0; i int a, b, w; scanf("%d%d%d", &a, &b, &w); e[j].from = a; e[j].to = b; e[j++].w = w; } sort(e, e+j); //Kruskal int ans = 0; for(int i = 0; i ans += e[i].w; f[rb] = ra; } } cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |