ACM

CodeForces 696A Lorenzo Von Matterhorn(STL)

CodeForces 696A Lorenzo Von Matterhorn(STL)
看着挺像线段树的,不是吗?但是不是,这是个STL中map的应用。开始看数据,只有q个命令,u、v的数据也不算很大,有没有什么办法可以把命令存起来就好了。像python中字典那样,后来发现C++中的map,好东西啊。说下思路,因为要计算u->v的权值之和,我们可以把权值放在v中,由于题目中给定的u、v特性,我们可以从最后一个v开始倒回来每次除以2,然后把权值加起来就好了,注意输入的区间大小值。... 继续阅读 »
ACM

POJ 3660 Cow Contest(传递闭包)

POJ 3660	Cow Contest(传递闭包)
求出每个点能到达的点。如果有一个点,排名在它之前的和排名在它之后的点之和为n-1,那么它的排名就是确定的。Floyd即可。题目地址:http://poj.org/problem?id=3660代码:Memory: 712 KBTime: 63 MSLanguage: G++Result: Accepted#include <iostream&... 继续阅读 »
ACM

SCU-2090 单色三角形(计数)

SCU-2090	 单色三角形(计数)
题意:找具有三条边颜色相同的三角形数这个题数据比较水,直接暴力也能过,不过@freeloop建议我们用单色三角形理论去计算,于是看了别人的题解。大致就是先求出非单色三角形数目,然后用总的减去非单色三角形。总的数目是C(n,3),非单色三角形我们只需要遍历每个点,看看他的边是否具有同样颜色(这里要注意除以2,因为遍历三角形另外点的时候具有重复计算)就可以了。题目地址:http://acm.scu.e... 继续阅读 »
ACM

CodeForces 690C2-Brain Network (medium)

CodeForces 690C2-Brain Network (medium)
题目意思就是给你一棵树,保证这颗树的合法性,然后加入要你判断这棵树最长的路径是多长。这里有个小技巧就是从任意一点开始出发找到最远的一点再从这一点出发寻找最远点,之后找到的最远点就是整棵树的最远点了。题目:http://codeforces.com/problemset/problem/690/C2代码:Memory: 5400 KBTime: 108 MSLanguage:&n... 继续阅读 »
ACM

CodeForces 690C1-Brain Network (easy)

CodeForces 690C1-Brain Network (easy)
判断是不是一棵树的问题,不能成环。使用Kruskal判断就可以了。题目:http://codeforces.com/problemset/problem/690/C1代码:Memory: 16 KBTime: 15 MSLanguage: GNU G++ 5.1.0Result: Accepted#include<iostream>#includ... 继续阅读 »
ACM

2016HUAS_ACM暑假周测3 - C - 畅通工程续

2016HUAS_ACM暑假周测3 - C - 畅通工程续
C - 畅通工程续这个题目嘛就是求最短路径咯,比赛的时候想的是Dij,然后用了邻接矩阵过的。效率比较低。而且比赛的时候换了好几种算法都是错的,一定要注意边界值的问题!!!下面贴出比赛时的代码,和后来的两段优化代码。题目:飞机票直达(C - 畅通工程续)1、Dijkstra+邻接矩阵Memory: 1964 KBTime: 46 MSLanguage: C++... 继续阅读 »
ACM

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

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

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

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

2016HUAS_ACM暑假集训3 - B - Frogger

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

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

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