-
Archives
- January 2012
- December 2011
- August 2011
- July 2011
- June 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009
- December 2008
- November 2008
- October 2008
- September 2008
- August 2008
- July 2008
- June 2008
-
Meta
Monthly Archives: May 2010
POJ 3481 —— Double Queue
这个题目可以有多种做法：基本的堆，建立 2 个堆，一个大顶堆加一个小顶堆，同时更新；还有就是 treap，它是 tree + heap，在本题中将优先级作为 tree 的 key 有序排列。另外再添加一个字段（随机的）作为 treap 中的优先级满足堆的性质。 由于本质是搜索树，由此导致了不同搜索树的比拼：treap，红黑树，伸展树（splay），普通的二叉搜索树等等。 参考： http://www.amoa400.com/oiblog/read.php?30 http://hi.baidu.com/_silen_/blog/item/dd7f7658df9781d69c8204bc.html http://blog.sina.com.cn/s/blog_6114627a0100hpp6.html
一生得失总是零
这个世界上所有的事情，总是有一得必有一失。爱情能够给你欢乐，但它同时也给你痛苦；财富可以给你享受，但它也会带来苦恼；成功使你快乐，但是当失败之后痛苦将变得强烈而无法忍受。 如果你期待某件东西，而你得到了，那是一种快乐。然而相对地，当你失去的时候也会感受到等量的悲伤。得到时是八分快乐，失去也会有八分的痛苦，那个总数几乎是一样的。 有人得到了财富，却可能失去了健康、家庭或感情；而有人在事业和成就少了三分，则在生活质量、身体健康或时间自由方面多得到三分。有些东西看似不公，如果你细想下去，其实是公平的。
Posted in 投资
Leave a comment
HDU 2388 —— Playground Hideout
http://hi.baidu.com/wswroy/blog/item/23aedf58364d41262834f097.html 最短路。
POJ 1717 —— Dominoes
n 张骨牌，求最小的翻转次数，使得上下之差最小。 f[i] = j 表示在差值为 i 的情况下最小翻转次数为 j。
POJ 1745 —— Divisibility
题意：输入 n 个运算数和除数 k, 要求判断这 n 个数通过加减运算后能否整除 k。 样例输入： 4 7 //n , k 17 5 -21 15 //当17 + 5 + -21 - 15 = -14 时能整除k = 7 最多只有 [-k, k] 这么多种情况。
POJ 1742 —— Coins
给定 n 种硬币，每种硬币有相应的价值，并且每种硬币有一定的数量。问用这些硬币，可以组合出多少种不同的价值总和。 同样是母函数的应用。
POJ 1170 —— Shopping Offers
一个商店提供多种商品，当用户单独购买商品时有一个价格，当用户组合购买时可以获得优惠，现在提供多种优惠方案和需要购买的物品总数，问最大的优惠是多少。 输入 2 7 3 2 8 2 5 2 1 7 3 5 2 7 1 8 2 10 表示有 2 种商品，编号分别是 7 和 8，分别要购买的数量是 3 和 2，2 和 5 是它们的单件购买价格。 接下来是 2 种优惠。第 1 种优惠有 1 种商品：3 个 … Continue reading
POJ 1163 —— The Triangle
基本 DP 问题，滚动数组的又一利用，和那个矩阵下寻找最小路径的比较类似。
POJ 1159 —— Palindrome
题意：输入一串由‘A’到‘Z'和‘0’到‘9’组成的字符串S，要求添加最小的字母，使得S变成回文串。 这个题目有多种做法，应该值得收藏。 思路： <1> （1）求 S 的逆串与原串 S 的最长公共子序列sub； （2）ans = len(S) - len(sub)。 <2> 动态规划，转移方程： dp[i][j] = min(dp[i + 1][j - 1], dp[i][j]) (S[i] == S[j] 1
POJ 1080 —— Human Gene Functions
两个字符串，其包含的字符分别是 A, C, G, T。可以对它们添加空格来使得它们等长，空格不允许和空格匹配，还有一个矩阵来描述字符匹配对应关系下的得分，现在要使得得分最大。 跟前面谈到的字符串穿插问题类似。
POJ 1513 —— Scheduling Lectures
有 n 个主题要讲，每堂课时间为 L，每个主题必须得放在一堂课当中，只有在前面的主题讲完之后才能讲后面的主题，针对每堂课有个不满意因子，和这堂课剩余的时间有关，问至少需要几堂课，最小的不满意因子是多少。 至少需要几堂课可以通过贪心来获得，但是为了使得不满意因子最小，则不能通过贪心来获得。比如对 50 30 20 40 30 的序列，可以分为 50 30 和 20 40 30；也可以分为 50 30 20 和 40 30。而前一种方法的不满意因子较小。 设 m[i, j] 表示以前 i 堂课程覆盖 j 个主题的最小不满意因子。DI(x) 表示剩余时间为 x 时的不满意因子。 则 m[i, j] = m[i -1, … Continue reading
POJ 3409 —— Broken line
题意，给你 N 条线段，问你是不是形成欧拉回路。 做法就是最简单的并查集判断是否连通，记录所有节点的度。 麻烦的是坐标是250char的整数，并且有前导零。 所以去掉前导零后，字符串哈希一下就OK了。