about 3 years ago

左偏树见论文。。。这篇博客只是证明我学过左偏树。。。
一道裸题hdu1512.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1056
分析:
平衡树裸题。。。为何我的常数那么丑= =。
bzoj1056.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1055
分析:
很显然的一道题。
表示区间是否可以用来得出。
那么方程就是
时间复杂度
bzoj1055.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1054
分析:
很明显状态数很少,我们直接就好。
bzoj1054.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1053
分析:
我们知道答案可以化成一系列质数幂之积。
即:,不妨设。根据贪心原则必定是质数表的前面连续若干项,且。因为这样的数非常少,我们可以直接搜索。。。
bzoj1053.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1052
分析:
很明显我们要二分答案,然后解决判定的问题。
我们考虑一个包括了所有点的最小矩形,那么其四条边上都一定有点。
而我们只有三个正方形,也就是说至少有一个正方形在矩形的一角上。
我们考虑枚举第一个矩形放在哪个角上,删去覆盖掉的点,剩下的就变成了一个子问题。
bzoj1052.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1051
分析:
很显然我们先缩环,一个环内的点要么都是答案,要么都不是。
这样我们得到了一个,我们只要求上是否有点满足其他所有点都可以到达它。
我们将新图上的边反转一下,记录入度为的点,如果超过一个,那么很显然无解,否则我们以那一个点为源点一遍判断即可。
bzoj1051.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1050
分析:
首先我们肯定要按照边的大小排序,然后枚举哪一条边是当前的最小边,接着再确定最大边。
那么我们怎么求出这个最大边。。。暴力重建最小生成树是可以过的(虽然很慢),然而我们可以在中动态加边维护最大边,这样会快很多。
暴力重建树
动点spfa

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1049
分析见http://pan.baidu.com/share/link?uk=2651016602&shareid=1490516411
bzoj1049.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1048
分析:
一道跟前面某道搜索题类似的题。
均方差就是标准差,然后我们可以忽略跟号和除以,只记录平方和即可。
表示左上角为,右下角为,分割为块的最小平方和,然后就是枚举横竖分割多少块即可。
bzoj1048.cpp