ACM

BZOJ 3211 花神游历各国(线段树)

BZOJ 3211 花神游历各国(线段树)
题意:就是中文,都能看懂。看到区间很大,肯定得上线段树。不过这里直接上线段树肯定还是TLE,所以得用一种类似于剪枝的方法,当一个数多次开根号之后肯定是1了,所以一旦为1就不要往下更新?题目地址:http://www.lydsy.com/JudgeOnline/problem.php?id=3211代码:Memory: 7552 KBTime: 1976 MSLanguage:&... 继续阅读 »
ACM

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

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

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

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

2016HUAS_ACM暑假集训2-D - 敌兵布阵

2016HUAS_ACM暑假集训2-D - 敌兵布阵
D - 敌兵布阵二叉搜索树的问题,求区间最大数。这个题嘛,只能说坑,坑到死,写程序和调试程序的时间大概是1:2,一遍写好,之后就一直在Debug,我就说我逻辑没错吧,为了检查我把别人的c语言代码全部移植过来,也是TLE,难道是我主程序有问题?怎么可能!!!找了好久,最后用“敌兵布阵 TLE”作为关键词搜索,发现,原来是c++里面的cin、cout太耗费时间,我...Description... 继续阅读 »
ACM

2016HUAS_ACM暑假集训2-A - Is It A Tree?

2016HUAS_ACM暑假集训2-A - Is It A Tree?
L - Points on Cycle        这个题本来是应该要用并查集来解决的,但是仔细想想也可以不用,根据离散数学,树是没有连通回路的图,而且  节点数=边数+1,所以,通过判断这棵树有没有同时指向一个点的多条边,以及 节点数=边数+1就行了,然后空树也是树,所以这样就截出来了... 继续阅读 »