dango

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

2011年3月5日 #

POJ2750 Potted Flower(线段树区间更新)

传送门: http://poj.org/problem?id=2750

题目大意:
一堆花围成一圈,每一盆都有自己的attractive value。要你来选一串花,使得总attractive value最大。(题目中有一个非常重要的条件:不可以选所有的花,这个一不注意就功亏一篑了)
每次,有一只坏猫会来把第A盆花的attractive value换成B。坏猫每捣蛋一次,你就要求一个新的总attractive value最大的连续序列。

解题思路:
数据那么大,暴力搞肯定超时了,这种区间最大最小值的问题首先还是应该要想到线段树的。
1 struct tnode 
2 {
3     int sum,mins,maxs;      //当前区间的和、最小子序列和、最大子序列和 
4     int lmin,lmax;          // 当前区间从left出发所能形成的 最小子序列和、最大子序列和 
5     int rmin,rmax;          // 当前区间以right结尾所能形成的 最小子序列和、最大子序列和
6     //int minn;           //当前区间最大最小值 
7 }t[maxn*4];
线段树的节点定下来以后写法差不多也就定了。
每次需要根据孩子的情况来更新父节点的各种值。判断的时候一定要把“转移”(这个挺像动态规划的状态转移的其实……)情况都想齐全,再下手写,写的时候比较容易晕,一定要仔细,避免查错的时候头昏脑胀。
WA了一次,有一个地方没写好。题中说不可以选取所有的花,所以若得到的总attractive value最大的连续序列是整圈的花,就要剪掉整圈花总attractive value最小的连续序列的attractive value和,WA的时候之剪了最小attractive value的一盆花。

代码:(注释掉的一些地方是第一次错的地方,引以为戒~)
POJ2750
posted @ 2011-03-05 21:07 Dango 阅读(553) | 评论 (0)编辑 收藏

     摘要: 写了题还是应该来总结一下,否则除了个别刻骨铭心的题以外,都忘掉了。 POJ2155题目大意:给一个N*N的矩阵,每次给一个命令取反一个子矩阵,或者查询其中某一点的01状态。(注意每两组output中间要空行,PE了一次) 解题方法;二维线段树。 解题小结:原先好像写过二维的线段树,不过都忘得差不多了,这一次算是重新捡起来吧。这一道题可以用a[rootx][rooty]来记录rootx段到ro...  阅读全文
posted @ 2011-03-05 17:04 Dango 阅读(722) | 评论 (0)编辑 收藏

2010年10月8日 #

     摘要: 准备ACM,看了一下STL库。http://www.docin.com/p-46121844.html豆丁这个PDF不错,福州大学的,感觉简明扼要刚好够ACM用。很水,所以做水题。每一道题都能多发现几个有用的函数。map很多时候都不是最好的办法,自己写hash估计其实会更快的,不过既然是熟悉map,就全部用map了。相关的POJ题目, 搜索"poj map"然后找出来的可以用map解决的题目。PO...  阅读全文
posted @ 2010-10-08 21:17 Dango 阅读(574) | 评论 (0)编辑 收藏

2010年8月26日 #

     摘要: [hdu3236] Gift Hunting (转自自己的CSDN博客) 一、题目描述 原题地址: http://acm.hdu.edu.cn/showproblem.php?pid=3236 GG有两张奖券,面额分别为V1、V2,准备给MM买礼物。当天是MM生日,所以MM还可以免费得到一份礼物。 礼物有价格和幸福值两个参数,并且礼物分为特殊礼物和普通礼物,特殊礼物是一定要全部到手的。 ...  阅读全文
posted @ 2010-08-26 20:47 Dango 阅读(237) | 评论 (0)编辑 收藏

     摘要: [hdu3234] Exclusive-OR (从自己的CSDN博客转来的) 一、题目描述 http://acm.hdu.edu.cn/showproblem.php?pid=3234 存在n个正数。题目逐渐给出信息或询问。 如果中途出现冲突,输出有冲突,其余语句全部忽略。 详见原题。 二、准备知识 对于a,b,c有:a xor b == c 和 a xor c == b 和 b ...  阅读全文
posted @ 2010-08-26 20:46 Dango 阅读(354) | 评论 (0)编辑 收藏

Hdu 3265 Posters

题目描述:

    原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=3265

    很多很多海报,每张海报又被挖掉了一个长方形。求这些海报的覆盖面积。

题目分析:

    一张海报可以拆成四个矩形处理。线段树。

小结:

Long long 还是不要用printf输出,用cout吧……

posted @ 2010-08-26 20:45 Dango 阅读(213) | 评论 (0)编辑 收藏

Hdu 3237 Help Bubu

题目描述:

    原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=3237

    题目可以抽象成这样,有0~7这样8个数字组成的数字串,可以抽出k个数字再插回到任意位置,问最后不同的数字段(相同的数字组成一段,例如00077112有4段,000为一段,77为一段……)

 

题目分析:

    这个题乍一看很像动态规划,但是真的是动态规划,不过我还是第一次做这样的动态规划。

    参考了一位大牛的报告,地址如下:

F[i][j][k][s],表示前i本书,拿走j本,留下的书最后一本高k(呃我觉得这个很巧妙),留下的书的组合为s(例如1010000表示高度为0的,高度为2的书有留下的)

    状态转移部分伪代码(当处理到f[i][j][k][s]时)

(1)  考虑第i本书不抽走,在f[i-1][j][k][s]存在的前提下(也就是处理到i-1本书的时候,这个状态下,留下的最后一本书高度为k):

若这本书的高度也是k,那么这本书的加入不会造成混乱度的提升,f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s])

若这本书的高度不是k,那么这本书的加入会造成混乱度增加1,则f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s] + 1)

(2)考虑抽走第i本书,f[now][j+1][k][s] = min( f[pre][j][k][s], f[now][j+1][k][s])

最后处理答案的时候要考虑一下那些被抽走的书还是要插回去的。如果有一本高度为h的书被抽走,剩下的书里头都没有高度为h的,那么混乱度需要增加。

 

代码:

hdu3237
posted @ 2010-08-26 20:44 Dango 阅读(462) | 评论 (0)编辑 收藏

Hdu 3231 Box Relations

题目描述:

    原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=3231

    给定一些正方体的关系,要求一组符合这些关系的正方体坐标,如果不存在符合条件的正方体坐标,IMPOSSIBLE。(Special Judge)

 

题目分析:

    首先把正方体这个立体问题拆分成X,Y,Z三个维度上的的平面问题。三个维度上的平面问题处理完了,正方体问题也就处理完了。

    首先想到了差分约束系统,但是我的SPFA呃,TLE了……(求一个不TLE的差分约束系统标程……)

    上网搜索了一个大牛的文,说只需要拓补排序就可以了,完全不需要差分约束。

    再想一想,此题如果用差分约束系统来做,所有边权都是-1。其实不如更直观地进行构图,例如a<b,那么就构图map[a][b] = 1,也就是不妨看做a到b的边权为1。其实进行一下拓补排序,根据点的拓补排序的结果就可以直接作为答案输出,如果拓补排序失败也就是IMPOSSIBLE。

 

代码:

hdu3231
posted @ 2010-08-26 20:44 Dango 阅读(572) | 评论 (0)编辑 收藏

     摘要: Hdu3229 Jinyuetuan Puzzle 题目大意:     原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=3229     劲乐团游戏,得分种类: 1、  single note,按一下键得一个cool 2、  strip note,开始时按一下键得...  阅读全文
posted @ 2010-08-26 20:42 Dango 阅读(356) | 评论 (0)编辑 收藏

     摘要: Hdu3225 Flowers Placement 题目大意:     原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=3225     给定每个位置上不可以出现的数字,求N满足以上要求的第K(1<=K<=80)大的N(1<=N<=200)的全排列。 题目分析:...  阅读全文
posted @ 2010-08-26 20:41 Dango 阅读(471) | 评论 (4)编辑 收藏