Monthly Archives: November 2008

22岁

呃……可以结婚了……话说我的小学同学都有快当爸爸的了,差距啊……晚上买了个大饼鸡蛋庆祝一下……低调,低调

爱的想象——摘自《三体II:星暗森林》

“你可能需要一些调整,但没什么大事。”听完罗辑的漫长叙述后,医生对他说。

“没什么大事?”罗辑瞪大了满是血丝的双眼,“我疯狂地爱上了自己构思的小说中的一个虚构人物,和她一起生活,同她出游,甚至于就要因她和自己真实的女朋友分手了,你还说没什么大事?”

医生宽容地笑笑。

“你知道吗?我把自己最深的爱给了一个幻影!”

“你是不是以为,别人所爱的对象都是真实存在的?”

“这有什么疑问吗?”

“不是的,大部分人的爱情对象也只是存在于自己的想象之中。他们所爱的并不是现实中的她(他),而只是想象中的她(他),现实中的她(他)只是他们创造梦中情人的一个模板,他们迟早会发现梦中情人与模板之间的差异,如果适应这种差异他们就会走到一起,无法适应就分开,就这么简单。你与大多数人的区别在于:你不需要模板。”

“这难道不是一种病态?”

“只是像你的女朋友所指出的那样,你有很高的文学天赋,如果把这种天赋称为病态也可以。”

“可想象力达到这种程度也太过分了吧?”

“想象力没有什么过分的,特别是对爱的想象。”

合肥之行 – Day3

这次只写比赛,比较扯淡的东西以后再补。先简单列一下题目,这里列的只是当场的想法:

A. 我没看题,被lx秒杀了

B. 也没看题=,=,好像是离散对数,但是是经典问题的加强版。据说有结论,我们不会做

C. 图论,利用求割边的那些东西

D. 图论,利用强连通分量缩点和传递闭包

E. dp,要用线段树优化,时限比较卡,我超时到最后

F. 一个特殊图(区间图加强版?)的最大团,不会做

G. 二分+Farey序列

H. 计算几何的计数题,不会做,只会暴力,超时到最后

比赛开始后,仍然按照惯例,lx从前往后,mdz从后往前,我从中间开始。读了D题,有一些大致的思路,但也有一些地方想不好如何处理,感觉不是马上能做,lx读了A说能做,就上去写了。mdz跟我说H暴力的话复杂度是10^8量级,或许能水过。然后跟我说了F,然后我就直接走上了不归路……没仔细想就以为是区间图的最大团了,这时候正好lx把A题1y了,然后我就开始翻出区间图求PEO的那些东西来搞,但是我那个模板只是判断弦图的,关于最大团问题的具体结论我已经记不大清了,当时很后悔没有带一本图论书来。猜了两种结论,都WA掉了。这时候已经耽误了不少时间,当时虽然是把这题放弃了,但还是一直留着一个幻想以为过一会儿我就能把结论想起来。这时候旁边WHU已经过了C,lx也正好想了一个C的算法,在我改F的时候交替着上机把C写完了,但也是WA,后来又改了个小错还是WA。然后我就一边依依不舍地yy着F,一边给lx查错,结果听lx讲完算法后发现他的想法基本不靠谱=,=,马上被我举出反例了……他说当时跟mdz商量了一下,mdz说感觉是对的于是就上了=,=,看来一上场大家的感觉都不大准啊……然后我们讨论出了利用双连通分量的方法,感觉是没什么问题了,我就上去重写C,结果写完又WA……崩溃……同时mdz在写H的暴力,不知道他后来交了没有,然后又来帮我们想C和D,这段时间我们做得有点混乱,大家也都有点着急,这就是中期之前我们出了一题就囧住了的原因。

还好C题我的算法框架还是没有问题的,不久发现了一个小错,这时候我又急躁了,直接改完就再交。然后又WA……奔向厕所,然后突然想到还有一个小错,回到座位发现lx也发现了那个错误,改之再交,终于在150min,两人写了两份代码,5次提交之后得到了第二个Yes。这时候我才突然反应过来F题因为时间区间可以跨过零点,所以不是一个真正的区间图,那么可能要对经典模型进行修改才行,不过我连经典模型都忘记怎么证的了=,=,于是直到这时才真正把F放弃。这时mdz提出了D题的解决方法,我感觉前期心情有点太急了,于是有意求稳了一下,这题我俩讨论了较长的时间,把所有细节都分析清楚了,然后我才开始上机,同时让mdz出数据。与此同时lx也基本想出了G题的做法,但他那题有点不太好写,我在他下机规划的空隙把D完成了,mdz出的数据也直接全部通过,然后直接提交1y。几分钟之后lx的G题也改对了,又一个1y。感觉这两道题我们是完成得比较好的。

这时候还有大概100分钟,我们4题排第二,但第一名很快做出了第6题,而且他们过的几题我们都没有好的思路,当时就感觉压力很大了。这时候场上过得稍多的是E,很明显是一个需要优化的dp,但这题一开始他们两个都不愿去想,这种优化dp也一直是我们队的薄弱环节,我又一直在和自己的弱智错误搏斗,所以直到这时候我才有时间开始想这题。同时lx想B,mdz继续对H加一些常数优化,不过B和H我都没有好的想法。写E题的时候我又有点着急,一开始转移方程没想好,后来线段树的实现还出了好几个小错,直到结束前半个多小时才过了Sample,结果交上去却TLE了。从数据规模上分析这题的时限确实很卡,复杂度是O(MNlogN),M=100,N=10000,但因为过的队比较多我就硬上线段树了,没想到真的会TLE。后来又加了些常数优化,但还是TLE。最后lx说了一个O(MN)的算法,但被我反驳掉了,我也试图想过O(MN)的算法,但总是感觉想不好。后来问WHU他们就是用O(MNlogN)过掉的,这几天我要好好检查一下我的线段树为什么那么慢了……另一边mdz的H也在TLE中。lx的B本来还有些不太确定的想法,也没时间写了。比赛就这样很囧的结束。

从总体上来说,我们确实没有完全发挥出来,但也并不能算是做得很烂。如果我最后的E能过,那么我感觉我们就已经几乎做到最好,没有什么遗憾了。冠军那支队表现出的确实是超越我们之上的实力,我们输得心服口服,这样水平的队伍也确实足够有资格进入Final。虽然不计名次,我知道大家都有点YY能拿个冠军,不是我们没尽力,只是对手太强大啊……虽然我这么说有点推卸责任,呵呵……

当然这次比赛也暴露出了我们队的很多问题,前期我太早地把时间浪费在一道没有把握的题上,而且因为我在敲F导致lx不能把C题与我进行讨论,得出了错误的算法,然后又因为我着急把C题赶回来而出了一堆小错,浪费了大量的时间。如果我们前两题的速度能够跟上当时的第一梯队的话,后面的E可能也就不会没时间仔细优化了。这一系列的连锁反应都是由于我的草率造成,这个我要检讨一下。还有就是冠军队诡异的过题顺序确实对我们造成了一定的影响,这次比赛的8个题我们都没有轻易放弃,每道题都有某人或某两人想过不短的时间,甚至对于没把握的题都完成了代码,只因为已经有人过了就想水一下而已。所以赛后lx一直纳闷怎么感觉时间过那么快。如果能尽早集中火力的话或许结果会好一些。两个队友的表现都比我好得多,mdz想出了D的正确方法,lx单枪匹马干掉了G,相当的赞。我自己则是先跳了一个到最后也没人过的F坑,还没爬出来又让C坑拌了好几个跟头,最后终于挂在E坑里了。囧……

好了就写这么多了。我代表全队给大家道个歉,希望大家能认为我们还不算太给TJU丢人,请期待Neptune在后面赛区的表现。

ps. 最后要赞一下Zing,最后一分钟搞定D题。可惜还是rp差了一点,没有银牌。在杭州爆发吧,哈哈。

合肥之行 – Day1

晚上十一点多的火车,到车站的时候就发生了一件囧事,出租车师傅手快,到站就把计价器按零了,然后小票就打不出来了 =,= 在火车上又发生一件囧事,就是我们上去之后发现有两个位置已经有人占了。把乘务员叫来仔细查验以后发现是他们把时间弄错,应该是13号,买成了18号的票,然后检票什么的都没发现……我们是半路上车,当时车上就已经熄灯了,望着窗外发了会儿呆就睡了。貌似睡得不太好,不是因为情绪紧张,是因为我白天睡多了 =,=

到了合肥,发现和印象中的石家庄(不过石家庄我已经很久没有去过了)很有几分神似,都是那种很破败的省会城市的样子。不过中科大的校园还是相当不错的。合肥比天津要热五六度,在街上走了一路就感觉有点热了,有点后悔衣服穿多了。吃完饭去一个叫“包公园”的地方玩,里面有包公的祠堂、蜡像、遗迹之类的,还不错。比较囧的是景点的英文名叫Lord Bao Park,我一直在想对ACMer来说是不是应该翻译成“包教主的公园”?@_@

回学校的时候又囧了,我们是在六点多钟的时候打算打车回来,结果就发现出租车根本不鸟我们。有很多明明是空车,但就不亮那个红灯,招手也不停。后来好不容易拦了俩车,师傅说是因为他们都是七点交接班,所以都不拉活了……囧,但那正好是下班高峰期啊……

回到科大的时候碰到一队人,其中一人喊我“萝卜”,不过天比较黑,没认出来是谁,汗

然后还有一个囧事是说因为我们是特邀队,所以没有衣服,但我们报名费可没少交啊,这个可真是有点郁闷了,这个问题正在交涉中。

晚上玩了会儿杀人,扯了会儿淡,就到现在了。今天就这么多事了,明天教练会和热身赛,加油。:)

一道有意思的平面几何题

来自于一道ACM题: Ural 1659 Regular Triangles

给定一个正三角形,现在要求出六个点,三个在原三角形内(严格在内,不允许在原三角形的边上),另三个在原三角形外(同样,要求严格在外),使得这六个点与原三角形的三个点之间可以组成九个正三角形(含原有的一个)。

答案见图:

 

Triangles

Triangles

 

 

其中三角形内的三个点是选在三条角平分线距顶点的1/3长度处,而问题的关键在于那两种不同色的三角形在形外的那个顶点是否重合。答案是肯定的,但我还没有找到一个非解析几何的证明。