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

qus的博客

 
 
 

日志

 
 

校赛  

2010-03-28 20:58:52|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今天校赛,打得很郁闷,也很喜剧。个人很郁闷,代码很烂,状态不好,几乎导致队伍失败。幸好Feeling RP爆发,力挽狂澜。

赛前,我们3个在那里东扯西扯的。甚至说如果跌出前6就直接退役,找实习去了。然后去吃了点东西。

废话不多说了。

比赛开始,好吧,开始看题,我从后面看起,Feeling从前面,tothemax中间。

当时的想法是通过N的情况推出N+1,不过在比赛初期,不应该直接搞这题。

于是继续看,然后tothemax看到了E

然后tothemax说先打个素数表,然后再质数分解就可以了。然后,我想了想说,可以直接筛。当时,以为tothemax听明白了。然后他上去敲。等他敲完了,我一看,晕,再跟他说可以直接筛,然后演示了一次,终于明白了。

然后,改完就交了,下来WA。再试几个数据,发现被覆盖了,什么东西,这水B错误都有。再改,交,YES。

然后,我跟冷冻说了I。恩可以做,然后,冷冻跟我说了个直线的DP,问怎么处理环,然后,我就说可以用N-1的补上。

E题:求n的最小质数。

刷刷榜,1题最后,晕。

然后,i看榜首G有人过了。开始看G,很现,不水很难很难,然后跟tothemax说,他说水,说了个做法,叫我再想想。然后,我就根本听不懂,于是再想想。

憋了很久,发现已经有人3题了,过的是A。

恩,于是叫Feeling看A,是斐波那契数列的题目,然后,我想起那个公式,于是直接给Feeling看。然后,Feeling想A。

终于,tothemax想好了I,敲了I,WA,再打了些补丁就过了。话说,我现在都不懂,补丁了什么。

I题:给一个N+1个点的图,0到N-1个点是一个环,标号N的点和所有点都有一条边,问总共有多少颗生成树。

再刷榜,2题最后。

然后,我叫tothemax敲G。但是,敲着敲着就发现不行了,原来他理解错题意了。我就觉得没那么简单吧~

Feeling搞A没果,问我G。跟她说了下。然后,就问怎么样例还有-1这么变态,明明题目都说>=1了,然后,我想起刚开始的时候,改了题目,于是,赶紧找裁判问了下,唉呀。改了后,就是一个水了。

G题,N个格子,每个格子有个分数,K中跳法,问最大获得的分数。

经典的DP,Feeling就上去敲了。

我跟冷冻憋A。

G无悬念过了。

再刷榜,3题最后。

已经有人5题了。过的是B,跟A。tothemax继续憋A,我跟Feeling开B。Feeling说直接DIJ()改小小。我想想,感觉可以让她敲。我开F。B交上去WA了,再修改了几处,还是WA。此时,我们的罚时已经可以让我们无限提交了。B先放下。然后我跟tothemax说了个快速幂矩阵求Fi(N)的算法,看能不能启发他。其实,A题的N那么大,肯定是快速幂做的,关键就是怎么递推,我就跟他们说,只有递推出来,我肯定可以写。然后,我的F已经有很明确的算法了,然后想起铁路那道的剪枝,感觉肯定可以出。然后,看到有人过B了。我忽然想起DIJ改造的BUG ,让Feeling转用SPFA来实现。

B题,无向图,问从起点到终点的奇数最短边,和偶数最短边。

再刷榜,4题最后。

然后我开始敲F,想不到,我最大的悲剧开始了。先是敲完,然后,过样例,交TLE,然后改叫WA,然后~~~循环了几次,感觉已经把可以优化的都优化掉了。tothemax也帮我在看,也感觉不可能有问题。于是,在一些很无聊的地方纠结,有没有错,可不可能越界。然后,Feeling推出了A的矩阵。于是,我感觉验证了下了,没问题,上去敲了。

A题,求Fi(n)*Fi(n)的前N项和。

关键是构造矩阵。快速幂矩阵,很快敲完,然后,过样例,测了几组数据,交了,WA。查查代码,晕,漏了一大段,可能都被F打蒙了。补上,感觉不可能错。还是WA。当即就郁闷了,快速幂矩阵,敲了那么多次怎么可能错。查代码,3个人一起查,终于Feeling发现了负数的处理。啊~~我以前的矩阵都未写过负数的。tothemax,帮改了下。终于AC。

再刷榜,5题最后。

好了,再刷榜,H,D都有人过,D之前就跟冷冻说了,后缀数组。但是那个用法还是不熟悉。在最后的时刻我们做了如下分工,我开D。我记得矩阵切割的题目,是肯定可以做的。tothemax重打F,Feeling,水H。过程不说了,反正我的D实现了绝大部分,但是细节上挂了,交上去未知原因TLE。F不加剪枝过了,只能够说我之前写的F某处出问题了。。导致,未知原因TLE(怎么今天写代码都未知原因TLE啊)。

F题,给你一颗树,求根到所有点的最少时间

再刷榜,6题最后。不过6题的不多,上到第3。

F是剩下25分钟的时候过的。那个时候他们两个跑出去,说就给我机器,我就纳闷了~~悲剧了。我的D遇到了细节,开始补丁流,还是不过样例~~然后,Feeling回来,剩下10分钟,我就跟她说,不行啊,我写不出。让她机器。我看她重新了个程序,然后上交,忘记返回是WA 还是TLE。然后,给回我调,我就是调不出。然后,她说改下,我就让她改,再交,剩下4分钟,竟然YES。

H题,求某字符串的回文字串个数

再刷榜,7题最后。上到第2。我也楞了~~怎么她随意改下就过啦,我D就是似乎调不出,我晕~~

能够在初期劣势这么大的情况下,打回来,真的很幸运。

纵观全场,我们队从1:3落后好长时间之后,就开始了提交流,每次都是N题最后,说实话,RP实在是比较重要的~~能在最后压过,永根他们队靠的就是运气。当是,Feeling也是,随意地试试的。只能够说,我的队友很牛B,我很水B。

  评论这张
 
阅读(187)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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