加载中…
博文
(2014-01-20 18:10)
现在搬到这里了
http://townboy.net
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 

    本来很久之前就打算开始做这个专题,也没太多完整时间,现在集中做一下 http://220.166.52.162/oj/problemlist?p=8 这个oj上能评测

    建图是白色字体 全选就能看见。

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

    这道题的做法和克鲁斯卡尔算法过程上差不多,都是利用了并查集的性质,那么在证明上是不是也可以借鉴一下MST呢?

    先介绍一下MST性质     最小生成树性质:设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。若(u,v)是G中一条“一个端点在U中(例如:u∈U),另一个端点不在U中的边(例如:v∈V-U),且(u,v)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)。

    那么接下去证明这道伪森林,如果在将边集按照权值大到小排序之后,如果可以选择某条边,两顶点为u和v,那么这条边有两种情况,第一种是u和v是处于同一个连通分量里面,暂且把这个连通分量叫做UU,这条边叫做X,那么如果此边不选,在之后的选边过程中,假如之后没有添加关于UU的边,那么证明成立,这条边选入是最优解,假如之后有选择关于UU的边,那么之后选择的必定权值小于X的权值,那么如果新选的也存在两种情况,一种是沟通UU内部的边,那么撤去新选择的边

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2012-07-17 13:04)
标签:

hdu

树状数组

杂谈

分类: hdoj题库

    树状数组题,题目本身不难,但是证明呵呵,还是思维能力太弱了。

    关于证明,假如任意一个数字左边有N个比它大的数字,那么在最后的排序结果中是升序的,那么左边这些数字必定要跑到这个的右边去,必定发生的交换次数就是N次,需要的时间最小就是左边的这些数的和加上对应的这个数字自身的消费。这是下限。

    假如左侧的这些数列已经处于升序状态,那么刚好就可以把最右边的数字与N个比它大的数字进行交换,相当于一个插入排序,这样的话可以重新构成一个升序序列。每个数字的下限都可以取到,这也就证明了最小次数就是这个每个数字左侧比它大的那些数字的花费和本身交换所产生的花费。

   具体的交换流程就是对于一个左侧的升序序列把任意一个值插入重新构成一个升序序列。就是一个插入排序的流程。

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2012-07-16 19:41)
标签:

杂谈

分类: hdoj题库

    这道题终于用树状数组过掉了,TLE了很久很久,这道题时间真的卡的比较紧,最后花了1500ms,刚开始的作法是每行从左至右进行求中位数的操作,关于求中位数这点,真的学到了一个很棒的函数,可以用很高效的效率求出树状数组中第K大的元素,原来之前一直是用普通的二分写的.但是每行从左至右还是TLE,于是让求中位数的操作改走S路线,这样终于过了.

附个代码:

 

#include<stdio.h>
#include<memory.h>
#define lowbit(t) (t&(-t))

int MAX,n,r;
int in[1100000],old[510][510],neww[510][510],k;

void plus(int pos,int v)
{
    while(pos <= MAX)
    {
        in[pos]+=v;
        pos+=lowbit(pos);
     
}

int sum(int end)
{
    int sum=0;
    while(end > 0)
    {
    &

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2012-07-14 21:48)
标签:

杂谈

分类: hdoj题库

    这两道题目都是树状数组的题目,都是更新区间求点,树状数组的特征是点更新,区间求和.

虽然1556是一维的 3584是三维的,思想是一致的,记录产生作用的边界点,对这些点进行区间求和.

在操作上可以N维的就记录2^N 个边界点.

    如果是三维的,对长方体的8个顶点进行标记,其中4个+1,4个-1. 还是有规律可循的.

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2012-07-06 14:54)
标签:

杂谈

分类: hdoj题库

题目大意:

    在一个平面上,存在两条线段,题目告诉你在分别在两条线段上的速度和平面上其余地方的速度,让你求线段上一点A到线段上另外一点D 的最短时间。

 

分析:

    这道题是一个三分搜索,但是可能会比较难想到,因为自己就想了很久,首先,时间最短的路径必定是至多3条直线段构成的,一条在AB上,一条在CD上,一条架在两条线段之间。

    其次,如果有一个固定的点,求到另外一条线段上的一个端点上的最短距离,怎么做呢,可以通过三分来解,应该可以想到,枚举线段上的两个端点作为左右两个端点。这样线段上每个点作为中间点的距离从固定点到线段上的端点的距离就构成了一个凹形函数,这样子就可以用三分枚举出最小值。

    接着我们就用三分枚举AB上的那个最小值点,通过确定的那个点,在CD上三分出最小值。这样子通过三分嵌套三分的算法。就可以确定出答案了。

 

总结:

    在二分三分的应用上是非常灵活的,关键是建立好的模型。   

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2012-07-02 19:51)
标签:

杂谈

分类: hdoj题库
    题目的意思就是在普通的31背包之外对于每个物品加上了一个需要购买它的金额限制,普通的01背包不行,这道题关键就在于对于q-p先进行从小到大的排序 至于为什么呢,真的想不通。以后再搞懂。
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2012-07-01 21:04)
标签:

背包

dp

杂谈

分类: hdoj题库

    这道题是一道 背包 ,但又不是普通的背包,特殊在于题目要求满足当前余额满足5元才能购买物品,所以如果 直接用背包来解的话其实是不对的,因为这样带有限制的背包求出来的并不是真实饭卡里能剩的最小值。

    这道题就可以转化一下,如果为了要是饭卡里剩的钱最少,所以最贵的菜一定是最后买的,这样的一定是最优解,而要买最贵的菜,所以卡里的钱 一定是大于等于五元的,所以这个时候对于其他剩余的n-1道才来说,就是一个普通的01背包了。直接求解就可以了。

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2012-06-21 18:41)
标签:

杂谈

分类: hdoj题库

此题就是一个二分匹配

刚开始存在的问题

1.点最多有36万个,然后就用了vector过了,但是时间花了500ms左右 比较慢

可以改进的地方,此题的二分匹配不用再正式的图上进行,其实可以像其他深搜的题目一样在真实图上进行,每次向周围4个方向上进行扩展,时间上就可以大大优化。

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
搜博主文章
个人简介
夏天到了
春天小猪要加油啦啦啦
我要做彩虹猪
为成都赛区加油
友情链接

hqhome

学习计算机 关注互联网

个人资料
春天小猪
春天小猪
  • 博客等级:
  • 博客积分:0
  • 博客访问:6,163
  • 关注人气:3
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
分类
  

新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有