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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

TCO2013 Round1 B  

2013-03-03 11:15:22|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天早上总算没有睡过头,我按时地起了床,高兴地参加了比赛。
br也参加了,却没有开黑,也没进行什么交流,原因只有一个,题目实在是太水太水了所没有想到的是这场比赛竟然还算rating,所以就可以尽情地虐div2的选手了,好丧失的感觉。
我们房里除了我和一个rating比我稍稍高一点的选手是黄名以外,其它的都是五颜六色,从灰色到蓝色应有尽有。其中有几个还是中国的,于是很不人道地用中文在上面聊天。
开始比赛,点开第一题,要求将n个人两两配对,每个人一个权值,使得权值和最大的和最小的两个组权值和之差最小。我最先还理解错了题意,不过并没有照成多大的影响,将所有数排个序,贪心地首尾配对即可。证明不会,似乎是个很久以前就知道的结论了。
做完之后发现时241+,房间里已经有几个人交题了,感觉压力巨大。
废话少说,在QQ上聊了几句之后就点开了500pt的题目:
n*m的网格,有些格子里面有黑点,你每次可以将连续R行的所有黑点或连续C列的黑点消掉。求最小操作数。
看到这道题的时候吓了一跳,不会做求破,但是一看数据范围,n,m<=15。这尼玛也太小了吧。暴力枚举用行来消除消掉了哪些行。于是就成了经典问题:用最少的长度为L的线段覆盖区间上所有点,贪心即可。
等我做完500pt的题目的时候我已经是房间rank1了,其它已经有人点开了500分的题目,但是却没写完吧。
兴高采烈地点开了1000pt:
对于一个字符串,你可以将前偶数个字符颠倒过来。现在有n个字符串,你每次可以消除相同的两个字符串,求最后剩下最少的字符串数。
开始我还想了一会,很明显变化是可逆的,那么就只要将每个串变为其最小表示,然后比对,将相同的串两两消除即可。
但是怎么变呢?自己手画了一下,发现相邻的奇数项和偶数项永远相邻,而且位置可以任意对调——将以这个偶数项结尾的前缀颠倒,这两个就到了前面,于是可以对换这两个然后复原,于是将这两个合并。发现剩下的就是可以颠倒前缀,将其排序,很简单吧,每次将最大的换到最前面,然后换到最后面,去掉就行了。
于是就很简单的水掉了。。。这次1000pt的题目比上次还要简单。
此时比赛大概还剩下45分钟。
接下来就是仔细检查程序,但是硬是没法发现错误,代码实在太短了,想写错也难。
等啊等,最后我去李毅吧逛了逛。。。
br做的似乎不是很顺,500pt的题目似乎卡了一会,1000pt的题目代码写了蛮久,不过最终也无压力地三题全切了,跪拜。
到了challenge时间,平常我都是无所事事的,但是想到我room rank1的身份来之不易,于是努力地去看了看别人的程序——不过此时一些人第一题已经被hack了。第二题发现很多人的代码竟然挺长的,明明很好写的。而第三题则是各种喜闻乐见——还真有人认真地写了匈牙利来找匹配,而且我发现了一个骗分的,将所有字母个数统计出来然后用些奇葩方法搞一搞,竟然样例都过了。我无情地将其hack了。
不久challenge结束,开始系统测评
一般而言系统测评是各种奇葩的,几乎排名要改变1/3。
这次也差不多,开始我rank35,后来随着system test,排名逐步提升,慢慢稳定在rank 20。房间也顺利地rank1了,似乎第二题和第三题都有人FST了。
于是我顺利地结束了我TC三连跌的历史,成功地涨了很多很多rating。。。。。。
(昨天去看电影,王怀新邀请了一个和他关系很尴尬的妹子,真心是bfm级别的,然后听说两人关系很微妙,因为那个妹子在追他!有木有啊!而且王怀新没同意——他自认为他已经有别的妹子了。。。。。。gfs的生活果然不是我等屌丝可以想象的)
  评论这张
 
阅读(108)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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