大内高手

题解

前端(1)

/ 注册

全部文章 / 题解（共29篇）

PAT1010 - Radix

这题看起来不难，实际上并不是一道简单的进制转换问题，有几点需要注意。没有给最大的radix，第一次提交我最大radix设置到了100，只有第7个测试点错误，其余全部正确，于是我把radix设置到了10000，还是只有第七个测试点错误，设置到了1000000，这时有测试点TLE了。。。根据1可知...

CPP PAT

2020-04-04

0 755

PAT1012 - The Best Rank

此题虽说不是什么高级算法题目，但是很多细节方面很到位。本题“坑位”：总分是四舍五入，而不是向下取整 exist数组里保存的应该是四次单科排序过后的index+1，这里+1是为了规避0，因为全局int数组默认初始化为0 sort四科需要四个compare函数，但是cmp很巧妙的只写一个函数就OK...

CPP PAT

2020-04-04

0 656

PAT1007 - Maximum Subsequence Sum

这是一道求最大连续子序列和的问题(DP问题)。除了求最大连续子序列的和之外，还需要输出最大连续子序列的起点和终点的值。 // runtime: 8ms // space: 424K // https://pintia.cn/problem-sets/994805342720868352/proble...

CPP DP PAT

2020-04-03

0 1154

PAT1004 - Counting Leaves

此题考查树的层序遍历，需要记住的是层数n // runtime: 3ms // https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184 #include <iostream> #inclu...

树的遍历 CPP PAT

2020-04-02

0 599

Dijkstra最短路径问题 - Emergency[PAT真题]

这是一道Dijkstra最短路径的变种问题。注释里面写的比较详细了，标注上关键代码部分需要仔细思考一下，如果还是不懂，欢迎留言。 // runtime: 4ms // space: 384K // https://pintia.cn/problem-sets/994805342720868352/p...

CPP 图论最短路径

2020-04-02

0 601

HDU1874 - 畅通工程续

此题是经典的Dijkstra单源最短路径问题。 // runtime: 33ms #include <iostream> #include <algorithm> #include <climits> #include <vector> #includ...

CPP 图论最短路径 HDUOJ

2020-03-31

0 629

HDU3342 - Legal or not?

这是一道关于拓扑排序的题目 #include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; const int MAX =...

CPP 拓扑排序图论 HDUOJ

2020-03-31

0 688

最小生成树 - 还是畅通工程

这是一道典型的最小生成树的题目，利用Kruskal算法，先按照road的长度排序，若当前的road未在连接好的“城市组”里，则连通它。直到所有的城市全部连通，即所铺路径最短。 // runtime: 6ms // space: 488K #include <iostream> #inc...

最小生成树 CPP 图论

2020-03-29

1 779

并查集题目 - Is it a tree?

并查集的题目 // runtime: 4ms // space: 608K #include <iostream> using namespace std; const int MAX = 10000; int father[MAX]; int height[MAX]; int in...

CPP 图论并查集

2020-03-28

2 689

0-1背包变形

代码和0-1背包非常之像，只是由原来的容量固定，求最大价值，最小邮票数是每个邮票的价值(权重)一样，都为1(枚)，在背包大小固定的情况，求最少的邮票数。 // runtime: 4ms // space: 496K #include <iostream> #include <alg...

CPP 背包问题 DP

2020-03-23

1 841