算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
酱了个油。。。。。

前天中午到长春,水了水邀请赛,本来想测测环境的。。。但是感觉太累了,没什么激情,就水了水题。。。
晚上群聚,很happy,攒了很多人品。

昨天正式赛,早早到了赛场。。。在外面想找岛神涨些人品,但是没有看到= =
比赛开始,我从中间看题,但是感觉题目描述都好长。。。
找到了描述较短的G,找出一个回文子串,使这个串的多项式哈希值 mod 777,777,777是第k大的。。。
除了后缀数组乱搞我没什么特别好的想法,而且必超时。。。于是看H。。。
定义一个数列A,A的和等于N,A的最小公倍数等于M,A的长度等于K。M,N<1000,K<100,求A的方案数。
不知道为啥,我就想到整数拆分去了。。。。 于是去拉了躺翔。。。 没有找到满意的解法。。。
回来之后看了E,给一颗树,找到一个点使所有点到这个点的路径的最小边权之和最大。想了想树DP什么的,未果。。。
看了D,数学什么的最讨厌了。。。

于是我就迷茫了,看大家都过了K,磊哥和lulu在一起看K。这时清华突然过了H,我就确信H没有我想象的那么复杂。
于是想到可以一个一个加点然后DP。于是上去搞之。

这时lulu问我一个公式的单调性,我说根据导数来看是单峰的。于是lulu确定K可以三分搞。
敲了半天E,交之,返回re,lulu上去搞K,我下来发现对因子数的估算可能是错的,于是改大点再交,果然返回wa了。。。
我想卧槽我这么稳的选手居然提交两次都跪了。。。这把要难了。。。。
于是上个厕所回来,发现代码中的小漏洞,再交61min H3y。

lulu上去一会觉得不对,于是磊哥上去敲B。B过得人也很多了,我看有些队过了C,于是看题。
题目大概就是个。。。。枚举吧。。。。
磊哥敲了150+行的B,感觉不对,于是下来了。我当时感觉有点跑偏了。。。。。

上去敲C,99min C1y

下来之后,我看有人过了E,于是各种想E,各种不会。。。 lulu和我确定了一下K题的做法,k题是求
k^1 + k^2 + ... + k^r = n的方案,n <10^12。
其实枚举+二分就可以了,但是我当时被lulu带进他的公式里了。

后来幸亏跳出来了。。。。141 k2y。 其中因为long long 的问题跪了一次。看来状态都不佳。。。。。

E题我觉得不能在深陷树DP的泥潭了。于是换了一个贪心的思路,但是没什么进展。于是和lulu交换了下思想,然后去看A了。
lulu非常给力了解决了我那个方法的瓶颈,于是191min E1y。

磊哥B题wa了一次,而且一直没有找到错误。我也因为J题描述太长没有看J题。
可以说因为这两个错误我们与金奖失之交臂。。。如果能早些沟通。。。。因为我们这时的罚时还处于可以挽救的地步。

这时B题大概过了50多个队了,我知道磊哥思路肯定跑偏了。于是我看题,发现是2-SAT。。。。
在我敲的过程中,B题有多了两次wa。我还范了点小错误,明明不到一周前还敲过tarjan....
B246min 4y

这时磊哥和lulu确定了J题,是LCA,于是lulu开始敲,我继续看A题,并且确定了做法。。。。

但是J题比赛结束前15min才敲完。。。。 并且TLE到了最后。。。
最后我问lulu,原来是暴力求的LCA。。。。

最后rank 32。。。。

要是能多一些沟通。。。。就不至于跪成这样了。。。。其实赛前就知道拿金基本上没可能,但是这个跪法太让我难受了。
明明有100分的实力,最后只发挥了60分左右。。。如果我能早点看B和K和J的题。。。如果不在E卡那么久,早点和lulu分享下做法。。。。
如果最后J由写过十多次LCA的我来敲。。。。

一切都是假如了。。。就算假如都实现了,我能确定A一定能过么。。。唉,讨论这些没用,成都再战吧
posted on 2012-10-15 22:44 西月弦 阅读(434) 评论(2)  编辑 收藏 引用 所属分类: 比赛感言

FeedBack:
# re: 2012亚洲区长春站
2012-10-15 23:03 | YAIMH1993
我也在zoj上做了B题,但是我使用并查集做的。我是若菜,希望能够与大神多多交流,这是我的博客里的题解,希望大神多多指正
http://hi.baidu.com/yaimh1993/item/68c8f7c2abc95f3c5150585f  回复  更多评论
  
# re: 2012亚洲区长春站[未登录]
2012-10-15 23:10 | lenohoo
我也是用并查集做的,顶楼上,哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈!!!!!!!!!!!
飞哥,你弱爆了,还是有人用并查集做的嘛,哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈!!!!!!!!!!!!!!!!!  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理