2009年4月随笔档案 - Dreams

hdu 1134 Game of Connections 摘要: Catalan Number(卡特兰数)
S(n) = C(2n,n)/(n+1)
递推公式：a(n)=((4*n-2)/(n+1))*a(n-1)
我不理解~ 阅读全文

posted @ 2009-04-30 15:51 DreamSky 阅读(808) | 评论 (2) 编辑

hdu 1133 Buy the Ticket 摘要: 考虑（m+n）个人排队购票的情景，第（m+n）人站在第（m+n-1）个人的后面，则第（m+n ）个人的排队方式可以由下列两种情况获得：
a.第（m+n ）个人手持￥100的钞票，则在他之前的(m+（n-1））个人中有m个人手持￥50的钞票，有（n-1）个人手持￥100的钞票，此种情况共有f(m,n-1);
b.第（m+n ）个人手持￥50的钞票，则在他之前的(（m-1）+n）个人中有m-1个人手持￥50的钞票，有n个人手持￥100的钞票，此种情况共有f(m-1,n);
根据加法原理得到: f(m,n)=f(m-1,n)+f(m,n-1)
最终得到递推公式：f(m,n)= C(m+n,n)-C(m+n,m+1)
即：f(m,n) = ((m+1-n) / (m+1)) *((m+n)!) 阅读全文

posted @ 2009-04-30 15:36 DreamSky 阅读(883) | 评论 (0) 编辑

hutc 1042 Lecture Halls 摘要: nothing 阅读全文

posted @ 2009-04-29 08:10 DreamSky 阅读(259) | 评论 (0) 编辑

hutc 1041 最优装载摘要: nothing 阅读全文

posted @ 2009-04-29 08:09 DreamSky 阅读(477) | 评论 (0) 编辑

hutc 1040 Knapsack Problem 摘要: nothing 阅读全文

posted @ 2009-04-29 08:07 DreamSky 阅读(292) | 评论 (0) 编辑

vijos 1313 金明的预算方案摘要: 背包如此之妙（有依赖的背包）
题目大意：给你一系列物品清单，其中两物品直接可能存在主附关系，即要买附件必须将其附件也买下，比如若桌子跟椅子是主附关系，那么想买椅子则必须桌子也买下……问题来了，给你钱N，物品若干，快快买吧……如何买？
dp[j]表示钱为j的时候买得东西的最大价值
一、当物品为主件时：
1、没有附件
MAX（不买，买主件）
2、有一个附件
MAX（不买，只买主件，买主件与一附件）
3、有两个附件
MAX（不买，只买主件，买主件与一附件，买主件与两附件）
二、当物品为附件时：直接跳过
阅读全文

posted @ 2009-04-27 17:41 DreamSky 阅读(498) | 评论 (0) 编辑

vijos 1133 装箱问题摘要: 温习背包
阅读全文

posted @ 2009-04-27 14:23 DreamSky 阅读(299) | 评论 (0) 编辑

vijos 1317 开心的金明摘要: 比较明显的DP
稍稍多了一个条件，细细品味阅读全文

posted @ 2009-04-27 13:56 DreamSky 阅读(244) | 评论 (0) 编辑

hdu 2670 Girl Love Value 摘要: 女孩的爱不易得~
先对损耗值从大到小排序，使损失最小化，然后再常规化DP
dp[i][j] = MAX(dp[i-1][j] , dp[i-1][j-1] + X)//dp[i][j] 表示前i个人中选j个的最优值阅读全文

posted @ 2009-04-26 20:09 DreamSky 阅读(356) | 评论 (1) 编辑

hdu 1074 Doing Homework 摘要: 还需要慢慢揣摩~
貌似用的记忆法搜索~ 阅读全文

posted @ 2009-04-26 19:30 DreamSky 阅读(1337) | 评论 (1) 编辑

hdu 2059 龟兔赛跑摘要: 无言阅读全文

posted @ 2009-04-26 18:51 DreamSky 阅读(641) | 评论 (0) 编辑

hdu 1114 Piggy-Bank 摘要: 完全背包
时间从546MS优化到93MS，感觉不容易，呵呵~
还需要慢慢消化~ 阅读全文

posted @ 2009-04-25 20:22 DreamSky 阅读(827) | 评论 (1) 编辑

hdu 2152 Fruit 摘要: 最后一道母函数
G（X,Y,Z…）=（X^i…X^j）*（Y^i…Y^j）*（Z^i…Z^j）*…… 阅读全文

posted @ 2009-04-25 10:59 DreamSky 阅读(547) | 评论 (2) 编辑

hdu 2069 Coin Change 摘要: 母函数，终于貌似理解一点了~继续努力吧
ans[i][j]表示i分钱用j个硬币组合的方案数
要求记录组合硬币的个数~值得一看
注意点：1. 要求 0 cent 输出 1
2. 如果硬币总数超过100,是不合法的,也就是不用计算超过100个硬币的找钱方法. 阅读全文

posted @ 2009-04-25 10:33 DreamSky 阅读(1339) | 评论 (5) 编辑

hdu 1709 The Balance 摘要: 题目大意：天平平衡问题，给你n个砝码，每个砝码质量Wi，判断有多少种质量不能称量，质量范围是所以砝码的质量和
当然啦，天平两边都是可以放砝码的阅读全文

posted @ 2009-04-25 09:18 DreamSky 阅读(372) | 评论 (0) 编辑

va家族的等级制摘要: 先求出一段串是否为回文~
再是单调子序列思想~ 阅读全文

posted @ 2009-04-24 21:52 DreamSky 阅读(215) | 评论 (0) 编辑

hdu 1171 Big Event in HDU 摘要: 母函数解决
DP算法还是想不出来
郁闷中…… 阅读全文

posted @ 2009-04-24 18:11 DreamSky 阅读(1773) | 评论 (9) 编辑

hdu 1085 Holding Bin-Laden Captive! 摘要: 继续母函数
G（X）=（1+X+X^2+X^3+……）*（1+X^2+X^4+……）*（1+X^5+X^10+……）
时间不太好~ 阅读全文

posted @ 2009-04-24 16:42 DreamSky 阅读(670) | 评论 (3) 编辑

hdu 1028 Ignatius and the Princess III 摘要: 再来一次母函数~
G（X）=（1+X+X^2+X^3+……）*（1+X^2+X^4+……）阅读全文

posted @ 2009-04-24 14:55 DreamSky 阅读(584) | 评论 (1) 编辑

hdu 1398 Square Coins 摘要: 还不是很理解~
母函数G（X）=（1+X+X^2+X^3+……+X^289） *（1+X^4+X^8+X^12+……+X^288）*（1+X^9+X^18+X^27+……+X^288）*……*（1+X^289）;
阅读全文

posted @ 2009-04-24 14:23 DreamSky 阅读(515) | 评论 (1) 编辑

hdu 1728 逃离迷宫摘要: 一次性走完一行（一列）
该题用DFS超时了，不会剪枝~5555555 阅读全文

posted @ 2009-04-23 19:25 DreamSky 阅读(1415) | 评论 (0) 编辑

zju 3182 Nine Interlinks 摘要: 找规律阅读全文

posted @ 2009-04-23 08:05 DreamSky 阅读(245) | 评论 (0) 编辑

Lecture Halls （会议安排）摘要: 贪心+优先队列阅读全文

posted @ 2009-04-22 13:31 DreamSky 阅读(377) | 评论 (0) 编辑

hdu 2512 一卡通大冒险摘要: 内存消耗比较大~
什么类型的DP没想清楚，dp[i][j]表示i张卡片分成j堆时的情况数，
dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1]（dp[i-1][j] * j 表示i-1张卡片分为j堆的时候，第i张卡片可以分到任意一堆中，当然也就出现了一种新的分堆方法，dp[i-1][j-1]表示第i张卡片要独立成为一堆时的方案数）阅读全文

posted @ 2009-04-20 16:38 DreamSky 阅读(303) | 评论 (0) 编辑

hdu 2182 Frog 摘要: 青蛙吃害虫~
跟龟兔赛跑比较类似，第i个位置的值跟其前面位置的值有关阅读全文

posted @ 2009-04-17 22:10 DreamSky 阅读(361) | 评论 (0) 编辑

hdu 2275 Kiki & Little Kiki 1 摘要: set容器的应用
身旁有牛人就是好~ 阅读全文

posted @ 2009-04-17 18:33 DreamSky 阅读(290) | 评论 (0) 编辑

NK 1137 （hutc 1036）Pebble Merging（石子合并问题）摘要: 石子合并~
使用了最笨的方法，利用矩阵连乘思想阅读全文

posted @ 2009-04-17 13:05 DreamSky 阅读(448) | 评论 (0) 编辑

zju 2849 Attack of Panda Virus 摘要: 熊猫烧香优先队列+BFS 阅读全文

posted @ 2009-04-17 09:15 DreamSky 阅读(744) | 评论 (0) 编辑

hdu 1016 Prime Ring Problem 摘要: 简单深搜~ 阅读全文

posted @ 2009-04-16 16:51 DreamSky 阅读(629) | 评论 (0) 编辑

hutc 1035 编辑距离问题摘要: 题目大意：串变换，有串s最少经过多少步能够变换成t串
先用DFS过了，（但在南开JudgeOnline超时 555555555……）
再一次DP，总算都过了阅读全文

posted @ 2009-04-16 14:37 DreamSky 阅读(580) | 评论 (0) 编辑

zju 1234 Chopsticks 摘要: 题目大意：从n根筷子当中选取j对，其中一对筷子包含三根，并且要求第三跟不短语前两根。要求取出的筷子长度差（前两根的长度差）的平方的和最小。
num[i] 表示第i+1个筷子与第i个筷子长度差的平方~

开始从前面往后推，漏洞百出:dp[i][j]表示从1……i个筷子中选取j对，
dp[i][j] = MIN(dp[i-1][j],dp[i-3][j-1] + num[i-2]);
问题在哪？第i个筷子能用，
一种情况：第i-1个筷子能与第i-2个筷子配对了（来了第三根筷子i）；
二种情况：影响1……i-1个筷子中取j对筷子的配对情况。WHY？think about~

最后从后往前推:dp[i][j]表示从i……n个筷子中选取j对，
dp[i][j] = MIN(dp[i+1][j],dp[i+2][j-1] + num[i]);
没问题了吧~ 第i个筷子取，则必与第i+1个筷子配对，不取则可以忽略它（就因为它是当前最短的）阅读全文

posted @ 2009-04-16 10:04 DreamSky 阅读(348) | 评论 (0) 编辑

hdu 1026 Ignatius and the Princess I 摘要: BFS+保存路径
可以试想一下从终点走点始点，这样路径是否好处理一点~ 阅读全文

posted @ 2009-04-16 07:58 DreamSky 阅读(934) | 评论 (0) 编辑

hdu 1421 搬寝室摘要: 搬寝室——从n个物品中选取k对，使得每对物品质量差的平方之和最小
赋初值的时候要小心~
dp[i][j]表示从前i个物品中选取j对物品的最优值，
dp[i][j]=MIN(dp[i-1][j],dp[i-2][j-1]+(w[i] - w[i-1])*(w[i] - w[i-1]))，
取第i个物品，则必取第i-1个物品，WHY？相连物品平方差必定最小~
在WXH帮助下完成，学习学习~ 阅读全文

posted @ 2009-04-15 19:01 DreamSky 阅读(601) | 评论 (0) 编辑

并查集的初级应用及进阶摘要: 并查集资料
拷贝牛人http://blog.csdn.net/pure_life/archive/2008/09/13/2922118.aspx 阅读全文

posted @ 2009-04-15 13:46 DreamSky 阅读(453) | 评论 (0) 编辑

hdu 1159 Common Subsequence 摘要: 重温最长公共子串（LCS）
~ 阅读全文

posted @ 2009-04-15 13:16 DreamSky 阅读(455) | 评论 (0) 编辑

hdu 1558 Segment set 摘要: 题目大意：求交叉在一起的线段的条数，如果线段A连接着另外两条不相交线段B、C，则认为B、C也是相交的
简而言之就是输出要查找的线段所在集合中线段数为多少~
主要参考了牛人的代码，寻求了很久才找到一个能正确判断两线段是否相交的函数，珍惜珍惜~
并查集中的路径压缩，就这么回事~ 阅读全文

posted @ 2009-04-14 20:22 DreamSky 阅读(501) | 评论 (0) 编辑

hdu 1272 小希的迷宫摘要: 小希的迷宫~
题意：要求无回路，同属于一个集合
注意输入数据 0 0 的情况，应该输出 Yes~
并查集判连通，未输入的结点不用考虑，用visited数组标志结点是否出现过
矮树并入高树有益于查找阅读全文

posted @ 2009-04-12 17:08 DreamSky 阅读(1027) | 评论 (1) 编辑

hdu 1232 畅通工程摘要: 并查集好不简单，哎~笨牛~
不过在学弟的耐心指导下还是解决了，也算是跨进了并查集的门槛吧……
核心问题：求出有多少个集合~ 阅读全文

posted @ 2009-04-12 11:34 DreamSky 阅读(563) | 评论 (3) 编辑

hdu 2141 Can you find it? 摘要: 该题很容易超时，提交20余次~ 很郁闷~
先列举序列a与序列b的和，然后再进行二分查找
for(i=0 ; i< lena; i++)
for(j=0 ; j< lenb; j++)
temp[k++] = a[i] + b[j]; 阅读全文

posted @ 2009-04-11 19:56 DreamSky 阅读(423) | 评论 (0) 编辑

hdu 1239 Calling Extraterrestrial Intelligence Again 摘要: 典型的搜索
题目大意：给出三个整数m a b 其中 4 < m <= 100000 ， 1 <= a <= b <= 1000，寻找一对素数p q 使得
p*q<=m && a/b <= p/q <=1 ,要求使p*q尽可能大
按常规思想，数据量大肯定超时~
如果q为某个大于10000的素数，那么当p<10时，p/q < 0.001(然而a/b>=0.01),当p>10时,p*q>100000(然而m<=100000)
因此 p q 都是在10000以内的素数~
剪枝：if ( a[j]>m || a[j]*a[i]>m || ( (double)a[i]/a[j])more~ 阅读全文
posted @ 2009-04-11 19:44 DreamSky 阅读(430) | 评论 (0) 编辑

hdu 1010 Tempter of the Bone      摘要: 走迷宫-主要考查奇偶剪枝法
题目大意：给出起始位置，然后给定时间T，在时间T内从出发点走到终点，每步只能往上、下、左、右四个方向走一步，时间是1，不能在原地停留。如果到达某点的剩余时间为奇数，那么必定是在奇数步内走到终点，也就是两点的行差绝对值 + 列差绝对值也要是奇数~ 奇偶剪枝  阅读全文
posted @ 2009-04-11 19:26 DreamSky 阅读(837) | 评论 (1) 编辑

hdu 1072 Nightmare      摘要: 做噩梦了~
逃了好久好久~
在炸弹爆炸之前逃出迷宫，定时炸弹时间可以重置~
mark[i][j]表示第i行j列位置时剩余爆炸时间，当然是时间越长越好  阅读全文
posted @ 2009-04-11 19:15 DreamSky 阅读(696) | 评论 (0) 编辑

zju 1558 Euro Efficiency      摘要: 在六种欧元面值中找零……
  阅读全文
posted @ 2009-04-10 20:45 DreamSky 阅读(244) | 评论 (0) 编辑

hdu 1298 T9      摘要: 字典树+dfs+剪枝
先理解题意，给你一连串数字，输出其对应的出现频率最大的单词
在每一步深搜之前先做剪枝~  阅读全文
posted @ 2009-04-10 16:03 DreamSky 阅读(750) | 评论 (2) 编辑

hdu 1075 What Are You Talking About      摘要: Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 102400/204800 K (Java/Others)
Total Submission(s): 1238 Accepted Submission(s): 340
先用map勉强过了（1593MS 37528K）~
然后再建字典树（296MS 59804K）~  阅读全文
posted @ 2009-04-09 17:43 DreamSky 阅读(966) | 评论 (8) 编辑

hdu 1251 统计难题      摘要: 还是构建字典树~  阅读全文
posted @ 2009-04-09 14:17 DreamSky 阅读(361) | 评论 (0) 编辑

hdu 1800 Flying to the Mars      摘要: 利用字典树统计数字出现次数，输出出现次数最多的一次。
注意因为是大数，故需考虑除去前缀0，因0010 、010是同一个数字

字典树：又称为Trie，是一种用于快速检索的多叉树结构。Trie把要查找的关键词看作一个字符序列，并根据构成关键词字符的先后顺序构造用于检索的树结构；一棵m度的Trie树或者为空，或者由m棵m度的Trie树构成。
特别地：和二叉查找树不同，在Trie树中，每个结点上并非存储一个元素。   阅读全文
posted @ 2009-04-09 14:15 DreamSky 阅读(433) | 评论 (0) 编辑

Tian Ji -- The Horse Racing      摘要: 田忌赛马  阅读全文
posted @ 2009-04-08 19:28 DreamSky 阅读(293) | 评论 (0) 编辑

hdu 1195 Open the Lock      摘要: 对每个数字只要三种转换状态：加1，减1，跟其后面一个数字交换位置。
需注意的是最后一个数字没有交换，数字9加1变为1，数字1减1变为9。
很传统的一个BFS……
利用hash表标志走过的状态……  阅读全文
posted @ 2009-04-08 10:04 DreamSky 阅读(329) | 评论 (0) 编辑

hdu 1050 Moving Tables      摘要: 最少拦劫子系统类似  阅读全文
posted @ 2009-04-07 16:28 DreamSky 阅读(521) | 评论 (0) 编辑

hdu 1013 Digital Roots      摘要: 开始用int,WA,接着用__int64,还是WA,最后改用字符数组,新的错误：Compilation Error, WHY?
C语言要求变量的定义应该放在所有的执行语句之前，而C++则放松了限制，只要求在第一次使用该变量之前进行定义即可……
切记切记……
看下面代码————焕然大悟！！！  阅读全文
posted @ 2009-04-04 10:49 DreamSky 阅读(734) | 评论 (0) 编辑

hdu 1142 A Walk Through the Forest      摘要: 记忆法搜索
因为1是出发点，2是终点，先运用dijkstra（迪杰斯特拉）算法计算出所有点到终点的最短路径。
然后记忆法搜索，从1开始，与1相连且到终点2的距离比dist[1]小的点都可行，依此类推……  阅读全文
posted @ 2009-04-03 20:27 DreamSky 阅读(985) | 评论 (1) 编辑

hdu 2066 一个人的旅行      摘要: 多旅行多快乐  阅读全文
posted @ 2009-04-03 19:23 DreamSky 阅读(780) | 评论 (1) 编辑

zju 1076 Gene Assembly      摘要: 简单贪心
类似活动安排问题  阅读全文
posted @ 2009-04-03 19:14 DreamSky 阅读(234) | 评论 (0) 编辑

hdu 1078 FatMouse and Cheese      摘要: 米老鼠觅食
从坐标0、0出发，依次找其周围最优的方案然后递归下去，同时记录搜索过的地方  阅读全文
posted @ 2009-04-03 08:46 DreamSky 阅读(255) | 评论 (0) 编辑

poj 1088 滑雪      摘要: 滑雪不好玩  阅读全文
posted @ 2009-04-02 20:20 DreamSky 阅读(154) | 评论 (0) 编辑

zju 2022 Factorial      摘要: 计算N！后面零的个数  阅读全文
posted @ 2009-04-02 12:28 DreamSky 阅读(257) | 评论 (0) 编辑

zju 1199 Point of Intersection      摘要: 公式推导过程
temp=(y1-y2)/(x1-x2);
sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0))/sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0))=r1/r2;
(y1-y0)/(x1-x0)=temp;
(y2-y0)/(x2-x0)=temp;
  阅读全文
posted @ 2009-04-02 09:37 DreamSky 阅读(163) | 评论 (0) 编辑

zju 1047 Image Perimeters      摘要: 求X块图的面积
从出发点向四周扩散，如果X的一边为.或者是边界，则sum++  阅读全文
posted @ 2009-04-01 21:31 DreamSky 阅读(244) | 评论 (0) 编辑

zju 3049 Diablo II Items      摘要: 题目的背景是鼎鼎大名的暗黑2，这题讲的是关于暗黑卖物品的一个问题。暗黑里面有两种物品，普通物品和魔法
物品。普通物品只有一个普通出售价格，而魔法物品有两个出售价格，鉴定前的价格和鉴定后的价格，用鉴定卷轴
鉴定魔法物品，物品的价格就变成鉴定后价格了。然后现在没有钱，有一堆物品要卖，其中有若干的普通物品和若
干的魔法物品，其中魔法物品都是没有鉴定过的。同时，可以买无限量的鉴定卷轴（价格cost）。现在的问题是怎么
卖东西才能让最后的总收益最大。这题主要考察的是分析题目的能力。首先发现，所有的普通物品可以直接卖掉，
因为他们只有一个价格。然后考察魔法物品（鉴定前价格normalPrice，鉴定后价格magicPrice），如果
normalPrice >= magicPrice - cost，那么也可以把它们当作普通物品一样直接卖了，因为鉴定它们完全不会有任
何的收获。然后，剩下的物品，鉴定后卖总是比不鉴定直接卖要赚钱的。我们可以发现，一旦我们有钱可以买得起
一个鉴定卷轴，买一个来鉴定一个魔法物品然后卖掉后，钱会增加，于是可以继  阅读全文
posted @ 2009-04-01 12:22 DreamSky 阅读(247) | 评论 (1) 编辑

04 2009 档案

公告

导航

统计

常用链接

留言簿(6)

随笔分类

随笔档案

文章分类

文章档案

相册

百事百通

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜