算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
先说感想!
这场比赛,期望很高,结果很差。好在不是regional,还有很长的补救时间。
昨天在火车上和孟神看《灌篮高手》,觉得自己的境遇和赤木很像,一年又一年的苦等,执着。。。
今年已经是最后的机会,不可以给自己留下遗憾!

再说过程。。。

热身赛有奖金,很炫酷。 但是目测了一下来的队伍,觉得拿奖金有点悬。。。
A题,大数除法,让xy上去敲一些模板。
然后孟神看了C,题意是给出仅包含[0-9]的字符串A,B。每次可以进行一个操作,将某个数字集体上翻一次(如果是9就变成0),或者将某个数字集体下翻一次(如果是0就变成9)。
上翻和下翻的花费是不一样的。一开始以为是可以上/下翻任意次,互相不影响,以为是水题,换下xy敲之。发现最后一个样例没过,发现自己读错题了。于是还是让xy敲A。

过了一段时间,xy的A敲好了。反复调试,没过样例。于是打印出来和模板diff....(吐血。。。。)
期间我和孟神确定了B题的做法。题意是,给出10^5个大小为100的字符串,然后输出出现次数最多的三个字符串。根据字符串hash可以马上确定10^5 * 100的空间的做法。
因为这题最后是按照空间判优,隐隐觉得应该没有更好的空间复杂度了。。。。
不久之后敲完,80min B 1y

在我敲B的过程中,孟神和xy找出了A的一些bug。果断改之,九十多分钟也是 1y。
之前xy卡A的过程中,我yy出了C的解法,表面看,dp的状态数是 11^10,但是其实拓展出来的不会超过 10! (因为最优方案最多转移10次,就会让所有的数一样)。
于是果断spfa上跑dp,这种题喜闻乐见了,唯一的新奇之处就是动态拓展出状态,把新状态和其dp值,vis值都扔到map里面,118min 1A。

然后看D:判断一个轨迹是否是"n"
hough变换 ? 手动构造n提取shape-context特征?
反正当时是基于x和y的变化率分段乱搞,可惜最后没有敲完。。。。

于是就非常幸运的热身赛夺冠,拿了1200。。。。


于是为正赛的悲剧埋下伏笔。。。
上来看到A题,怒敲之,转int + 0.5 /100.0 然后 cout ,莫名其妙WA。
扔给xy,搞D题,并查集水题,犯了点小错误卡了一会,交之,WA。
扔给孟神,敲H题,基于博弈的DP,48min 1y。此时我知道这场肯定是逆风局了。。。
孟神看出D题的数组开小了,改之,55min 2y。期间我以为我会做E了,上了趟厕所去想一下细节。。。
xy重敲A题,70min 4y。
E题求gcd(a,b,c) = 1,lcm(a,b,c) = k的(a,b,c)三元组个数。
期间误以为是 a*b*c = k ,分解质因子之后,各种容斥+组合数,敲完后发现样例不对,才发现自己犯sb不要紧,还不去检查样例。
好在xy提醒了我正确思路,也是基于分解质因子,大部分代码都没白敲,117min 1y。
4题之后15名,还在金区,不到2个小时,这个局势其实可以接受,属于小逆风节奏。


但是接下来一切都不一样了。
孟神给我讲了G题,说是3进制状态压缩,略难敲,我也感觉这样绝对可搞,而且属于中规中矩,并不很难敲(事实证明,还是有点难敲。。。),中间转移的部分需要枚举。
之前xy和孟神讨论了暴力做法,但是被孟神否了。。。。。要是xy把暴力做法给我讲了的话。。。。

于是我就开始敲。。。。。敲得过程中发现是4进制dp,真是各种难写啊。。。。 最后各种调试,总算178min 2y。此时rank 14。。。。

如果这是问题1的话,其实还是可以挽回的,但是问题2就是硬伤了。。。

在这期间,xy和孟神讨论了I,和我讲了一下,我觉得靠谱,于是搞之,wa。。。。发现题意理解错了,于是我就一头钻到I里面了。。。。。
此时可做题: B,C,I,J。J我看了下,觉得大脑内存不够,无暇去想,C题他俩都没看懂,我就懒得去看了。B题xy给我讲了一下,我在全神思考I,无暇管B。。。

后来连wa四次,一口老血就把I撇给孟神了。回去确定了C的题意和O(n^3)做法。。。(多校原题。。。。)


最后时刻debug结束,提交。。。WA。。。。

(捶桌。。。。)
两个问题: 1是题目做法没有及时交流,2是平均实力不够。2很大程度可以弥补1,以上。。。。

之前牛逼吹大发了,看来是不能当人了,我艹。。。 这个得在regional找回来。。。在次之前随便谁怎么说吧,我需要调整一下,争取恢复到去年这个时候的状态。
uptdate1 :
C就算N^2的也不算难写,先O(n)求回文,拓展的部分dp,见hdu 2859。
I题最稳妥应该差分约束。。。而且点很少,时限和编码量都少,非常靠谱,次奥。。。
posted on 2013-05-28 00:53 西月弦 阅读(826) 评论(11)  编辑 收藏 引用 所属分类: 比赛感言

FeedBack:
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结[未登录]
2013-05-28 01:12 | xiaodao
。。。仰慕 1200。。~  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-28 01:17 | 西月弦
@xiaodao
I题真有可能你们是正解。。。反正按照hime的反例,判断二分完全图是错的了。  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-28 08:34 | HEU_xueyan
坑队友了~  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-28 08:45 | 浅雨歌
真的卡到I题里面去了……当时看榜的时候感觉果断应该改成J题或者C题,当时看题目情况是C题19提交7A,J题20提交8A,I题66提交2A,感觉肯定有坑……不过这个战况看来……重点是策略失误而不是实力问题……figo加油,下面的比赛肯定能找回场子……  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-28 08:54 | isaacpei
figo乃们其实不错滴,有1200又有帝都一日游。偶们这种银牌第二啥都木有的渣渣更是悲剧  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-28 09:40 | silver__bullet
最大的败笔还是G。。。都怪我>_<
MLGB...regional之前TC不黄誓不为人!!!!  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-28 13:47 | 西月弦
@isaacpei
你们做出了 F, Orz..  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-28 13:48 | 西月弦
@silver__bullet
你最好把TC div1的250和500都弄会,这样肯定能变黄  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-28 13:49 | 西月弦
@浅雨歌
其实是实力不济导致了策略失误,如果C,J,B都能较快确定那肯定会优先选择的  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-29 10:36 | 啊实打实大阿道夫的
C题是多校原题 能找到题号吗?? 谢谢  回复  更多评论
  
# re: 【奋战2013regional】 老骥伏枥,志在千里 --- 通化邀请赛总结
2013-05-29 15:12 | 西月弦
@啊实打实大阿道夫的
2859  回复  更多评论
  

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