posts - 7, comments - 2, trackbacks - 0, articles - 1
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

2009年8月3日

     摘要: Here are my OS practices.
If certain mistakes are found, please mail to me "jiyuan0914@gmail.com"  阅读全文

posted @ 2009-08-03 01:26 Lemon 阅读(237) | 评论 (0)编辑 收藏

2009年8月2日

     摘要: Here are my OS practices.
If certain mistakes are found, please mail to me "jiyuan0914@gmail.com"  阅读全文

posted @ 2009-08-02 01:11 Lemon 阅读(416) | 评论 (0)编辑 收藏

2009年8月1日

     摘要: Here are my OS practices.
If certain mistakes are found, please mail to me "jiyuan0914@gmail.com"  阅读全文

posted @ 2009-08-01 11:45 Lemon 阅读(289) | 评论 (0)编辑 收藏

2009年4月15日

1.Tourist http://acm.pku.edu.cn/JudgeOnline/problem?id=2964 做过一道类似的http://acm.hdu.edu.cn/showproblem.php?pid=2686规模小,可以n^4(dp[x1][y1][x2][y2])解决,本题要一个n^3的状态方程.仔细观察n^4的方程,可以发现有很多冗余状态.dp[step][x1][x2], y1 = step - x1, y2 = step - x2.
2.Polygon http://acm.pku.edu.cn/JudgeOnline/problem?id=1179 有一个细节要特别注意,两个很小的负数相乘变成一个很大的正数。枚举第一条要消去的边,再dp[form][to][2],最后一维0记录最小值,1记录最大值,记忆化搜索一下。
3.Milking Time http://acm.pku.edu.cn/JudgeOnline/problem?id=3616 一维dp,按开始时间排序,特殊处理第一段(不用休息),注意时间段,比如r = 2时, [1, 2]和[4, 5]不冲突。
4.Euro Efficiency http://acm.pku.edu.cn/JudgeOnline/problem?id=1252 无穷背包,或最短路搜索。有个细节要注意:一个数可以由超过100的数减另一个数得到。
5.Washing Clothes http://acm.pku.edu.cn/JudgeOnline/problem?id=3211 简单的01背包,每件衣服的时间小于1000,总时间不超过100000,背包分配男生的任务,剩下就是女生的了。

posted @ 2009-04-15 00:57 Lemon 阅读(276) | 评论 (0)编辑 收藏

2009年4月1日

形如 X2 - D * Y2 = A 称为pell方程。其实不是pell发现的。
只要D不是平方数,方程就有解,解有无穷多个。

因式分解方程 : (X + sqrt(D) * Y) * (X - sqrt(D) * Y) = A

先找到一个最小的解(a, b)

再构造其余的解

(X + sqrt(D) * Y)^2 * (X - sqrt(D) * Y)^2 = A

(X + sqrt(D) * Y)^3 * (X - sqrt(D) * Y)^3 = A 

(X + sqrt(D) * Y)^4 * (X - sqrt(D) * Y)^4 = A 

……

posted @ 2009-04-01 11:31 Lemon 阅读(661) | 评论 (1)编辑 收藏

2009年3月13日

     摘要: http://acm.hdu.edu.cn/showproblem.php?pid=1813IDA* g(x,y) = depth, h(x, y) = 从x,y到出口的最小距离,先BFS求每一格到出口的最短距离,剪枝的效果蛮不错的大家如果能把我的数据跑进200MS应该没问题了 #include <stdio.h>#include <stdlib.h>...  阅读全文

posted @ 2009-03-13 17:55 Lemon 阅读(293) | 评论 (1)编辑 收藏

2009年3月7日

       一道搜索好题,着实让我费了不少工夫。

       先想到了用位表示每个字母是否已经被用过,一共2^n个不同的状态,根据题目意思就画出了一棵搜索树,根部和叶子结点少,中间很胖,就是C(n,1) + C(n, 2) + … + C(n,n) = 2 ^ n。

       写了一个DP,字符串的比较用两重循环,记忆化,Run了两个测试数据

A

AAAAAAAAAAAAAAAAAA


GTGTACCTGCAGTTGCAG

GGTGGCAAGCTATACAAG


Ans : 6 8

Time: 2000+MS 2000+MS

       又写了一个迭代加深的搜索,Run一下,Time: 1400MS 27000MS,第二测试数据的时间简直无法接受,答案的深度加一,时间就飙了一个数量级。

       又写了BFS广搜,Time: 16MS 500+MS 还是比较满意的,不过还是超时了。我想大概是字符串处理的太慢的,把那段改成用KMP来做,测了下时间更慢了,郁闷~

       最后想到了A*,测了下15MS 170MS,已经挺满意了,不过还是超时,失望啊~我怀疑STL太慢了,于是自己写了一个堆,结果卡过了,PKU 900MS,呵呵~

       这题让我用尽了浑身解数,把这么多算法都回顾了一遍。我知道,有些地方写得不是很好结果超时了,黄队的博客上写用BFS过的,看来我的搜索能力还有待提高啊~

posted @ 2009-03-07 20:05 Lemon 阅读(348) | 评论 (0)编辑 收藏