C++博客-Lemon的空间

Producers and Consumers

Lemon — Sun, 02 Aug 2009 17:26:00 GMT

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

Lemon 2009-08-03 01:26 发表评论

Producer and Consumer

Lemon — Sat, 01 Aug 2009 17:11:00 GMT

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

Lemon 2009-08-02 01:11 发表评论

The Dinning Philosophers Problem

Lemon — Sat, 01 Aug 2009 03:45:00 GMT

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

Lemon 2009-08-01 11:45 发表评论

动态规划专练(不断练习更新中)

Lemon — Tue, 14 Apr 2009 16:57:00 GMT

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，背包分配男生的任务，剩下就是女生的了。

Lemon 2009-04-15 00:57 发表评论

pell方程解法--学习笔记

Lemon — Wed, 01 Apr 2009 03:31:00 GMT

形如 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

……

Lemon 2009-04-01 11:31 发表评论

HDOJ 1813 Escape from Tetris

Lemon — Fri, 13 Mar 2009 09:55:00 GMT

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

Lemon 2009-03-13 17:55 发表评论

Copying DNA PKU3633

Lemon — Sat, 07 Mar 2009 12:05:00 GMT

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

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

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

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过的，看来我的搜索能力还有待提高啊~

Lemon 2009-03-07 20:05 发表评论