Monthly Archives: May 2010

XTU市赛解题报告

http://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列的格子:

clip_image002

I. I, Robot

很容易看出是BFS,稍微加了一点难度是涉及到机器人的方向,实际上只需要把状态加一维即可,每个状态包括机器人的横坐标、纵坐标、当前方向。总的复杂度是O(N*M*4)。注意有不能到达的情况。

J. Just a Triangle

方法很多,数据量也不大,基本上怎么写都可以过。本来想卡一下O(n^3)的暴力,结果发现要想那样的话木棍长度就只能出到高精度了(汗)。我认为比较好的方法是先排序,如果能组成三角形,那么一定存在连续的三个值能组成三角形,所以只需判断O(n)次相邻的三个值即可。

后记废话:

题目总的来说是很水的,如果以Regional的难度来看除了H题都可以看作是中等以下。其实我是很想让大家挖掘一下各题的背景资料,包括每道题一开始的一句话都不是随便乱写的(虽然因为水平有限,大部分套得比较生硬,嘿嘿)。不过明显是没有很多人在比赛中顾得上关心这个,所以只好自己选几个说一下 :D

A题Bill Gates那句话是网上流传的众多“IT界最愚蠢的预言”之一,感兴趣的同学可以去搜一下其他,现在看上去都很有喜感,我印象比较深的另外一个是更早的忘了谁说的了:“未来的计算机可能只有一吨重”。B题是我很喜欢的一句话,Dijkstra这个人不止是很牛的计算机科学家,还很喜欢说一些格言式的话出来。C题背景是来自著名的政治讽刺小说《1984》,样例里的几个名字也是出自此(多嘴一句,我觉得每一个身在天朝的人都应该看看这小说)。D题那句诗是已经被用滥了,不过背景描述我觉得很有意思,哈哈。F题用来怀念已经为这个时代所不容的鲁迅老人家。G题冯诺依曼那句话在TAOCP里也有提到,随机数的生成确实是一个很复杂的问题。H题用来感叹一下当前的房事(市)吧,杜甫老人家真是深谋远虑啊……(随便说一句,这题其实不是我原创,貌似在NOI冬令营上有讨论,但是没看到有比较完整的题解,而且我也找不到题目原始出处,汗)I题题目来自著名科幻小说家阿西莫夫的短篇小说集《我,机器人》,题记是他提出的著名的“机器人三定律”之一。J的题记是纯粹硬凑的,来自泰戈尔的《飞鸟集》。我本来想写一句跟三角形有关的话,结果无论如何想不出。

[转载]5月12日,让我们哀悼敏感词

http://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 解题报告

此报告非官方版,不保证完全的正确性。另由于本人水平和时间有限,目前尚未做出最后两题,留待以后补充。比赛链接: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

关键在于计算六边形内的各种不同区域的情况,可以分为内部小六边形(盖住一个)、边缘(盖住两个)、角部(盖住三个)三部分考虑。其中小六边形和角的面积容易计算,总面积减去这两部分就是边部分的面积。如下图所示,红线围起来的部分即为可以覆盖三个正六边形的圆的圆心所在区域。(当然如果是在边界的话就不是了)总的大六边形减去小六边形再减去六个角部,就是可覆盖两个六边形的圆的圆心区域。然后把在外边界的情况处理一下就可以得到结果了。

f

G. I Wanna Go Home

对两种点分别求最短路,再枚举一下通过哪个边从某种点走到另一种边。

H. Repeater

简单题,递归写就可以。注意可能容易超时,实现上注意优化。

I.J.待续

[转载]掌声响起

http://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》的感觉,这就 是我对那些掌声的感受。