在这不存在的一天,我不知道该写什么。
无题
2010年06月4日 352 views柏拉图说过啥
2010年06月1日 888 views每当看到那种被到处转载到滥俗的文章,我都有一种认真魔人(需翻墙)的冲动。今天我比较无聊了,来考据一下这篇:
柏拉图有一天问老师苏格拉底是什么是爱情,苏格拉底叫他到麦田走一次,要不回头地走,在途中要摘一株最大最好的麦穗,但只可以摘一次。
柏拉图觉得很容易,充满信心地出去,谁知过了半天他仍没有回去。
最后,他垂头丧气地出现在老师跟前诉说空手而回的原因:“很难得看见一株不错的,却不知道是不是最好的,因为只可以摘一株,只好放弃,再往前走看看有没有更好的。到发现已经走到尽头时,才发觉手上一株麦穗也没有—”
这时,苏格拉底告诉他:“这就是爱情!”
又有一天,苏格拉底让柏拉图到树林里,砍下一棵全树林最大最茂盛、最适合放在家里作圣诞树的树。其间只能砍一次,并且只可以向前走,不能回头。
柏拉图于是照着老师的话做。这次,他带了一棵普普通通,不是很茂盛,亦不算太差的树回来。老师问他,怎么带这棵普普通通的树回来,他说:“有了上一次经验,当我走到大半路程还两手空空时,看到这棵树也不太差,便砍下来,免得错过了后,最后又什么也带不回来。”
苏格拉底告诉柏拉图说:“这是婚姻!”
首先第二部分有一个显而易见的bug,很多人也都发现了,那就是苏格拉底和柏拉图是不可能知道“圣诞树”这种东西的。他俩生活的年代是公元前400年左右的古希腊,而耶稣诞生于公元元年,这其中至少差了大约四百年。实际上,人们开始过圣诞节是在耶稣诞生几百年之后了,形成砍圣诞树的习俗则更晚。所以柏拉图是无论如何不会纪念一个四百年之后出生的人的。(顺便提一句,其实耶稣不是出生在12月25号的,真正出生在12月25号的最nb的人是艾萨克.牛逼顿,我记得在TBBT里Sheldon也说过这事。)
如果你还是对四百年的偏差没什么概念,觉得两千年前和两千四百年前没啥区别的话,我们可以把这四百年放到现在试试。从现在往前数四百年,也就是公元1600年左右,我查了一下,在中国是明朝的万历年间。所以我们可以猜想,万历皇帝之所以三十年不上朝,其实是因为他沉迷于一个叫做《尾行3》的网络游戏。这下你该明白四百年意味着什么了。
发现不小心又愤了一下CCAV……淡定淡定,我们接着来考据。其实嘛,写这种心灵鸡汤类的小故事,直接用自己的口气写就可以了嘛。我想作者(很可能是个充满幻想的小萝莉)非要把柏拉图扯进来的原因,是因为那个已经滥俗了的词——“柏拉图式的爱情”。(我记得还见过一篇更夸张的,里面全是柏拉图说,爱情怎么怎么样;柏拉图说,恋爱是啥啥啥。)不得不说,很多哲学词汇已经被大众广泛地误解到偏离原意很远了,比如“犬儒主义”(Cynicism),现在大家提到这个词时所联想到的东西,和它的古希腊创始人的本意几乎完全不同甚至相反。我觉得这个“柏拉图式的爱情”(Platonic Love)也是这样。
现在提到柏拉图式的爱情,大家都会觉得是指不涉及xxoo的精神上的恋爱,让充满幻想的小萝莉们很向往的纯纯的没有杂念的男女之情。实际上呢,精神恋爱或许是对的,不涉及xxoo或许也是对的,最主要的不对之处是性别——柏拉图所赞扬的爱情,其实极有可能指的是男男之爱。
柏拉图,虽然确实相貌堂堂一表人才,但他可不像小萝莉们猜想的那样是个情种,因为痴心地苦恋某MM而不得,才YY出了一套精神恋爱的理论。实际上,在古希腊,如同古代的大多数其他地方一样,女性是几乎被无视的。(各位MM先别怒,我不是在表明观点,只是在陈述事实。)所以很难设想柏拉图作为一个衣食无忧、声名显赫的富家公子,会纠结于男女感情之事并为此著书立说。柏拉图对爱情的比较系统的论述并不多,主要见于他的《会饮篇》(Symposium)。在里面描述了一个私人宴会的情景,当时在场的苏格拉底说出了一种很神奇的观点——如同柏拉图的很多其他著作一样,我们不知道到底是苏格拉底真这么说的,还是柏拉图借苏格拉底之口表述自己的观点——说上古时期世界上有三种人,男人、女人和阴阳人,其中男人是最美好的。后来每种人都被劈成了两半,原来的男人被劈成了两个男人,女人劈成两个女人,阴阳人劈成一男一女。在现在的时代里,人们彼此的爱慕就是因为要寻找以前的另一半。如果现在的一个男人是从以前的一个男人劈出来的,他就会寻找另一半男人,女人的情况也类似,如果一个男人是从阴阳人劈出来的,他就会寻找另一半的女人(看来上古时期阴阳人居多啊-_-)因为他认为原来的男人是最美好的,从而现在的男男之爱也就是最美好的。接下来他的论述似乎表明在古希腊那个时代一个年长的怪蜀黍追求一个英俊的小正太是很正常并且被赞美的事情。(有人考据说柏拉图正是这样爱着他的老师苏格拉底的)
我们到这里总结一下,也就是说,柏拉图原意所指的爱并不是男女之爱,而主要是指与性别无关的师生之爱或朋友之爱,在他那个时代,这种爱一般就成了男男之爱。
柏拉图式的爱情的另一种(被大家认为具有的)特点是男女平等并且非常理想化。这大概来自于他的另一篇著作《理想国》(The Republic)。不过如果我真的把他在里面描述的男女关系说出来,相信大家就不会再喜欢了。插一句嘴,我读《理想国》时的感觉是——毛骨悚然,里面用十分理直气壮的口吻(还是借用苏格拉底-_-)描述了一个在具有现代民主意识的人看来简直匪夷所思的政治制度,里面充满了独裁、欺骗和不自由。这是世界上第一个对“理想国度”的YY,自此以后,总有人认为自己可以替千百万人设计出一个完美的政治制度,不幸的是所有类似的尝试都给人类带来了无尽的灾难,比如希特勒、比如马克思、比如敏感词。这也是我非常不喜欢柏拉图的原因,我们现在的河蟹生活,说不定在某种程度上就是拜他所赐。
又有点扯远了,接着说理想国里的男女关系,简单来说,和贵党一开始的口号类似——“共产共妻”。柏拉图大概是从斯巴达那里得到的启发,在他的理想国里,所有的少年男孩子和女孩子都要在一起接受教育和体育锻炼,这倒是确实平等。到了适当年龄,他们就由抽签决定和谁xxoo然后生孩子(而且这抽签是统治者骗人们说是完全公平的,实际上更健康更聪明的男女会故意被抽到一起,以便于产生更好的后代,并且故意使得最强的父亲有最多的儿女),这其中没有感情的成分,xxoo只是对国家的义务。孩子出生以后就会立刻从父母身边拿走统一抚养,因此所有人都不知道自己的父母和儿女是谁,这是为了避免由血缘而引起的私情。其他方面的耸人听闻的说法还有很多,我就不详述了,相信前面这些已经足够让小萝莉们知道什么是柏拉图的爱情了。
最后,其实那个拾麦穗的故事还是挺好玩的。我们不妨来建个模型看看到底有没有什么比较好的策略。首先我们假设我们在适当年龄的一段时间遇到的所有mm是可以严格地喜好程度排个序的。当然这个假设是过于理想的,mm之间很难有全序关系,甚至都很可能没有偏序关系,因为传递性难以满足。不过为了便于讨论我们还是假设能给mm排个序出来。现在的问题就是,你面前有一系列的mm,你依次与她们交往,交往一段时间后你就要决定到底是接受还是不接受,如果接受,你就没有机会再找后面的mm;如果不接受,你以后也没有机会再吃回头草。你做当前的决定时是无法预知后面mm的质量的,问要有怎样的策略才能使找到的mm尽可能好。为了便于讨论,再假设你已经知道一共有N个mm,并且这N个mm的出现都是等概率的。也就是说这N!种排列次序都是等可能的。
有一个很有意思的策略,可以让你有大约25%的机会挑到最好的mm。具体来说是这样的,把mm分成两部分,在交往前一半mm时,不管多好,全拒。用机器学习的语言来说,这一半mm是用来train你的model的。接下来的后一半,一旦遇到一个比所有前一半mm都好的mm,就马上接受。如果到最后也没有,那就接受最后一个mm。
在这种策略下,只有当第二好的mm恰好在前一半,而最好的mm恰好在后一半时,我们才能挑到最好的mm。简单计算一下,假定n是偶数,那么满足上面情况的排列一共是 (N/2)*(N/2)*(N-2)! 种情况,再除以总数N!,得到概率为 n / (4(n-1))。当n比较大时,这个数就很接近1/4。
实际上,还能有更复杂些的策略,因为我们不一定非要最好的mm不可。据说可以设计出一种策略使得可以有非常大的概率得到排名在前12logN以内的mm。感兴趣的童鞋们可以试一下,据说是用到Chernoff不等式,我智商太低做不出来了。
后记:其实我是想看一下如果硬把古今中外文哲数理扯在一起是什么效果,我目前精神很正常,勿惊,哈哈。
修正@2010-06-02:感谢小刘同学指出,最后的计算有一个错误。我列的情况并不完全,并不一定非得第二好的mm恰好在前一半,而最好的mm恰好在后一半时才能挑出最好的,但是别的情况都比较复杂了,粗糙的结论就是找到最好mm的概率是大于n/(4(n-1))的,25%只是一个下界。
XTU市赛解题报告
2010年05月23日 384 viewshttp://acm.xtu.edu.cn/OnlineJudge/index.php/contest/problems/contest_id/71
A. Allocation of Memory
简单的用一个大小为M的数组标记一下每个位置属于哪个进程即可,用0表示未被占用。新申请一块内存时从左到右寻找到连续的一段大小为K的区域,找不到就碎片清理,然后找第二次,还是找不到就返回-1。进程退出时扫描一遍数组,把本属于它的位置都标记为0。每次操作的复杂度是O(M),总复杂度是O(N*M)。
B. Beautiful Tree
树型DP容易想到,问题的难点在于“平均值”那个地方。此类问题常见的解法就是二分答案验证(和“最优比率生成树”、“最大密度子图”之类是一样的思路)。假设答案是t,把每个点i的权值变成v[i]-t*w[i],在新的权值下找不少于K个点的权值和最大的子树。如果这个最大权值和大于0,说明我们的t定得小了,反之说明t定大了,然后在相应的一半范围里继续二分即可。
现在的问题就是如何找出一个权值和最大的子树,这一步可以用树型dp来解决。用dp[i][j]表示在以i点为根的子树里选出j个点(且选择了i点)的最优解。状态转移是一个类似背包的过程,每次把一棵子树合并上来。DP的复杂度是O(n^3),总的复杂度是O(logC*n^3)。
C. Civil War
比较简单的数据结构题。用大顶堆维护当前各势力的状态,每次弹出堆顶的两个元素,如果没有同归于尽,再把获胜的一方重新压回堆里。注意处理好当战斗力相同时的字典序比较即可。总复杂度O(nlogn)
D. Dating
中等难度的dp问题。从后往前计算即可,用dp[i]表示自第i天以后能得到的最大期望幸福值。每次你有两种选择,搞破坏或不搞破坏。若搞破坏,则幸福值就是下一天的dp[i+1]。若不搞破坏,那么小R有p*q的概率成功,得到v[i],有p*(1-q)的概率单恋难过K天,故得到dp[i+K+1],有(1-p)的概率不喜欢女孩,得到下一天的dp[i+1]。总结得转移方程
dp[i] = max(dp[i+1], p*q*v[i] + p*(1-q)*dp[i+K+1] + (1-p) * dp[i+1])
复杂度O(N)
E. Enumerating the Squres
简单计数。结果就是M*N+(M-1)*(N-1)+…+(M-min(M,N)+1)*(N-min(M,N)+1)
F. Fat Man
这个题目乍看上去是非常复杂的计算几何问题,实际上有一个巧妙的转化:我们把胖子看成一个点,把树看成半径为R的圆,另外两侧墙壁也要向里推进距离R,这样得到的问题是等价的,因为这时可以看作是只考虑胖子圆心的轨迹。
然后我们建立一个图,把每棵树看作一个图中的点,如果两棵树所对应的圆相交,就在两点之间连边。把两侧墙壁也分别看作两个点S,T,如果墙壁和树所对应的圆相交,也连边。这样,胖子能不砍倒任何树通过峡谷,当且仅当S和T在图里不连通。
现在点上带了权值,问题变成:删掉权值和最小的点使得S,T不连通,这就得到了一个显然的网络最小割问题。把每个点拆成两个点,中间加上容量为该点权值的边,原来的边容量为正无穷,求S, T的最大流也就是最小割即可。
G. Generating Random Numbers
简单题。直接按照题意生成序列,生成过程中用一个大小为M的数组标记一下哪个数已经出现过即可。复杂度O(M) 。出的数据比较多是为了卡住O(M^2)的纯暴力。
H. House
我觉得这是最难的一题。首先有经验的ACMer可以发现这个可以用所谓“插头DP”来解,但现在这个数据范围会爆内存。实际上针对此题的特殊要求,可以将其转化为一个费用流问题来解。下面详细说转化方法:
首先考虑一个简化版的问题:判断能否不用任何“开路”就走遍所有格子。把格子黑白交替染色,黑点做X集白点做Y集,得到一个二分图,若两点相邻则连边。因为要求最终的路径中,每个点被进出各一次,也就是每个点“匹配”上两条边。于是我们可以添加源S和汇T,源到X集中每个点的边容量为2,Y集每个点到汇的边容量为2,中间的点容量为1。求最大流,若最大流能使所有S发出的边都充满,则原问题有解。
下面引入“开路”,此时的难点在于,每个点不一定连到另一条点上,而是可以连到“外界”,并且有多余的花费。在上面得到的图中再添加两个虚拟点u’,v’,表示“外界”。下面假设X集不小于Y集(否则可以交换X,Y集,问题不变)。X集中所有在边界上的点都有一条通向u’的边,容量为1,费用为1,表示此点可能通向外界,v’到所有在边界上的Y集点都有边,容量为1,费用为1,表示此点可能通向外界。u’到v’之间有边,容量为无穷,费用为0。最后,u’到T直接有边,容量为(|X|-|Y|)*2,费用为0,这是为了处理X集里多出来的点,这些点允许直接流向汇。求最小费用最大流,若最大流能使所有S发出的边都充满,则原问题有解,费用除以2即为最小“开路”数。
题目中的第一个例子建成图如下所示,其中点中的(x,y)表示第x行第y列的格子:
I. I, Robot
很容易看出是BFS,稍微加了一点难度是涉及到机器人的方向,实际上只需要把状态加一维即可,每个状态包括机器人的横坐标、纵坐标、当前方向。总的复杂度是O(N*M*4)。注意有不能到达的情况。
J. Just a Triangle
方法很多,数据量也不大,基本上怎么写都可以过。本来想卡一下O(n^3)的暴力,结果发现要想那样的话木棍长度就只能出到高精度了(汗)。我认为比较好的方法是先排序,如果能组成三角形,那么一定存在连续的三个值能组成三角形,所以只需判断O(n)次相邻的三个值即可。
后记废话:
题目总的来说是很水的,如果以Regional的难度来看除了H题都可以看作是中等以下。其实我是很想让大家挖掘一下各题的背景资料,包括每道题一开始的一句话都不是随便乱写的(虽然因为水平有限,大部分套得比较生硬,嘿嘿)。不过明显是没有很多人在比赛中顾得上关心这个,所以只好自己选几个说一下
A题Bill Gates那句话是网上流传的众多“IT界最愚蠢的预言”之一,感兴趣的同学可以去搜一下其他,现在看上去都很有喜感,我印象比较深的另外一个是更早的忘了谁说的了:“未来的计算机可能只有一吨重”。B题是我很喜欢的一句话,Dijkstra这个人不止是很牛的计算机科学家,还很喜欢说一些格言式的话出来。C题背景是来自著名的政治讽刺小说《1984》,样例里的几个名字也是出自此(多嘴一句,我觉得每一个身在天朝的人都应该看看这小说)。D题那句诗是已经被用滥了,不过背景描述我觉得很有意思,哈哈。F题用来怀念已经为这个时代所不容的鲁迅老人家。G题冯诺依曼那句话在TAOCP里也有提到,随机数的生成确实是一个很复杂的问题。H题用来感叹一下当前的房事(市)吧,杜甫老人家真是深谋远虑啊……(随便说一句,这题其实不是我原创,貌似在NOI冬令营上有讨论,但是没看到有比较完整的题解,而且我也找不到题目原始出处,汗)I题题目来自著名科幻小说家阿西莫夫的短篇小说集《我,机器人》,题记是他提出的著名的“机器人三定律”之一。J的题记是纯粹硬凑的,来自泰戈尔的《飞鸟集》。我本来想写一句跟三角形有关的话,结果无论如何想不出。
[转载]5月12日,让我们哀悼敏感词
2010年05月12日 431 viewshttp://blog.renren.com/blog/308446797/464406568
5月12日,让我们哀悼敏感词
孙宇晨
马上要到5月12日了,有同学给我发站内信,说他是四川人,期间经历了很多,希望我能写点东西。我觉得很有意义,便有了这篇文章。
前年的这个时候,四川绝大部分的孩子已经在宿舍安睡了。他们并不知道明天的下午会发生什么。他们并不知道那些爷爷给他们审批规划的是脆弱如粉末的教学大楼,这与其说是教室,不如说是早就盖好的坟墓。他们更想不到的是,这件事情才仅仅过去两年,在我们这片神奇的土地,这一切都变成了敏感词,甚至包括他们自己的名字。
有人试图公布死亡孩子的名单,结果他和孩子的名单一起成了敏感词;有人试图调查教学大楼的质量问题,结果他和质量问题一起成了敏感词;有人试图为死亡孩子的家长讨回公道,结果他和家长们也成了敏感词。时间才仅仅过了两年,权力再次试图从记忆抹去这一切,它并不是第一次做这种事情。
我提笔写这篇文章时,我朋友告诉我,这个时候,恐怕写地震不合适吧?他说的很对,在祖国母亲的照看下,我每一提笔,就会想到:西藏不能写,新疆不能写,地震不能写,领导不能写,质量不能写,奶粉不能写,地沟油不能写,三鹿不能写,孩子不能写,房价不能写,于是乎,除了把笔丢掉,把电脑关掉,我不知道自己还能做什么。
这一切让我的思绪倒退回了数千年前的封建社会,那个数千年前“为尊者讳,因言治罪”的时代,一位汉武帝时期的作者提笔而起之时,也必然会想到:刘彻不能写,汉武帝不能写,领导不能写,匈奴不能写,李陵不能写,李广利不能写,西征不能写,于是放弃了历史学家这个职业,他是聪明的,如果他写了,他就会被阉掉。
对于这一切,古今无不同。虽然我使用这人类历史上最为先进的电子书写工具——笔记本电脑,但这并不标志着我生活在一个最为基本的现代社会。两千年了,我们还是没有逃离敏感词的时代,这个时代贯穿中华民族悠长的历史,无时无刻不彰显着我们这个民族的奇耻大辱。
我们生活在一个充斥敏感词的时代。我们这个时代什么都缺,缺良知,缺公正,缺尊严,缺生存,缺智慧,独独不缺的是敏感词。将老祖宗的传统保持到现在还没有丢掉,这要感谢国家,更要感谢我们伟大的领导同志,他们毅然将自己光辉的名字贡献到了敏感词的庞大词库之中,与各种生殖器名称俗称,各种性交姿势名称交织在一起。我不知道这种现象是否也恰如其分的反应了他们的生活。
拉开长长的敏感词列表,有的时代被列入了敏感词,是因为那是个最为光明的时代;有的时代被列入了敏感词,是因为那是个最为黑暗的年代;有的人把自己的名字列入敏感词,是因为他做了最为见不得人的勾当;有的人的名字被列入了敏感词,却是因为他做了最为光明正大的壮举;有的事情被列入了敏感词,是因为这件事情隐藏了这个民族最为惨绝人寰的悲哀,有的事情被列入了敏感词,是因为这件事情彰显了这个民族最后的良心与希望。
长长的敏感词列表,它会告诉我们5月12日发生了什么,它会告诉一切我们想知道而无法知道的东西,它会向我们诉说这个民族古老而悠长的悲歌。
若我们看清了这一切,那么在5月12日,让我哀悼逝者,哀悼为了逝者差点成为逝者的人,我们还想哀悼很多,但是我们只能哀悼敏感词。
2010/5/11
于北京大学
(by RoBa: 补充一个链接 http://g.s8.hk/ob )
PKU Campus 2010 解题报告
2010年05月10日 882 views此报告非官方版,不保证完全的正确性。另由于本人水平和时间有限,目前尚未做出最后两题,留待以后补充。比赛链接:http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1359
A. Bubble Sort
此题公式为 k! * (k+1) ^ (n-k) – (k-1)! * k ^ (n-k+1)。我是比赛时直接在网上搜的公式(汗),还没有仔细想这个公式是如何推出的。
B. The Bonus Salary!
最小费用流。把所有区间的端点当做图中的点,对于权值为w的区间[s,e),加边(s->e),容量为1,费用为-w。再对所有相邻的点加边(i->i+1),容量为K,费用为0。源点S到最左端点加边,容量为K,费用为0。最右端点到汇点T加边,容量为K,费用为0。容易发现每个流量都对应了某一天的安排。于是求最小费用最大流再将费用取反即可。
C. Tour in Wonder Land
树型DP。首先我们猜想,必然存在一种最优方案使得总是遍历完某子树的所有结点后再转到另一子树,而不是在不同子树间来回跳(证明略)。于是对每个结点i考虑遍历完它的所有后代的最小花费。我们用dp[i][0]表示遍历路线是从子树的根结点i进入然后走完子树所有点后从某一非根点跳出(或者是从某一非根点进入最后从i点走出,因为是无向图,这两者是等价的),用dp[i][1]表示遍历路线是从非根结点进入,又从非根结点跳出(当然,在过程中要经过i点)
于是,对于叶子结点有dp[i][0] = dp[i][1] = 0. 对其他点i,设i的儿子数为C,dp[i][0]有两种可能,一种是从i走进某个儿子j,这样走完j的花费是dp[j][0],然后对其他每个儿子k都花费dp[k][1],再加上在C个儿子间跳转的花费C-1;另一种是所有儿子k都走dp[k][1],再加上跳转的花费C。对于dp[i][1],一种可能是选择某两个儿子j,k,走花费dp[j][0]和dp[k][0](也就是经由j,k从根i绕一下),对其他儿子走dp[][1],再加上跳转花费C-2;另一种是所有儿子都走dp[][1],加上C+1的跳转花费(因为要跳到根再跳出来)。注意因为最后要回到1点,所以在总的树根处要再特殊处理一下。(我觉得我可能做复杂了……)
D. The xor-longest Path
首先一个关键的观察是,重合的路径经过XOR会“抵消”掉。于是我们求出从根结点到每个点x的XOR路径值a[x],则对于任意两点(x,y),他们之间路径的权值就是(a[x] XOR a[y])。而所有的a值可以用一个dfs简单完成,现在剩下的问题是,如何快速找出两个值使得其xor以后最大。
我们可以把全部的a值表示成二进制串,然后建立一个Trie。每个结点最多发出两条边,分别对应’0′和’1′。然后我们就可以在与a[i]的位数成比例的时间内对每个a[i]值求出它和哪个值异或后的结果最大。具体做法是先对a[i]按位取反,然后在trie上匹配。每次匹配时从trie的根开始,如果有相应的边,就沿着走一步,如果没有,就走另一条边,此时就出现了一个不一致的值,也就是结果的相应位置上有一个1。这样一直走完,得到的结果取反以后就是对a[i]来说最大可能的异或值。这样时间复杂度是O(31*N),此题时限较紧,写程序时要注意优化。我用vector建图直接TLE到死,杯具。
E. Xiang Hex
水题,不多说
F. Hexagon Coin Toss
关键在于计算六边形内的各种不同区域的情况,可以分为内部小六边形(盖住一个)、边缘(盖住两个)、角部(盖住三个)三部分考虑。其中小六边形和角的面积容易计算,总面积减去这两部分就是边部分的面积。如下图所示,红线围起来的部分即为可以覆盖三个正六边形的圆的圆心所在区域。(当然如果是在边界的话就不是了)总的大六边形减去小六边形再减去六个角部,就是可覆盖两个六边形的圆的圆心区域。然后把在外边界的情况处理一下就可以得到结果了。
G. I Wanna Go Home
对两种点分别求最短路,再枚举一下通过哪个边从某种点走到另一种边。
H. Repeater
简单题,递归写就可以。注意可能容易超时,实现上注意优化。
I.J.待续
[转载]掌声响起
2010年05月4日 263 viewshttp://www.hecaitou.com/blogs/hecaitou/archives/134416.aspx
我的好朋友宁财神很喜欢《叶问》,自然也非常喜欢《叶问2》。这对我选片有利,因为只要是他喜欢的武打片,我肯定就不用看了。同样是70后的老怪, 我清楚地知道他会喜欢什么,也正因为这样,我就不会喜欢。
生于70年代,意味着在80年代中后期一直到90年代早期,个人的青春期一定会遭逢功夫。没有看过《武林》,起码也看过《散打和武术》这类型的杂 志。在很小的时候,就知道什么站桩、寸劲、桥手一类莫名其妙的单词。宁财神喜欢的功夫片,大多是因为其中有所谓的“真功夫”,意思是他老人家坐在电影院 里,突然出现一段桥手,他懂了,他回忆了,他满意了。又来一段中路进攻,他看到了上中下三盘齐动,拳脚一根线打中间,他又懂了,他又回忆了,他又满意了。 所以,他所谓的“好”,要放在他的语境里去理解,未必是80后、90后喜欢的那种“好”。
今天下午实在没有片子可以看,于是去看了《叶问2》。看下来觉得宁财神一定会很喜欢,那我的态度是什么?你猜?
由于没有剧情可言,所以《叶问2》也就没有什么剧透的顾虑,我准备用一句话讲完:叶问在1950年到香港谋生,当时有一个蔑视中国武术的英国拳师 “龙卷风”在擂台上打死了洪拳的洪师傅(洪金宝),叶问代表咏春拳灭了龙卷风,为中国武术界赢得了尊严。让我诧异的是,甄子丹扮演的叶问击败龙卷风的时 候,电影院里响起了热烈的掌声和叫好声。
为了什么而鼓掌?我觉得导演对观众情感的控制一直很好,收放自如。类似我这样情感充沛的人,往往镜头才变暗,音乐才转调,女主角的眼睛都还没有忽 闪,我的鼻子就已经酸了,泪水在眼眶里打转。有鉴于此,我需要经常分析一下自己的情感从何而来。在《叶问2》里,我也感觉到振奋,基于以下几个线路:
1、影片暗示了龙卷风背后的英国白种督察蔑视中国人,让我觉得不爽。
2、龙卷风放了很多狂妄的狠话,对中国武术不屑一顾,让我觉得很不爽。
3、龙卷风活活打死洪金宝时,没一拳都是慢动作,让他死得极为惨烈,让我觉得很不爽。
4、裁判团在叶问占优的情况下,修改规则,不允许叶问用腿,只准用手,让我觉得很不爽。
在以上不爽的情况下,叶问赤手空拳把龙卷风打得鼻青脸肿,休克昏迷,我自然觉得爽到哆嗦,深感振奋,一扫压抑。可是,我瞬间想明白上面的情感铺垫之 后,觉得对导演的恶感空前。因为他试图用这点廉价的东西控制住我,产生他想要的结果,这怎么可以?
回想过去的三十多年间,我有一小半的时光都在学校里接受教育。这种教育的优劣我不想评价,但是我想指出一点:那么多年来,我一直努力摆脱的就是那种 来自教育的自我侮辱,受压迫感,和被害情结。书本里一直在强调,周围的世界对我们心存恶意,诸多国家在历史上曾经欺负过我们。而我们的国家多么美,人民多 么好,太美太好以至于世人无法不对我们垂涎三尺,非要占我们的便宜不可。总之,他们都没安好心,打心底里看不起我们。所以,一定要给他们点教训,这样他们 才会打消邪念,看得起我们。
进入网络世界十年之后,我才终于明白,原来这种教育是要让我们成为小受。你有菊花,我有菊花,大家都有菊花。但是,菊花之于小受有特别的意义,因为 他觉得所有人都想爆自己的菊花,因此紧张不已。紧张了很久,事情却始终没有发生,于是他的内心就发生了转变,变得很焦急:为什么还没有人来爆我啊?这就是 小受心态。
火烧圆明园是耻辱,马关条约是耻辱,治外法权是耻辱,侵华战争是耻辱,杜勒斯拒绝握手是耻辱,总是都是耻辱。我们仿佛除了受辱,没有别的历史。于 是,我们除了报复,大概也没有其它事情可以做。我觉得,这种心理很病态。好在人人都有这种病,也就不用普遍治疗,大家带病工作,带病生活就好了。再过五十 年,若我们能一直发展良好,自立自强,习惯了做强者,那么这种心态也就会慢慢淡化,开始宽容、简单,易于相处。不会总以为外面的人想占便宜,想羞辱我们, 除了菊爆我们之外就无事可做了。我们也不会每天以发抗议、强烈抗议、最强烈抗议为能事,全国人民的情感月经性受伤。
对于这样一群有病的人,用《叶问2》里面的那些手法进行刺激,好诱发症状,不说是下作,起码是不厚道。如果是在医院里,医生给糖尿病患者巧克力吃, 好收治疗费,这是犯罪。如果是医生给狂犬病患者强光照射,浸泡进浴缸,那是摧残。做电影导演就这点好,做相同的事情,诱人发病,这叫技艺精湛,感人至深。 一群人为了根本已经消失多年的耻辱,甚至是剧情捏造出来的羞辱,最终欢呼鼓掌,这是一件多么扯的事情啊?
我喜欢电影院里有掌声响起,但是,我不希望是这种掌声。活在一个别人总想方设法要羞辱我们,我们想方设法要教训对方的世界里,当真很辛苦。而我最担 心的是,当你已经蹦起来三丈多高了,落下来却发现对方的眼睛很坦诚,很无辜,很困惑,搞不懂为毛你那么High,为毛那么激动?
十年前被蛇咬了,十年后见到绳子就来一剪刀,没有绳子搓一条出来再一剪刀,而且觉得这就是杀死了十年前的那条蛇,这就是我看《叶问2》的感觉,这就 是我对那些掌声的感受。
Hamilton路与带下界的网络流
2010年04月16日 584 viewsQQ群里戴牛提了这样的一个问题:为什么不能用求解带下界的网络流的方法来做Hamilton问题?详细来说,就是把一个图的每个点拆成两个点,在中间加上一条容量上下界都为1的边,求从一点S到另一点T的流,如果可行流存在,则S,T之间存在Hamilton路。
乍一看上去似乎非常合理,当然,我们知道肯定是有哪里出了问题的。因为Hamilton路是经典的NPC,而网络流有无数种多项式做法,如果真的这么把一个NPC解决了,那这几十年以来的计算机科学家们也忒弱了。
问题出在下界的转化那一步。首先来复习一下标准做法:带下界的网络流的求法通常分两步,第一步是判断是否有可行流,然后再求最大流或最小流。这里我们只关心第一步,这一步实际上是把问题转化成了一个点上可以发出或吸收流量的可行环流问题。先形式化一下这个问题(1):
给定网络(V,E),其中每个点i都有一个可正可负的值e[i],每条边(u,v)上有一个容量上界c[u,v]。我们要对每条边[u,v]求一个流量f[u,v],满足f[u,v] <= c[u,v],且Sigma f[u,v] = e[u],这里v取遍u的所有相邻点求和。
也就是说必须满足每个点都可以发出或吸收一定数量的流量,显然要使可行流存在必须有Sigma e[u] = 0,u取遍所有点。对这个问题的求解,我们可以添加一个源S和汇T,S向所有e[u]>0的点连边,容量为e[u]。所有e[u]<0的点向T连边,容量为|e[u]|。求最大流,若最大流能把S发出的边充满,则原问题(1)有解。
然后我们来看下界的转化。设每条边(i,j)有上界U[i,j]和下界L[i,j],流量f[i,j]须满足L[i,j] <= f[i,j] <= U[i,j],我们把它们全减去L[i,j],即0 <= f[i,j] – L[i,j] <= U[i,j] – L[i,j]。可以发现,这样变成了只以(U[i,j] – L[i,j])为上界的边。但是因为流入的量减少了L[i,j],我们必须把它补偿上,也就是说必须强制点j“发出”一份L[i,j]的流量,这个就对应了上面的e[]。同时,强制点i“吸收”一份L[i,j]的流量。
于是转化方法就是,把边的上界变成U[i,j]-L[i,j],然后令e[i] = Sigma L[i,j] – Sigma L[k,i]。这里j取遍所有i指向的点,k取遍所有指向i的点。然后我们添加一条从T指向S,容量为正无穷的边。求此网络是否存在可行环流。这就回到了问题(1)
注意问题(1)里并没有哪两个点是特殊的源或汇,这是一个环流问题,只要满足每个点的e满足要求就行。对于有源汇的问题,就如上面的转化,加一条从汇指向源的边,容量为正无穷即可。这样就可以让所有流量都再流回去了。但是Hamilton的转化也就在这里出了问题,我们经过转化后求的是可行环流,但这个可行环流并不一定是Hamilton路。原因在于这个环流并不保证连通Hamilton路中的两个端点,我们求出的可能是若干个不相连的环,它仍然是可行环流,满足问题(1)里的所有限制条件,但无法从它构造出Hamilton路。见下例,很明显,1和6之间不存在Hamilton路:
如果按照上述转化,就得到下图:
这里i和i’间的虚线本来是上下界都为1的,相减之后没有了。6′到1的虚线是容量为正无穷,其余边容量均为1。图比较乱,仔细看会发现S发出的6条边都能充满,比如S->2′->3->T, S->3′->1->T等等。这个图的可行环流存在。但是这个可行环流实际上是不相关的两部分,所以Hamilton并不存在。
有童鞋可能认为可以求出流来,再判断一下这个环流是不是相通了原来的两个端点。但是这并不是充要条件,我们求出的环流不连通并不说明Hamilton路一定不存在,而我们在求环流时无法强制令其连通。
ZJU 2010校赛解题报告
2010年04月10日 877 viewsEdit: 已经有官方完整版了 http://www.hhanger.com/blog/?p=438
抢在官方报告前发一个,为Blog增人气,嘿嘿。题目出得我觉得非常好,先写大家比较关心的D和G,以后再慢慢补全。比赛页面:http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=307
Problem D. Game
我们把棋子看作点,若两棋子的距离不超过L则在两点间连边。结论是很简单的:求这个一般图的最大匹配,如果不存在完美匹配(即有的点没有被匹配上),则先手必胜,否则后手必胜。下面说原因:
如果图中不存在完全匹配,则先手方可以先拿走任意一个不在最大匹配中的点u,则后手方不管怎么拿一定会拿到在最大匹配中的点v。(不然的话我们就可以把u-v这条边加进去得到更大的匹配,与前提矛盾)然后,每次先手方只要拿与后手方上次拿的那个点匹配的点即可。因为我们知道当得到最大匹配以后,图中是不可能存在交错增广路的,所以后手方每次都不可能选出不在匹配中的点(不然就是找到一条新的交错增广路了),这样一直进行下去,最后无路可走的一定也是后手方。
反之,若图中有完美匹配,则先手第一手无论如何都会选择在匹配中的点,然后后手就掌握主动了,像前面说的一样一直沿着这个最大匹配走下去,最终先手必败。
Problem G. Islands
这题我觉得我的做法可能有点复杂了。首先的观察是,因为不允许有多余的边,所以最后补出来的结果必定每个点都有一入一出,所以如果某个点的入度或出度大于1的话,直接无解。然后我们可以发现,如果一开始没有任何边的话,实际上这就是一个错排问题,也就是求一个1..N的排列使得每个数都不在它对应的位置上。下面先来说错排问题的递推解法(关于错排还能用容斥原理得到一个漂亮的公式,此处略):
设n个数的错排方案数是f[n],考虑最左边一个位置A,设它指向B,则有两种情况:
(1)B指回A,这时还剩n-2个数,所以问题变成了N-2个数的错排
(2)B指向A以外的数,这时我们会发现得到了一个N-1个数的错排(因为A已经确定指向B,本来是限制B不能指向自身,现在变成了限制B不能指向A,其实是一样的)
因为A一开始可以有n-1种B的选择,所以就有 f[n] = (n-1) * (f[n-1] + f[n-2])
现在的复杂之处在于这个排列里某些位置的值已经确定了(就是那些已经存在的边),除掉这种边以后,剩下的位置就分为了两类,一类是没有任何限制的,一类是不能指向它自身的。比如有五个点,已经有(2->3),(3->4)两条边,则4这个点就是没有任何限制的(它可以随便指向1或2或5),而1,5两点不能指向自身。类比错排问题的递推,我们用f[n][m]表示n个被限制不得指向自身,m个无限制的方案数,仍考虑第一个位置A,则有如下几种情况:
(1) A指向了一个有限制的B,共有(n-1)个这样的B,则有两种情况:
1a. B指回A,问题变成n-2个有限制,m个无限制
1b. B指向其他数,问题变成n-1个有限制,m个无限制(B的限制是不能指回A,类似上面错排第二种情况的讨论)
(2)A指向了一个无限制的B,共有m个这样的B,同样有两种情况:
2a. B指回A,问题变成n-1个有限制,m-1个无限制
2b. B指向其他数,变成n个有限制,m-1个无限制(这时B从无限制变成了有限制)
综上得到递推方程 f[n][m] = (n-1) * (f[n-2][m] + f[n-1][m]) + m * (f[n-1][m-1] + f[n][m-1])
边界条件是f[0][0] = 1
C++ Primer 笔记(5)
2010年04月10日 268 viewsChapter 14
这章主要讲操作符重载。
操作符重载不能用于操作数都是内置类型的时候。比如,我们不能重载operator+(int,int)。操作符的优先级、结合性、操作数个数不能改变。重载&&,||和逗号后,不再保证求值顺序和短路运算,最好不要重载这几个。
大部分重载操作符可以作为普通函数或类的成员函数,在第二种情况下,参数列表里会少一个,因为省略了隐含的this。一般将算术和关系操作符定义非成员函数,而将赋值操作符定义为成员(如上章介绍)。如果作为普通函数,因为往往要访问私有成员,在类定义里往往要将该函数设为友元。操作符也可以用类似函数调用的形式访问,像这样 loli = operator+(loli, loli2).
赋值(=)、下标([])、函数调用(())、成员访问(->)这几种操作符必须定义为类成员。+=, ++之类,最好定义为成员。对称的运算,如+, ==,往往定义成普通函数。
重载IO操作符应该声明为普通函数,不然的话类就只能作为左操作数,就会变成这样的诡异形式 loli<<cout,明显不符合习惯。而我们又不能为iostream类添加成员,所以只能定义成普通函数了,然后把它作为我们的类的友元。
重载加法时应该返回一个新的对象而不是引用(所以a+b是右值),而+=一般返回的是对左操作符的引用。(这种情况下用+=效率高些?)
某些算法(例如find())以及关联容器需要我们定义<或是==,要注意<的定义满足以前说的那几个条件。
下标运算符可能作为左值,故应返回引用。但对const对象应返回const引用,所以应该写const与非const两个版本的重载函数,如chapter 12所讲。
重载自增和自减操作符应该遵循惯例,前置返回引用,应该这样写:Loli& operator++(),后置返回变化之前的值,应该这样写:Loli operator++(int),最后那个int是为了与前置区分,在函数体内无视它。
定义了函数调用操作符的类,又被称作函数对象,因为这种类的对象看上去表现得像一个函数。这种东西最常用在STL里,比如我们自己定义一个结构体的比较函数对象,优先按照年龄,然后按照姓名排序:
struct Lolicmp {
bool operator()(const Loli &a, const Loli &b) {
if (a.age != b.age) return a.age < b.age;
return a.name < b.name;
}
};
std::set<Loli, Lolicmp> loli_set;
std::vector<Loli> loli_arr;
sort(loli_arr.begin(), loli_arr.end(), Lolicmp());
标准库也定义了若干函数对象,比如我们最常用的greater<T>,所以把int数组从大到小排序就是sort(a, a+N, greater<int>())
Chapter 15
本章介绍OOP的核心:类继承和动态绑定。继承就是指类之间的层次关系,一个类是另一个类的派生类之类。动态绑定是指在运行时才决定是调用基类的成员函数还是派生类的成员函数,这就产生了所谓多态。C++里实现要想实现动态绑定需要用对象的引用或指针,看下面例子:
class Loli {
public:
virtual void speak() { cout<<"oniisan~"<<endl; }
virtual ~Loli() { }
Loli() : age(0) { }
protected:
int age;
};
class TsundereLoli : public Loli {
public:
void speak() { cout<<"ulusai! I am "<<age<<" years old."<<endl; }
};
void func(Loli &t) { t.speak(); }
int main() {
Loli a;
TsundereLoli b;
func(a);
func(b);
return 0;
}
这个程序有很多地方需要解释,下面会慢慢说。
执行上面程序会发现,两次调用func()实际上调用了不同的函数,尽管func里写的是接受基类的引用(在书里这个引用或指针的类型叫做静态类型),但传进去的对象会“知道”自己实际的类型(书里叫动态类型)。要实现这个功能,一定要把基类对象的相应成员函数声明为virtual,只有虚函数才会执行动态绑定,普通成员函数的执行是在编译期就确定的。如果上面例子中的speak()不是虚函数的话,因为func接受的是基类Loli的引用,故一定调用基类的speak()。注意,一旦基类里声明某函数为虚函数,它就一直是虚函数,在派生类的实现里无需再带virtual关键字(是不是带上更清晰些?)
基类与派生类之间的转换
如上所述,存在派生类引用(或派生类指针)到基类引用(或基类指针)的自动转换,这就是实现多态的关键。反之的自动转换则不存在,例如如果把上面func()函数改成接受TsundereLoli的引用,则编译不过,因为func(a)这句要求一个基类引用到派生类引用的转换,这是不能自动进行的。
上面说的是指针或引用的转换,对象的转换则完全不同,如果把上面的func函数改成 void func(Loli t) {…},此时它自始至终都是接受一个Loli类型的对象,不存在动态绑定,如果把TsundereLoli对象传递过去,则TsundereLoli会被强行“切割”(slice down)成一个Loli对象,然后调用Loli::speak(),TsundereLoli对象的任何不属于Loli子对象的数据成员和函数成员将被丢弃。
下面来详细分析一下原因:
当用派生类对象对基类对象进行初始化或赋值时,有两种可能的情况发生:第一种情况很罕见,就是在基类里有一个以派生类为参数的复制构造函数和赋值运算符,像下面这样子:
class TsendereLoli;
class Loli {
public:
Loli(const TsendereLoli &) { ... }
Loli& operater=(const TsendereLoli &) { ... }
};
这时我们可以自己定义从派生类对象转换到基类对象时做什么。不过这种情况显然是非常罕见的,理论上基类的作者不应该知道具体是谁继承了自己,他只应该对自己以及父类负责。第二种情况是常见的,也就是基类里只有以自己的引用为参数的构造函数和赋值运算符(如果不写的话默认产生的也是这种):
class Loli {
public:
Loli(const Loli &) { ... }
Loli& operater=(const Loli &) { ... }
};
这时如果我们把一个派生类作为参数传进构造函数或赋值过来,这时会发生的事情是:首先将基类类型的引用(Loli&)绑定到一个派生类的对象,然后将这个引用作为实参传递给复制构造函数或赋值符,因为是基类的引用且非虚函数,函数内部只能使用到派生类里的Loli子对象部分,如果调用函数的话也只能调用基类的函数,通常情况下函数内部的实现是把基类的成员一一复制过来(不写的话默认也是这样的),当函数结束后,就得到了一个真正是基类的对象,不存在任何派生类的成分,这时我们就说派生类被slice down了。
(15章未结束,待续)
C++ Primer 笔记(4)
2010年04月8日 263 viewsChapter 12 (cond)
关于构造函数
所谓构造函数初始化式(Constructor Initializer)是指在构造函数参数列表后面冒号里的那一列东西,这是一个很多熟练程序员都可能不太了解的地方,大家可能更习惯在构造函数的花括号里写东西。但是实际上只有在冒号后面的那些才是真正的初始化,在花括号执行的只是普通的赋值语句,明确地区分这两者看上去有点无聊,但某些情况下是必须要考虑的。一是效率上的原因,不管怎么写,在创建对象时都要先对每个成员进行初始化,然后再执行花括号里的普通计算。如果写在花括号里,实际上是先初始化一次,再赋值一次覆盖掉初始化的内容,这样就造成了浪费,如果成员是比较大的对象,效率上会有影响。二是某些对象是不允许赋值的,比如引用和const成员,这时只能在初始化式里初始化,不能在花括号里赋值。总之,尽量写在初始化式里比较好。
初始化的次序与成员声明的次序一致,与初始化式里的次序无关。尽量不要让初始化的值依赖其他成员变量,以免造成混乱。
如果初始化式里没有指明某个成员变量,则按照默认方式初始化:对于类类型成员调用默认构造函数,对于内置类型成员,如果是全局对象则置0,局部对象则为未定义值。
如果对类A声明了任何一个构造函数,则编译器不会再自动合成默认构造函数。这种情况下会带来诸多不便,比如如果某个类B以类A作为一个成员,则类B也不再有默认构造函数;不能声明A的静态数组;包含A的容器也不能只用一个表示大小的值来初始化,等等。所以通常情况下最好要有个默认构造函数。
如果类有接受一个参数的构造函数,这时就隐含了一种类型转换的可能,见下面代码:
class Loli {
public:
Loli(int n) : age(n) {}
int get_age() {return age;}
private:
int age;
};
void print_loli_age(Loli loli) {
cout<<loli.get_age();
}
虽然print_loli_age要接受一个Loli类型的参数,但我们可以直接调用print_loli_age(15)。因为Loli有一个接受一个int参数的构造函数,这样就把15自动转化生成了一个Loli类型。有的时候这样的隐式转换不是我们想要的,就需要在构造函数前面加一个explicit来禁止这种转化,此时如果想转化的必须显式调用:print_loli_age(Loli(15))
关于static成员
static成员独立于类的任何实例对象而存在。static成员函数没有this指针,也不能访问非static成员。static数据成员必须在类的定义体外定义恰好一次,在定义同时初始化,通常把它和类的成员函数的实现放在同一个源文件里。
Chapter 13
本章主要是三部分内容:复制构造函数、赋值运算符和析构函数
复制构造函数是一种特殊构造函数,具有单个形参,该形参(常用 const 修饰)是对该类类型的引用。当定义一个新对象并用一个同类型的对象对它进行初始化时,将显式使用复制构造函数。当将该类型的对象传递给函数或函数返回该类型的对象时,将隐式使用复制构造函数。
在初始化的时候,如果是直接在圆括号里写参数,例如 string s(10, ‘a’),则调用相应的构造函数,如果出现了赋值号(不知道这么说严谨不),例如 string s = “aaaa”,则先生成一个临时对象,再调用复制构造函数复制过去。
当对象作为非引用的参数传递给函数的时候,以及从函数里返回一个非引用的对象的时候,会调用复制构造函数生成一个副本。另外如果是定义了类似vector<T> v(n)之类的东西的话,会先用默认构造函数生成一个临时对象,然后用复制构造函数复制n份。
如果没有显式声明复制构造函数,编译器会自动生成一个。多数情况下这就够用了,但是有些情况下还是不行的,比如对象里面有个指针或引用而我们想实现一个deep copy的功能,或者对象里有一个不可复制的成员,这时候就要自己定制了。定制的复制构造函数和普通的构造函数没什么大区别,接受一个相同类型的引用(通常是const)作参数,推荐用初始化式进行初始化,然后在花括号里干其他的事。
如果我们想禁止对象被复制,应该写一个private的复制构造函数(不能不写,不写会自动生成),但这样的话自己的成员函数和友元还是可以调用它,进一步的方法是只声明而不实现(好强-_-)。这样的话,如果是外部调用,会编译错误,如果是自己的成员函数或友元调用,会链接错误。
重载赋值运算符时,代码的写法看上去就像把operater=当作类的一个成员函数一样,它接受一个相同类型的const引用作为参数,返回值是同一类类型的引用。注意处理好赋值给自己的情况,这种情况通常要特判一下。
如果是new出来的对象,只有在delete时才会被删除(此时调用析构函数)。如果忘了删除就会导致所谓内存泄漏。内存泄漏往往只有在程序长时间运行后内存消耗严重时才表现出来,比较难于发现。
关于智能指针:所谓智能指针是指保存了一个“引用计数”的指针,它可以避免当多个指针指向同一对象时,通过其中某个指针把对象删除了,但其他的指针并不知道,继续访问就会导致错误。通过保存一个引用计数,只有当指向这个对象的指针数为0时,才真正把对象删除。在这种情况下需要自己实现一个指针类,把原生指针包装一下,通过重写该指针类的构造、复制、析构函数实现引用计数的管理。在13章的最后给了一个很好的例子。(ps. 在boost里有标准的智能指针实现了?)


