帖子

目前显示的是 九月, 2013的博文

腾迅入股搜狗,是张朝阳想套现?

9.16日,腾迅以4.48亿美元现金加上旗下的搜索资产,换取了搜狗的36.5%的股份和20.6%的投票权。搜狗为什么要出售?首先,此次交易对应的股份都是增发的新股,而且是B类优先股(一部分有投票权)。SEC公告上说,这部分资金中的3亿美元在交易结束后会发放给sogou现有的A类优先股的持有者。"Sogou will use a portion of the cash proceeds of Tencent’s investment to pay a special dividend in the amount of approximately $301 million to the holders of Series A Preferred Shares of Sogou, payable promptly following the closing of the transaction."记者会上说"这一次增发新股,后面会给原来老股东派股息,然后回馈小股东。最重要的是拿到腾讯的资源。"我十分不明白为什么要在此时发放特殊股利给A类优先股的持有者。那么这些持有者又是谁呢?根据历史公告,在2010年10月22日,搜狗出售了24.0 million, 14.4 million and 38.4 million份A类优先股分别给阿里、Yunfeng基金以及张朝阳自己的Photon基金,当时的价格分别是1500万美元、900万美元、2400万美元。对应的份额约为10%, 6% and 16%。此时搜狗依然保留搜狗53%的股份。根据2011年6月的公告:As of June 30, 2011, Sogou had outstanding a combined total of 216,000,000 ordinary shares and Series A preferred shares, consisting of (i) 139,200,000 ordinary shares held by Sohu; (ii) 24,000,000 Series A preferred shares held by Alibaba; (iii) 14,400,000 Series A preferred shares held by China…

UVA 最大递增子序列(LIS)相关题目总结

基本的: (直接用LIS算法就可以解决的)231 Testing the CATCHER497 Strategic Defense Initiative481 What Goes Up 关于LIS算法的基本实现,可参考我之前写的: http://www.sunchangming.com/blog/post/4583.html下面列些非基本的 10534 - Wavio Sequence这个问题求Wavio Sequence的最大长度。Wavio Sequence是指,先递增再递减,递增部分的长度和递减部分的长度一样,所以最终这个序列的长度必须是2N+1。比如 1 2 3 2 1 就是一个Wavio Sequence。假设给1 2 3 4 5 4 3 2 1 10 这样一个序列,怎么求出它长度最大的Wavio Sequence呢?假设原数组为A[0...n],可以证明,对于任意的A[i],以它为中心的最大长度的Wavio Sequence就是向左找最长上升序列,向右找最长下降序列,然后拼接起来。最后为了满足2N+1的条件,裁减一下。我的做法是,做两次LIS,一次从头往尾做,另一次从尾往头做。然后遍历求max。代码如下:std::vector<size_t> ret1=lis(nums.begin(),nums.end()); std::vector<size_t> ret2=lis(nums.rbegin(),nums.rend()); size_t maxlen(1); for(size_t i=0;i!=ret1.size();++i){ size_t l=ret1[i]; size_t r=ret2[ret1.size()-i-1]; if(l==1 || r==1) continue; maxlen=std::max(std::min(l,r)*2-1,maxlen); } std::cout<<maxlen<<"\n"; 其中lis算法可以用O(nlgn)的实现,具体我省略掉了,请参见我之前的日志。10131 - Is Bigger Smarter?参见 http://www.sunchangming.…

致身为儿女的80s们,我们的父母真的开始老了

我是一个北漂,85年出生,今年28岁,无房无车无户口。在此讲一些我身边的事情,提醒大家要开始注意父母的身体健康了。人都会老,而我们的父母现在就在这个坎上。先从我一个朋友的事情说起。她两年前工作调动来的北京。她母亲是教师,恰逢放假,就过来看看。她母亲身体一向很好,连感冒都很少得。每天她去上班,她母亲就下楼去晨练。等周末了,就一起去颐和园什么地方去逛逛。然后突然有一天,她母亲就倒下了,急匆匆的送进了301的ICU(不是急诊科)。她开始四处筹钱,不先准备个10万不行。还好,最终有惊无险,阿姨过了两周顺利出院,又乐滋滋的跟我们去逛公园了。只有医生清楚她是多么幸运。我姨,也就是我妈妈的亲姐,刚去世没几年,地里正收庄稼呢,突然就脑溢血倒下了,在送去医院的当天就过世了,那时她还不到60岁。我妈,多年来一直体重不过百,吃饭很少,血压偏低。然后突然有一天,就高血压、脑梗塞了。多次晕倒在地上,以至于我们很不敢放她独自在家,但是又没有办法。该上班的要上班,我弟弟该上学还要上学,谁能天天在家守着她呢?谁也没有料到,刚到50岁,就从低血压变成高血压了。她是突然晕倒在地然后被送去医院然后抢救过来,她才知道自己有高血压。并且已经有颈动脉斑块,腔隙性脑梗塞。之所以想写这篇长文是因为今天,又是一个中学同学,打电话咨询我,他父亲颈椎有问题,老觉得身体麻木,是该看骨科还是神经科?我说,当然该看骨科啊!问题是你咋知道颈椎有问题呢,拍片子了?他说拍了,说是颈动脉有点问题,好像是有点堵。我晕,我赶紧改口让他去看神经内科,并且很严肃的告诉他,那就是一个定时炸弹,不定什么时候爆发,重则瘫痪。但要是积极治疗一直保持注意,其实也没事。我们当务之急是,多关心父母的健康,向他们灌输正确的健康观念。每年体检对于50岁以上人太重要!我第一次带我爸去做体检,花了300多,除了腰围太粗之外什么都没查出来。所以他觉得体检不值得。他很愤恨,腰围太粗这需要你查吗?我照照镜子自己都知道。在他看来,花了钱,却什么都没查出来,这钱是白花了。他说他健康的很,不用查就知道。嗯……他不知道腰臀比过高意味着什么,难道要像我妈一样,直到突然有一天晕倒被送到急诊科了,才知道自己有高血压吗?话说我妈比我姨幸运多了。但是我妈也2多了,一边在病房挂着点滴,一边偷偷的跑出去买酱鸡爪啃着吃。她向我们抱怨医院的伙食太差,整天清汤寡水的,像坐牢一样。她说我们故意虐…

uva 10131 - Is Bigger Smarter?

题目http://uva.onlinejudge.org/external/101/10131.html输入是一些有序整数对(a1,b1)
(a2,b2)
(a3,b3)要求从中挑取一部分输出。 输出需要满足满足第一列严格递减,第二列严格递增,即 a(i) < a(i+1) && b(i+1) < b(i) 输出的序列可以不保持原先的相对顺序。求输出的序列的最大长度。分析这是一个与LIS相关的题目。我想套用之前的代码,在O(nlgn)的时间内解决这个问题。 关于LIS的讨论参见 http://www.sunchangming.com/blog/post/4583.html首先,我的想法是,把输入的序列按照第一列排序,然后扔到我之前写好的LIS函数中求解(求LIS时只考虑b的值,不管a)。可惜,失败了。因为第一列有可能重复。(1,3)
(1,2)的LIS的长度应该是1。如果LIS的时候不考虑第一列,会出错。于是我把LIS的时候的comp函数换成了booloperator<(const elephant& r) const{ returnthis->first < r.first && this->second > r.second; } 结果还是错了!这跟我采用的LIS算法有关。假设输入为A[0]={500,1}
A[1]={500,2000}
A[2]={600,1000}在处理第二行的时候, 因为A[1] < A[0] == false ,所以我不能拿它来替换M[0]。并且 A[0] < A[1] == false,我也不能把它放在原来的LIS的末尾构成一个更长的LIS。综上所述,我只能在处理中把它丢弃。结果是,在处理A[2]的时候遇到了同样的情况。所以,要使我的算法能正常工作,如果有A[1]<A[2] && !(A[0]<A[2]) 必须有 A[1] < A[0]于是我最终这样:排序的时候,两列都按照升序排计算LIS的时候,对于第一列,只判断是否相等。booloperator<(const elephant& r) const{ returnthis->first != r.first &&…

Longest Increasing Subsequence

题目uva 481: What Goes Up http://uva.onlinejudge.org/external/106/10684.html这个问题是这样:给定一个数组a[0...n],求它的单调严格递增子序列的最大长度,并给出一个示例解。子序列是从最初序列通过去除0个或多个元素但不破坏余下元素的相对位置而形成的新序列。严格单调递增是这个序列中每个元素都小于后一个元素,不能等于,也不能大于。例如:-7 10 9 2 3 8 8 1 的解是4,其中一个长度为4的LIS是:-7 2 3 8例如:0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 的解是6,其中一个长度为6的LIS是:0, 2, 6, 9, 11, 15这就是一个很普通的求 LIS(Longest Increasing Subsequence)的问题。我本来LIS以为和LCS很像,但是实际写一下发现,这个东西挺难的,花了我整整一下午的时间才写好。解法一首先,基本思路是用动态规划,自下而上的把解构造出来。要使用动态规划,就得有最优子结构。下面来分析一下。把原来的问题稍微加点限制。设LIS(i) : 以a[i]为右端点的单调严格递增子序列 (加了以a[i]为右端点这个限制)那么显然有LIS(0) = a[0];LIS(i) = max { LIS(j)  : a[j]<a[i] && 0<=j<i } .append( a[i] );所以在O(n^2) 的时间内,就能求出最大长度。另外,如果我们直接存储n个LIS,那么空间消耗是O(n^2)的。所以实际计算中可以采用下面这样的方法:先用一个数组m,其中m[i] =  LIS(i)的长度。所以m最终的长度和输入数组a的长度一样。另外一个数组indexesindexes[i]: 以a[i]为结尾的lis的a[i]的上一个的(index+1)。0,没了 。这个有点像链表。我用0来标志结束,所以不得不在存index的时候都先加1,再存入。最终通过遍历链表的方式遍历这个数组,就可以得到子序列。 代码如下: //return the indexes of the origin array template <typename T> std::vector<…

UVA 11264: Coin Collector

http://uva.onlinejudge.org/external/112/11264.html原问题是这样:小明去国外玩,想兑换些货币。他希望每种面值的货币都兑换点。但是兑换处的人可不理会他这个需求,兑换处的原则是,尽量挑选面值最大的给他。比如货币的面值是100、50、20、10、5、2、1,你要76块钱,那我先给你50,还差你26。于是再给你20,还差6块。那我再给5块,再给1块。嗯……一般人都是这样给钱的吧?但是小明就是喜欢收集钱币啊。假如货币的面值种类已知,问用这种方法最多能换到多少种?假设小明很富有,钱无限多。例如:1 2 4 8 16 32 6种1 3 6 8 15 20 4种1 3 6 8 11 3种答:假设输入的数组为A[1...n] ,它代表了N中不同面值。假设我们已经按照从小到大排序,其中A[1]最小,A[n]最大。如果小明拿m元换得了k种货币,那么m最小是多少? 答:把这几种货币的面值加起来。另外,A[n](即面值最大的)一定会被选中,反证:如果花了m元却没有选中它,可知m<A[n],于是用m+A[n]元去兑换可以得到一个更优解。假设S(i)是A[1]...A[i] 中那些被选中的货币的面值的和。那么一定有 S(i) < A[i+1]。假如我们已经知道最优解是k种货币,那么它对应的具体哪k种呢?这个答案是否唯一? 不。 拿1 3 4来说, 1 4 和 3 4 都是最优解。所以我们想办法构造一个这样的序列出来。按照规则:如果有S(i-1) + A[i] < A[i+1],那么A[i] 被选中。首先,这个序列很显然是一个合法的序列,所以它是解。其次,要证明它是最优的,即,不存在比它更长的合法序列。longresolve(std::vector<long>& nums){ if(nums.size()<=2) return nums.size(); std::sort(nums.begin(),nums.end()); nums.push_back(LONG_MAX); //now,nums.size()>=3longret(2); longsum(nums[0]+nums[1]); for(size_t i=2;i!=nums.size()-1;++i){�…

uva 624 - CD (0-1 knapsack)

http://uva.onlinejudge.org/external/6/624.html我把这个问题复述一下。输入有很多行,每行都是如下格式sum n a1 a2 a3 a4 这样的格式。如5 3 1 3 4sum = 5 背包的容量是多少n =3 有多少个物品1 3 4 每个物品的体积是多少。然后要你把物品塞进背包里,把这个背包尽可能的塞满。对于上面的输入,输出是这样:1 4 sum:5含义是:体积最多能塞到5。 因为1+4=5。
例如:
10 4 9 8 4 2
对应的输出是:
8 2 sum:10例如:
20 4 10 5 7 4对应的输出是:
10 5 4 sum:19
例如:
45 8 4 10 44 43 12 9 8 2
对应的输出是:
4 10 12 9 8 2 sum:45或者:
43 2 sum:45也就是说答案并不唯一,但是online judge系统都能接受。这个问题是经典的动态规划问题,但是我看大多数地方把它归为backtracking。他们是用backtracking and pruning 的方式来解决这个问题。However,即便是用动态规划解,程序也有很多不同的写法。有的人是用一个大的矩阵保存计算的中间结果,但是只保存total value,不保存每个物品具体的index。然后最终,backtracking一次这个矩阵,把最大值对应的所有的index计算出来。而我是在计算的每一步都把index记住,这样我就可以只用两个vector,或者甚至只用一个vector就保存所有的中间值。struct Result{ std::vector<size_t> indexes; long total; Result():total(0){} voidadd(long v,size_t index){ total+=v; indexes.push_back(index); } }; Result resolve(conststd::vector& values,long cap){ if(cap<=0) return Result(); std::vector* memo=newstd::vector; memo->resize(cap+1); for(size_t …

Catalan Number and parentheses

Question:print all valid (properly opened and closed combinations of n-pairs of parentheses, and how many they would be?for example, when n=2, there are 2 kinds:(()) , ()()when n=3, there are 5 kinds:((())), (()()),(())(),()(()),()()()Anwser:如果直接按照题意写,可得到如下代码:staticvoidprint_parentheses(std::string s,int ln,int rn){ if(!ln && !rn){ std::cout<<s<<std::endl; return ; } if(ln>0) print_parentheses(s+"(",ln-1,rn); if(rn>ln) print_parentheses(s+")",ln,rn-1); } int n=4; std::string s; print_parentheses(s,n,n); 但是,为了减少string的copy次数,可以改成传引用。staticvoidprint_parentheses(std::string& s,int ln,int rn){ if(!ln && !rn){ std::cout<<s<<std::endl; s.resize(s.size()-1); return ; } if(ln>0) print_parentheses(s.append(1,'('),ln-1,rn); if(rn>ln) print_parentheses(s.append(1,')'),ln,rn-1); if(!s.empty()) s.resize(s.size()-1); } 但是,到底会输出多少结果呢? 分析的过程比较麻烦。下面我的分析不好,请参见算法导论第三版的思考…

BST functions in libc

我今天刚发现,原来libc里面自带的就有二叉搜索树相关函数.void *tdelete(constvoid * restrict key, void ** restrict rootp, int (*compar) (constvoid *, constvoid *)); void *tfind(constvoid *key, void * const *rootp, int (*compar) (constvoid *, constvoid *)); void *tsearch(constvoid *key, void **rootp, int (*compar) (constvoid *, constvoid *)); voidtwalk(constvoid *root, void (*action)(constvoid *, VISIT, int)); 其中tsearch其实是insert函数,名字有点歧义。另外我看了下实现,发现FreeBSD下,这几个函数实现的是最最基本的BST,就是一点旋转、平衡都没有的。而在Linux下,它们是红黑树。freebsd下没有destroy函数。其实这个只需要按照中序遍历,对每个节点delete/free就行了。

BFS与水罐灌水问题

图片
三个水桶,最大容量为10L, 7L, 4L。初始状态为,10L,0L,0L。 即,第一个是满的,后两个是空的。可进行的操作:把某个水桶的水倒入另一个水桶中,直到这两个水桶的某一个满了或者空了。 比如 (10,0,0) -> (3,7,0)问:至少进行几次操作,使得某一个水桶的水为2。就是说,怎么倒来倒去,能量出2L水来。这是一个很古典的智力题。解:我们先画一个圆圈,写上(10,0,0),代表水桶的初始状态。然后把它能通过一步操作转移到哪些状态,也画出来,用线连起来。如此反复。最终我们会得到一个很大的无向图,每个节点都是一种状态,每条边代表一次倒水操作。我们要做的,是从(10,0,0)这个节点开始,进行广度优先搜索。/** * 三个水桶,最大容量为10,7,4 * 初始状态为,10,0,0 * 可进行的操作:把某个水桶的水倒入另一个水桶中,直到这两个水桶的某一个满了或者空了。 * 问:至少进行几次操作,使得某一个水桶的水为2 */#include <iostream>#include <queue>#include <algorithm>#include <unordered_map>#include <string.h>struct Node { int state[3]; Node(int x, int y, int z) { state[0] = x; state[1] = y; state[2] = z; } Node(const Node& n) { memcpy(state, n.state, sizeof(state)); } booloperator==(const Node& n) const { return !memcmp(state, n.state, sizeof(state)); } boolisFound(int n)const{ return state[0] == n || state[1] == n || state[2] == n; } }; struct NodeHash { size_t operator()(const Node* n)const{ si…

UVA 138 - Street Numbers

QuestionA computer programmer lives in a street with houses numbered consecutively (from 1) down one side of the street. Every evening she walks her dog by leaving her house and randomly turning left or right and walking to the end of the street and back. One night she adds up the street numbers of the houses she passes (excluding her own). The next time she walks the other way she repeats this and finds, to her astonishment, that the two sums are the same. Although this is determined in part by her house number and in part by the number of houses in the street, she nevertheless feels that this is a desirable property for her house to have and decides that all her subsequent houses should exhibit it.Write a program to find pairs of numbers that satisfy this condition. To start your list the first two pairs are: (house number, last number):6 8
35 49Anwser完整的输出是6 8
35 49
204 288
1189 1681
6930 9800
40391 57121
235416 332928
1372105 1940449
7997214 11309768
46611179 65918161这个问题用数学语言描述就是,找到正整数n,m,…