随笔 - 4  文章 - 46  trackbacks - 0
<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

常用链接

留言簿(4)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

7月2日 热身赛
热身赛2个小时,我们不太适应比赛的环境,最后只做了6题。其中有几道复旦校赛的题真是有点意外。我不习惯用裸的vim,moonlight131建议我用eclipse c++,我试了一下感觉不错。由于感觉状态不好,我们没有参加fortress的游览,早早回宾馆睡觉了。

7月3日 正式赛
开场之后,我来配置环境。几分钟后moonlight131说C可以做,于是他上来敲C。我从后往前看,发现J就是圆和多边形交,翻了一下模板正好有,但是怀疑那个是求凸包和圆的,就问了下moonlight131,他说模板肯定是凸包的,此题不可能那么裸,于是先放。然后他刷了下board,跟我说F有人过了,于是我赶紧看F。读了几遍题后我确定了F的做法,就在纸上写好了程序。这时大概过了30多分钟,他写完了C但是觉得方法有问题,而且C还没人过,而F已经过了好几十了,就让我先敲F。我把纸上的程序敲上去,F过(46min 1Y)。然后一起看board,D过的人略多,于是开始攻D。moonlight131提出了一个dp的做法,但是我们感觉有点复杂,因为itmo很早就过了此题,但是也想不出更好的方法。他上去写D。我看了下A题,暂时不会,然后看了下H,应该是区间dp,但是样例没有推出,就让yangzx看H。moonlight131的D写好了,提交wa。然后我们一起找数据,小数据都没问题,这样的话算法是不会错了,问题出在边界上。yangzx提出打印出1~100的结果,然后查了一下发现错误出在62上,改后D题ac(114min, 4Y)。写D题是一个艰难的阶段,虽然此时rank很靠后,但是过了此题我们信心大增。我提议尝试一下J的模板,因为最后求的是有向面积,那么凹多边形也没问题,就上去敲。yangzx说了H的题意,moonlight131认为此题好做。J题敲完后不过样例,打印出来对模板,moonlight131上去敲H。找到J题敲错的地方后,我想等他先写完H,没有马上上去改。然后我看A题过了很多队了,就重新想了下,发现因为有“翻转”这个条件,那么方向就无所谓了,只要暴力找循环节即可。于是我在纸上写了A的程序,去趟wc。之后moonlight131写完了H,数组越界RE了一次,改完之后H过(170min, 2Y)。然后我把J敲错的地方改了,抱着尝试的心态提交,竟然过了(173min, 1Y),先不着急庆祝,赶紧把A题的程序敲上去,稍微改了下后A过(188min, 1Y)。这样就在20分钟内连过3题到了5题。我想应该能拿到名次了吧。这时剩下可以做的只有C了,moonlight131看到只有单组数据,决定用暴力做最大流的方法试一下,于是他上去把原来的程序敲完,神勇的AC了(210min, 1Y)。这时刷下board我们已经第10了。但是罚时很高,感觉拿牌是没希望的。此时还剩下一个多小时,但是其余的题都只有个位数ac,超出我们能力范围。moonlight131决定试一下B,我看了下别的题觉得没思路。最后B题接近了样例,封板后用暴力的程序提交了2次,但是离ac还比较遥远。
最后我们取得了rank17(icpc 14)的成绩,已经远远超过了我们的预期。后来很多国内的队伍都来恭喜我们,但实话说这次只是运气好而已,论实力我们是排在他们后面的。也许是飞机延误攒的rp,这次的运气确实有些不可思议,比如说在赛前我为了控制页数,把圆和多边形交这种不常用的模板删了,而临走之前moonlight131改了缩进,把这个模板又加上去,才让我们过了J题;比如说当时我给他讲了A题后,他不知为何的说了句“方向什么的都无所谓”,我后来才想到做法;比如yangzx在他写H的时候指明了题意,使H接下来的写法豁然开朗... 当然也有略遗憾的地方,如果罚时少100分钟,我们就有机会拿牌了。赛前我一直说拿牌的几率是0%的,也一直跟moonlight131说开场就暴力提交吧,结果在5题之后我们才开始考虑罚时。但这一切似乎都早已注定,没有开始就没有然后了,所以我们只是感到幸运,并不感到遗憾。

最终ranklist http://board.acmicpc.info/icpc2013/board.php
posted @ 2013-07-08 23:31 vici 阅读(727) | 评论 (0)编辑 收藏
2. 6月30日~7月1日
到俄罗斯后,一切的背运都逆转过来了。在30号的中午我们到达了目的地Renaissance宾馆,而殷老师和王老师也幸运的改签到最后2张票,随我们之后到达。
之后我们就按照ibm的安排,不想错过每一个环节,只想尽情呼吸圣彼得堡的空气,享受这趟finals之旅。


Renaissance宾馆


晚餐/娱乐的地方


6.30 注册


6.30 欢迎晚宴


7.1 IBM讲座


7.1 午宴


7.1 开幕式


晚餐


IBM chill zone


7月1日晚 冬宫广场


冬宫博物馆
posted @ 2013-07-08 23:20 vici 阅读(476) | 评论 (0)编辑 收藏
1. 航班危机
6月28日下午4点,我们从学校出发去机场。除了我们三人,同行的还有殷老师、王老师和孙老师。我们取到票,过安检后,发现我们的航班延误了2个小时,当时并没有担心,因为从北京飞莫斯科的飞机是半夜2点的。等到7点我们上了飞机,在飞机上坐了很久也未见起飞,结果机长通告说由于北京天气原因不能起飞,让我们下飞机等。于是在9点左右我们又回到了航站楼里,这时才意识到事态的严重性。我听到老师们谈论退票退宾馆的事,又听到moonlight131问“难道去不了了?”,殷老师答“那还去什么了”。顿时心里凉了半截。我们在一年时间里花费全部心力准备的finals,最后就等来了这样的结果?我不相信。
王老师打电话和北京方面联系,得知了一个消息:如果北京飞莫斯科的飞机也延误了,那么我们就能得到免费的改签,否则改签要每人1w7,学校是不会出的。我们只好祈祷那趟航班也延误。而比起北京的大雨,这边的航站楼里也不平静,许多乘客与东航的工作人员大吵起来,但终究徒劳,只是让我们感觉希望更渺茫了。
等到了将近12点,突然听到一阵欢呼,我们的飞机可以起飞了。但也许这对我们并不是好消息,因为这代表着北京天气已经好转了,那架飞莫斯科的航班很可能不会延误,而以现在的时间来看我们很难赶上那架飞机了。但无论如何,先去北京再说。
凌晨2点钟我们到了北京,在机场我们拼命的奔跑,但是过了海关到了俄航的窗口前时,人们都已上了飞机,这趟航班并没有延误。我们终究还是晚了一步,要是能早来十分钟就好了,因为这十分钟,我们要多付出上万的改签费用。但钱并不是最严重的问题,最严重的问题是我们很可能有钱也买不到票了。
我们遇到了最坏的情况,简直是老天在和我们作对!但我仍然不相信,难道命运就把我们拦在这里了么?千山万水都已走过,却要在最后一步卡住?这种结果怎么可以接受?
我们不能回头,我们要继续前进,没有任何事情能阻止我们去finals,除了坠机。
老师们决定找其他航空公司买票,那几个小时里我们就奔波在几家航空公司门前,最后在中航买到了4张去莫斯科的,但是没有返程。我们的签证只到7月5号,如果不能按时回来我们就是非法滞留,所以我们是不能乘这趟航班的。于是决定到上午再等消息。
我在椅子上睡到上午9点左右,老师叫醒我,原来是俄航的改签有了些进展。于是我们又过了海关去俄航台前等待,那里有很多人。等了一个小时候人们皆散去,原来是已经没有空位!而俄航的人晚上才会再来,到时候重新排号,能否等到位置完全是未知数。最后我们问那个工作人员的时候,那个人很粗鲁的回了句“晚上的事跟我无关”,我们失落的离去。(后记:真要感谢那个工作人员,如果她态度好点的话,我们在这等下去就完蛋了)
于是我们到了最关键的时刻,孙老师指出了两条路:1.坐下午1:30的飞机去莫斯科,但前提是要买到返程票,如果没有票那么也不能走。2.在这里等晚上的票。在这里等下去显然是希望渺茫,但坐下午的飞机需要很高的费用,学校可能不同意出钱,殷老师问我们自己花几万怎么样。而我的想法很简单,我不想追究航空公司的责任,也不在乎花多少钱,我只想去finals。实际上这件事根本不需要商量,因为几万块钱而放弃finals梦想真是会沦为笑柄。所以我当下就说钱不是问题,我家里肯定有。事实上我根本没和家里联系,我也不需要联系,因为我有绝对的信心我家人会帮我出钱。问题在于他们两个怎么想。

时间真是紧迫,如果再不回去买票可能就没有返程票了。我心急如焚,而moonlight131却在犹豫,他说他有点不想去了。我很吃惊,关键时刻你为什么这么迷茫!正想说“你们没钱的话我来垫上”的时候,殷老师替我们做了决定,带我们去买票。
万幸的是,我们买到了返程的票。于是我们三个队员,以及孙老师,先行一步踏上了去俄罗斯的行程。而殷老师和王老师为了保全我们牺牲了自己,留在了北京机场,另觅它途。
下午的飞机又晚点了,但只是坏运气的强弩之末,我们在6点左右终于踏上了去finals的征程。坐上飞机,想到这趟行程的不易。又想到殷老师和王老师两天来为我们奔波劳碌,最后却把自己留了下来,感动万分,一时间泪如泉涌。
posted @ 2013-07-08 23:12 vici 阅读(507) | 评论 (1)编辑 收藏
     摘要: 前言: 这篇文章发表于http://e-maxx.ru/algo/inclusion_exclusion_principle,原文是俄语的。由于文章确实很实用,而且鉴于国内俄文资料翻译的匮乏,我下决心将其翻译之。由于俄语对我来说如同乱码,而用Google直接翻译中文的话又变得面目全非,所以只能先用Google翻译成英语,再反复读,慢慢理解英语的意思,实在是弄得我头昏脑胀。因此在理解文章意...  阅读全文
posted @ 2011-09-05 07:10 vici 阅读(16267) | 评论 (14)编辑 收藏
仅列出标题