注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

qus的博客

 
 
 

日志

 
 

挑战赛、省赛GDCPC2010  

2010-05-09 23:11:47|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

这年省赛阿里巴巴赞助,他们为了测试他们的云计算服务器,特别举办了个挑战赛。

游戏是挺有趣的,就是用他们的库函数写个AI,控制自己的小车然后检地上的物品,然后回家得分。由于奖品非常丰富,包括手机,耳机,鼠标等。其中,最吸引我的是二等奖的PSP2000。实在牛B的奖品啊!!

我们大概制定了一个写底层导向小车,一个下上层寻找策略。不过,代码量还是挺大的。而且,我们写得很晚,在底层写完,就没有时间上平台调试了,只剩下第二阶段的2个半小时。不过,由于服务器的调试巨慢,巨难,而且,不知道为什么不能输出(前天试平台的时候,还可以的)。最后,悲剧地调试了2个小时底层。而且,是由于重命名问题,而不是代码问题。然后,没时间调上层。最后,决定上来直接回家,那个时候还是有分数的。但是104回合就跑完了。于是,最后决定随即跑150回合,再回家。由于,服务器过于慢,还没有看到运行结果,平台就关闭了。冷冬说,好吧,就当是留个悬念,看看能不能够回家。

然后,晚宴,自助餐还是相当丰富的,薯条,鱼,虾什么的都有。然后,他们放对抗赛录像(怎么这么多废话啊..省略前面N场),然后到我们队,由于,前面不少0分过关的,我们还是蛮有信心的。但是悲剧的是,其它两个队,都有车回家,虽然,分不多。但是我们有4辆小车,自己卡自己,在晃动,当时还引起全场的掌声呢.......

最后,首轮淘汰....(之后看录像,有个0分的一直晋级到18,我顶,什么人品,诅咒着队伍明天卡3个题目以上)

 

困啊,不想写太多,直接上省赛吧。(王师兄,上次还问我为什么你去珠海玩,都不写个日志啊,好歹,看看战况嘛。其实,是因为我懒....而且,打酱油的教练视角没什么好记录的......)

比赛前,按照惯例,研究气球颜色,寻找水题。发现A题的气球竟然是比赛服的橙色,然后,我说,为了让全场都挂上阿里巴巴颜色的橙色,A题肯定最水的,冷冬也表示同意。

开始比赛,tothemax布置环境

(这里大概提一下,我们队布置环境的风格,给一些师弟参考下。牛们跳过。首先,是头文件写齐全,包括字符串,几何,队列等。但是注意map这个头文件,如果包括进去了,全局就不能有map参数。然后,是主函数+文件流输入。外面,搞A到I的CPP,和A到I的输入文件。其实,很多队伍都不在乎这点时间。这大概是一个习惯吧。)

feeling和我看题。我先看到H的字符串匹配,然后,看到E的矩形找数,很容易找到一个朴素的枚举行+二分的算法。不过,大概估计了算法复杂度,时间挺紧。没说,再找题看。然后,feeling说A可以写了,跟我讨论下,tothemax开始敲了。

A:问N的立方体,能放多少个M的小立方体 6分钟A

tothemax交了之后,发现,没有return 0;于是,再补了句return 0;又交了一次。幸好,没有return 0;还是A了...不过也大概,预示着,我们今天的水B错误会比较多...

刷board,看到B很多队伍过,feeling开始做,我看到有人挂上K的气球,于是,我做K。

B:组合数学,一个公式加上二分的题目 63分钟A

不过,过程非常不顺利,又一个WA,等过了的时候,在board上完全消失了。

然后,是我的K,题目很长,不过难题不大。一个基本的打地鼠问题,数据很小,没悬念的直接模拟。

k 模拟+DP吧 86分钟A

不过,过程仍然是不顺利,第一个WA回来,感觉某个地方的循环上界不够大,改了再交,第二次WA回来,在打印的代码上终于找到,WA的原因,输出结果没赋初值...3A这么水的K,使我们本来就出得慢的罚时,更是雪上加霜。

前期大概结束了。我们队一向慢热,从水A到B,中间隔了一个小时,浪费了大量时间,还各种罚时。这大概暗示着,我们可以提交流了..

tothemax实现完C之后,一次出样例,做完最后检查,例如,数组大小,边界等情况后上交。他说,这个题很稳。但还是没有1A,返回的RTE,只能够说,实在是水B。后来,feeling说,她当时就问100个点够不够,tothemax很稳地说够....

C 题目是容器装物品 算法是二分+最大流判定  103分钟A

这个题目涉及到网络流,在以往的话,应该算是还有点难度的题目,但在ACM在各个学校疯狂流行的时代,这只能算法个中等的题目了

然后,刷board看到除了我们的4个题,有E I H有人过。于是,我们在考虑E的朴素算法的时间紧迫问题,然后刷board看到10个队都过E,唉,那肯定都是水过的。但是敲完上交,wa,打印,查代码,再WA。最后,发现是我读题的问题,然后改了二分那里就水过了。

E 大矩阵中有变化操作的寻在数字位置 163分钟A

算法变化是O(1)的,查询最坏是N(logn)。显然,没有最坏情况。其实,这个题目,我们讨论了很久,也查错查了很久,导致时间的大量浪费。也为最后G的流产留下伏笔。

然后,剩下I J 可以选,I,我是完全投降没有想法。不过J的话,tothemax说,他直觉是一个排序+DP,于是直接上去敲了。

代码短很快,过了样例。想水过的交。方法1排序返回WA。然后,改方法2排序,还是WA。我就感觉不能水了。于是,写个公式,拆开看看,告诉正确的排序方法。成功AC

I 根据某个计算方法,求20个数的排列方法,使值最大

框架可以直觉出是排序+dp,排序方法,认真的拆解下就不难发现。这种类型的题目,我以前见过,不过,直到tothemax开始敲得时候,我才知道这个题目。如果,我早点知道的话,我是决定能够很快就出,起码能够拯救下,我们可怕的罚时。

剩下G跟H。这两个最后意思的题目,虽然,我们最好还是过不了,不过,我感到这两个题出得很好。

先说说G,我从他们敲J的时候,我就开始注意G应该有机会出。

G是一个无向图,从起点到终点,必须经过某些点跟边,问最小时间多少。

我注意到必经点才10个,必经边才5个。先是想到将边转化成点,想了个满状态达到100W以上的DP,然后想了个所点优化,不过时间复杂度还是非常巨大。跟feeling交流下后,她提出个1000*32*100的满状态DP。于是,我感觉可以写了,那时刚好过J。我直接上去开敲。tothemax不解,跟feeling讨论起来。话说,我本来是准备单纯DP的,然后,写完输入后,想怎么写DP的时候,考虑按什么顺序DP,于是想到了搜,然后,再想到了,优先队列来保证时间最小性。

那时,我问tothemax怎么拼写有限队列的单词。这个时候,他们讨论进入了白热化,因为,他们各自提出的算法都有巨大的缺陷。tothemax打断我敲代码,要求我交待清楚算法,等我把想法都表达清楚的时候,他们都一致赞同,肯定是对的,只能TLE,不能WA。

在我敲完,之后。feeling开始水H,其实,H水过的希望不太大,毕竟过的人很少。

在修正了G若干个BUG之后,首先是返回RTE,然后,改了个上界,终于看到想象中的TLE。在剩下10分钟的时候,我忽然想起,我那个缩点的优化,能够将时间复杂度缩小5倍,一个巨大的优化。不过,我知道这个优化需要标记点,N^3的最短路,10分钟时间,很难出来。如果,能有大概30分钟左右,就应该可以出来了。

这里说下总体的算法流程

1.将100个点的原图,缩成,只保留10个必经点,和5条必经路径的两个点,加上起点终点,最多22个点的图。

这里用到100^3的最短路缩。复杂度没问题。

2用优先队列搜索,状态DP

DP数组[10个必经点的二进制保存数][5条必经边的二进制保存数0][22个尾点]总共是2^10*2^5*22个满状态,总共72W个状态,每个状态是22的转移,总复杂度1400W左右,应该可行

最后的结果就是DP[全1][全1][结束点]

最后,没能过这个题,只能说我的责任,本来这个优化,在很早之前就确定了,用来优化100W那个初始状态。不过后来feeling提出的优化状态,让我兴奋到把这个优化给忘了。

再说说H,H原题是一个十分裸的AC自动机,但是100W的字符个数。让我自己瞬间否定自己两次,tothemax一次AC自动机的想法。

其实,最后正确的做法,就是AC自动机。而那个100W,只需要用MAP优化下就可以了...

G,我们想到了关键的地方,和关键的优化,但是最后还是出不来,是有不少遗憾。

H,被自己的定势思维给直接搞死,也只能回家默哀

按照惯例,日志最后要YM下前面的队伍,不过,还未 收到确切的分数榜,就大概YM下吧,YM梁教主牛,YM耀满牛,YM中大FINAL队(合肥坐我们旁边的....)

 

 

  评论这张
 
阅读(196)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017