ACM

2016HUAS_ACM暑假集训3-Kruskal、Prim、Dijkstra、Spfa等几种算法的比较

2016HUAS_ACM暑假集训3-Kruskal、Prim、Dijkstra、Spfa等几种算法的比较
2016-07-31 ACM,2016HUAS_ACM暑假集训,图论 2390 100
一直都是在刷题，从来没总结过算法，这样不好啊，特别是这周，发现这么多算法，好多都有相似之处，所以，来个总结把。下面是总结表：算法时间复杂度关键词特性KruskalO（nlogn）最小生成树算法、 维护森林、 并查集、 路径压缩、 稀疏图Kruskal算法主要是运用了并查集的思想，将集合外的元素加入集合中。这个算法的一个重点在于要先排序，然后按照从小到大的顺序取点不断加入集合。它不像其它几种算法，它... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3 - H - Funny Car Racing

2016HUAS_ACM暑假集训3 - H - Funny Car Racing
2016-07-28 ACM,2016HUAS_ACM暑假集训,图论 1604 5
H - Funny Car Racing        这个题呢，也是一个计算加权最短路径的题目，只不过它不是单独的加权，还要考虑时间问题，属于动态权值，所以我们在通过某个通道时，判断是直接通过还是等待通过就好了，理论上来说也有好几个算法可以AC，@happy_code就用了spfaAC的。看网上别人的博客都... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3 - B - Frogger

2016HUAS_ACM暑假集训3 - B - Frogger
2016-07-27 ACM,2016HUAS_ACM暑假集训,图论 1441 45
其实这个题目读懂题目意思就已经成功一半了。下面是从别处找来的翻译。Description一只叫Freddy的青蛙蹲坐在湖中的一块石头上。突然他发现一只叫Fiona的青蛙在湖中的另一块石头上。Freddy想要跟Fiona约会，但由于湖水太脏，他不想游泳过去而是跳过去找Fiona。很不幸，Fiona所在的石头距离他有点远，甚至超出了他的跳跃能力。然而Freddy注意到湖中还有一些其他的石头。这些石头也... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3 - POJ 1251 - Jungle Roads

2016HUAS_ACM暑假集训3 - POJ 1251 - Jungle Roads
2016-07-26 ACM,2016HUAS_ACM暑假集训,图论 1468 30
这个题就是畅通工程的翻版好吗，一样可以用Prim和Kus算法来解。要注意的就是输入输出，cin、cout可能更好用 一以前的代码写的太low，更新了一下代码，prim改为优先队列优化，kruskal删除了一个莫名Wa的父节点交换，还是太年轻啊 题目：飞机票直达（F - Jungle Roads） 下面是代码： Prim算法： #include <iostream> #include &... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3-C - Til the Cows Come Home

2016HUAS_ACM暑假集训3-C - Til the Cows Come Home
2016-07-25 ACM,2016HUAS_ACM暑假集训,图论 1477 25
        题目意思大概是给出T条边，N个点。求第一个点到第N个点的最短距离。开始是n*n次直接循环，然后挂了，总是出现莫名其妙的数字（memset造成，memset使用要谨慎啊！！！）。后来看博客发现用Dijkstra算法求。从1开始，找出距离当前位置距离最小而且最远的点，然后通过这个点找他能到达的边的距离和当前... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3-G - 还是畅通工程

2016HUAS_ACM暑假集训3-G - 还是畅通工程
2016-07-25 ACM,2016HUAS_ACM暑假集训,树,并查集,图论 1328 6
G - 还是畅通工程        题目意思是找使公路路径最小。也就是最小生成树。但是这里应该有多种解法，我看了两种解法，一种是Prim最小生成树算法，一种是使用类似并查集思想的Kruskal算法。个人感觉Kruskal算法比prim算法好理解一些，但是Kruskal算法的效率要比Prim低。题目：飞机票直达... 继续阅读 »
ACM

2016HUAS_ACM暑假周测2-C - 小Q系列故事——最佳裁判

2016HUAS_ACM暑假周测2-C - 小Q系列故事——最佳裁判
2016-07-22 ACM,2016HUAS_ACM暑假集训 1530 0
C - 小Q系列故事——最佳裁判找最佳裁判，这个题我WR7次，TLE一次，尝试了二分法，排序，未果。后来直接查找，找距离最短的那个裁判（这个非常重要）才得以AC，而且时间是0ms。其实排序那里应该是有个距离问题没注意到，就是最短距离的前后编号在原始编号的大小。Description　　过去的2012年对小Ｑ来说是很悲催的一年，失恋了12次，每次都要郁闷1个来月。 　　好在小Q是... 继续阅读 »
ACM

2016HUAS_ACM暑假集训2-B - The Suspects

2016HUAS_ACM暑假集训2-B - The Suspects
2016-07-22 ACM,2016HUAS_ACM暑假集训,树,搜索,并查集 1428 0
B - The Suspects这个题是并查集的应用，如何找到可能的患者？我们只需要把和患者（编号0）会牵扯到一起有关联的社团全都加在一个父节点下面就行了，虽然使用了路径压缩算法，但是最后还是可能会存在树高为3的树，所以这里的路径压缩并不彻底，AC的时间比大部分高，还有待优化（其实优化过一次，不过是错的）。#include <iostream> //#includ... 继续阅读 »
ACM

2016HUAS_ACM暑假集训2-F - A Simple Problem with Integers

2016HUAS_ACM暑假集训2-F - A Simple Problem with Integers
2016-07-22 ACM,2016HUAS_ACM暑假集训,树 1495 0
F - A Simple Problem with Integers        这个题也是二叉搜索树的应用，但是考虑到数据是一个区间更新而不是单点更新，所以每个点都更新的话计算量太大会导致TLE,网上搜索之后看到基本上是使用“lazy”思想。所以更改几行关键代码就能AC了。  &nbs... 继续阅读 »
ACM

2016HUAS_ACM暑假集训2-E-I Hate It

2016HUAS_ACM暑假集训2-E-I Hate It
2016-07-21 ACM,2016HUAS_ACM暑假集训,树,搜索 1154 0
E - I Hate It这个题嘛，我也只能说坑，感觉二叉搜索树到处都是坑啊。这不过是二叉搜索树的简单应用吗？建树，更新，查找。不可能有错啊。和上一个敌兵布阵一样，我cin、cout也没用了啊，为什么？好吧，继续“I Hate It TLE”搜索。好了，找到了，数组开小了就会TLE，我。。。Description很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是... 继续阅读 »
1 2 3 末页