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

qus的博客

 
 
 

日志

 
 

华师校赛  

2010-04-12 00:17:41|  分类: ACM比赛 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今天,华师校赛,由于五校联谊,于是,有幸过去华师玩下。

由于,从大学城过去天河,时间还是挺赶的,我们还好去到那里还有15分钟开始,有些队最后时刻才到(估计是广工的,不过,不熟悉,反正,还是不知道谁是3XIAN)然后,还遇到高中的同学 星人、肥雄、梁锡雄(怎么这么多外号,其实还是一个人),顺便约他一起吃饭。

还有我们还是梁教主亲自带我们的啊,也看到些区域赛的老朋友。华农退役的PKKj还亲自过来找我呢,本来想让他指指谁是3XIAN,不过,貌似他也认不出。

我记得楼教主曾经在回忆录里面说过,现场赛是很多在网络上ID熟悉的人见面的机会。我也终于有点体会了。

比赛也推迟了10分钟开始。这里说说华师的机器布置,一列很长很有气氛,前面两个大屏幕,呵呵,感觉比华工的要好,不过,美中不足的是分开两个机房了~~还有,我们华工的全部一排,左面是耀满他们,右面是YANID他们,呵呵,真是直接沟通了~~气球没有藏起来,放在一旁,一眼望上去红色的F气球很多,冷冬直接把F题打开,说不过F不做其他题。然后比赛就开始了。

本来,我是从后面看起的,但是题目分到人手上的时候,就没有按照原计划看了~~因为题目很多都很熟悉。

首先是我准备翻到最后一页的时候,瞄到D的图片,很熟悉,跟POJ上的那个举行并周长很相似,于是看看,果然一模一样~~~

然后,跟他们说我可以直接上,然后找线段树的模板,但是冷冬质疑,一开始计算几何?我说是线段树呢。但是找不到模板,然后想起没带,因为之前几场都带了,没用上,而且感觉不会这么裸出的所以也就没带了,悲剧啊~~冷冬看到A说做到,我看看,废话肯定做过啦最长序列嘛,本来冷冬想直接上去敲的但是看看数据规模10W,哈哈,悲剧了吧,O(nlogn)的算法早就听说过,就是没有研究~~话说这个题目最后53提交0AC,我们压根就没开。

好吧,还是回到原来的套路看题,冷冬,执着的看F,我看到K,唉又是一个裸的凸包。看到旁边的游**,已经在疯狂的敲代码了~~

冷冬说F可以写了,我也感觉是水题,虽然,没看过但也就让他上去敲啦,我和飞铃继续看题目。

13分钟 F无意外的1A,由于我连题目都没看过,所以不知道算法~~冷冬补充

F:最小生成树(冷冬原话:我的是加了自环、重边判断、边权>=0的裸最小生成树)

然后,我上去敲凸包,话说,我凸包带了两个模板,我记得一个是用不了的,依稀记得第二个可以用,就先敲第二个模板,敲完,过不了样例,然后,冷冬说可以敲C。我先让他敲,然后,我比对下有没有敲错,发现没错,跟冷冬说,可以换一个模板。冷冬的C遇到细节,于是让给我写。我换用第一个模板的时候,看到排序函数,我就记得第二个模板要先排序的~~ 噢,不管了直接用第一个吧,肯定行,当我敲完的时候,顺利过了样例,提交就AC了,不过时间已经很慢了,已经是54分钟。(第一个出的是12分钟~~ YANID 他们)

K:裸的凸包,周长,很裸,很裸。

然后,我下来就着手写线段树了,没办法,没有现成的,只能手写。这时候冷冬的C和飞铃的J在并行写着。话说,冷冬的C很久都迟迟不行,我就问问他什么算法,他说是2SAT,还是让我看看那个模板是怎样用的,于是,我看看C的题目,提示说,用2sat来写比较不稳,用树状DP稳些,不过情况转移得比较复杂而已。飞铃的J写完交上去是WA。于是,先放下,因为D的矩形求并很稳,肯定可以出,大不了慢点。

写了多久忘记了,反正也和冷冬轮流用了下机器,飞铃直接看其他题目去。虽然大体算法很清晰,但是,某处变量的使用错误,让我调了很久,悲剧啊,时间就是这样浪费掉的呢~~138分钟的时候,1A

D:矩形并周长,很裸,很裸。

下来,飞铃已经把C的状态转移想好了,但说不熟悉树状DP的写法,于是,飞铃写出清晰的转移方程,我写。

冷冬开I,后缀数组的题目,说已经想好后续处理了,由于,当时,跟飞铃在讨论C,于是,没有像冷冬求证正确性,现在想想,这应该算是我们的一个比较大的失误吧。

在飞铃写C状态转移得同时,我看到右面两个黄色气球,我们没有的,是G,我看看,又是裸的最小割。再仔细地看了两遍题目,感觉真的很裸,于是,跟冷冬说,他下来,我上去敲最大流模板,也跟冷冬说了下G的题目,让他看下,冷冬也说没问题。我敲着敲着,跟冷冬说,不如,我敲完模板,就直接你写吧,反正图论你熟悉点。恩,好。我敲完模板,然后比对,冷冬敲主函数。下来,跟飞铃讨论。然后,看到软件那边很兴奋地过了E。于是,我跟飞铃开始讨论E,高次方程求根,基本想法递归求导,分区间二分。

冷冬204分钟过G,还是1A的。

G:十分裸的最小割,拆点,最大流。

然后,我上去敲C,飞铃手写E,冷冬继续想I。C的代码是很短很短的,直接一个DFS,毕竟,在飞铃指导下,把状态转移部分写完,顺利过了样例,222分钟顺利1A(今天人品很好,都是1A的,或者说样例很和谐,过了就基本过了,这里提下,这份题目虽然,原创性不足,但是,描述是很清晰的,恩,是很清晰的)。

C:给出一棵树,在某些点建电站,相怜的都能够供电,问最小建多少个。

下来,想了想B的类似离散对数,唉,怎么没打那个BABY STEP那个算法打印呢,至少有点参考嘛。又看了看A,虽然,有个O(nlogn)的算法模板,但是,没有用过,看不太懂,不懂怎样拓展到能够求数量。关于H的较难的计算几何,虽然,有个先确立一条边AB,然后移动C到可行位置,再通过伸缩变换和移动,应该能够比较艰难地出,不过,在还有其它把握更大的题目的时候,没有开的必要。

那边飞铃写E,和冷冬的I 在并行。飞铃经过一番调试,E过样例,交上去,也顺利1A(对于这种二分的题目,我是不敢写的,因为有过十分悲惨的经历,所以,我基本没看过代码)。

E:最高是5次方程,求根。我们的做法是递归求导降次,分区间二分。

其实,那个时候YANID他们也在写E,忽然顺航冒了句牛顿迭代法,然后,就对这个模板一顿敲,我不幸瞄到时浙大模板。于是,我拿起来我们的浙大模板看看,原来有个直接求跟的模板~~真是孤陋寡闻啊~~ 不过以后就知道了~~感谢顺航哥~~

然后,剩下来的时间不多了,冷冬说了个J的算法,让我想想怎样写,他继续调I。然后,我就产生个疑问,为什么之前飞铃直接用递推做J呢,起码要来个DFS吧~~然后她也感觉是~~囧~~

I到最后都,调不出,唉,对后缀数组的理解还是不够深啊。然后,我的J大体代码很短,最后,提交流,12次~~暴不了人品,后来,想想缺了个串联的可行性判断呢~~当时候,还纠结着会不会是除0的问题。

其实,J是我跟冷冬之前在做某国外现场赛的时候,碰过的,当时候是冷冬1A,然后,这次,他在开I与开J,之间选择了开I(毕竟I比J有挑战性,而且,他说他当时写的时候,很多补丁,感觉恶心不想写)。可能毕竟是来玩的心理占据上风吧。

这里说说J的算法,通过,不断组合并联然后串联直到剩下从S到T得一条路就行啦。复杂度,应该是没问题的。

最后,6个题目第5,其实,如果,多点积累的话,A应该是可以出的~~

这里YM下第一的华师08队伍(真是后浪将前浪拍死在沙滩上),第二的广工的GDUT_Poor(3xian啊3xian,还是认不出是谁,只是如雷贯耳),第三的华农的SCAU_APM1000(看来要问问PKKJ是什么来头,会不会是他的队友组的那个呢,估计是了),第4的耀满(最后8分钟,被他们绝杀~)。

最后,感谢下锡雄和伟好的饭和饮料,跟他们吹吹水还是挺不错的~~(我高中同学~~)

 

最最后附上,从燕描兄偷来的资料。

A题:问徐徐师兄
B题:问数论学家
C题:树状DP或者贪心,PKU 3659
D题:矩形周长并, PKU 1177
E题:题目有问题,公开道歉一下,牛顿迭代或者二分都可以做
F题:判断是否连通,然后最小生成树
G题:判断s和t是否连通,最小点割集(拆点最大流)
H题:梅内劳斯定理+定比分点
I题:问徐徐师兄
J题:基尔霍夫节电电流定律+高斯消元法
K题:凸包原题...不要问

 

然后,知道,我们过不到的题目,其实是真的不懂~~还以为,差一点点,一点点~~(ym下XUXU师兄)

C题:补充贪心做法,如果一个点它没有取,而且它的儿子和父亲都没有被取,那么就取它的父亲。(先叶子再根的次序处理),来自POJ的discuss

ACM字典:YM 仰慕!!用于膜拜大牛~~

 

  评论这张
 
阅读(370)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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